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

问题描述

根据维基百科关于链表的文章，在链表被认为是 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屋！