为什么要在链表O(1)的中间插入? [英] Why is inserting in the middle of a linked list O(1)?

问题描述

根据有关链表的Wikipedia文章，该文本插入链表被视为O(1).我认为这将是O(n).您是否不需要定位列表末尾附近的节点?

According to the Wikipedia article on linked lists, inserting in the middle of a linked list is considered O(1). I would think it would be O(n). Wouldn't you need to locate the node which could be near the end of the list?

这种分析是否不考虑发现节点操作(尽管这是必需的)，而仅考虑插入本身?

Does this analysis not account for the finding of the node operation (though it is required) and just the insertion itself?

编辑:

与数组相比，链接列表具有多个优点.在列表的特定点插入元素是固定时间操作，而在数组中插入则可能需要移动一半或更多的元素.

Linked lists have several advantages over arrays. Insertion of an element at a specific point of a list is a constant-time operation, whereas insertion in an array may require moving half of the elements, or more.

以上说法对我有些误导.如果我错了，请纠正我，但我认为结论应该是:

The above statement is a little misleading to me. Correct me if I'm wrong, but I think the conclusion should be:

数组:

• 找到插入/删除点O(1)
• 执行插入/删除O(n)

链接列表:

• 找到插入/删除点O(n)
• 执行插入/删除O(1)

我认为您唯一不需要找到位置的就是您保留某种指向它的指针(在某些情况下为头部和尾部).因此，我们不能断然地说，链表总是在插入/删除选项中击败数组.

I think the only time you wouldn't have to find the position is if you kept some sort of pointer to it (as with the head and the tail in some cases). So we can't flatly say that linked lists always beat arrays for insert/delete options.

推荐答案

您是正确的，本文将索引"视为一个单独的操作.因此插入本身就是O(1)，但是到达那个中间节点就是O(n).

You are correct, the article considers "Indexing" as a separate operation. So insertion is itself O(1), but getting to that middle node is O(n).

这篇关于为什么要在链表O(1)的中间插入?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！