Wol*_*olf 8 linked-list data-structures
根据这个网站,我在理解为什么链接列表的时间复杂度为O(1)时遇到了一些麻烦.根据我的理解,如果你想删除一个元素肯定你必须遍历列表以找出元素的位置(如果它甚至存在)？从我的理解不应该是O(n)或我完全错过了什么？
Pau*_*ton 15
不,你没有遗漏一些东西.
如果要删除特定元素,则时间复杂度为O(n)(n元素数量),因为您必须先找到元素.
如果要删除特定索引处的元素i,则时间复杂度是O(i)因为您必须从头开始关注链接.
插入的时间复杂度仅O(1)在您已经拥有对要插入的节点的引用之后.O(1)如果您已经有对要删除的节点的引用,则删除的时间复杂度仅适用于双向链接列表.仅O(1)当您已经引用了要删除的节点和之前的节点时,才删除单链表.所有这些都与基于数组的列表形成对比,其中插入和删除是O(n)因为您必须移动元素.
使用链表而不是基于数组的列表的优点是,您可以在迭代元素时有效地插入或删除元素.这意味着例如过滤链表比基于数组过滤列表更有效.