根据维基百科关于链接列表的文章 http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._arrays，在链表中间插入被认为是 O(1)。我认为这将是 O(n)。您是否不需要找到可能靠近列表末尾的节点？
此分析是否没有考虑节点操作的查找（尽管这是必需的）以及插入本身？
EDIT:
与数组相比，链表有几个优点。在列表的特定点插入元素是一个恒定时间操作，而在数组中插入可能需要移动一半或更多元素。
上面的说法对我来说有点误导。如果我错了请纠正我，但我认为结论应该是：
Arrays:
- 查找插入/删除点 O(1)
- 执行插入/删除 O(n)
链接列表：
- 找到插入/删除点 O(n)
- 执行插入/删除 O(1)
我认为唯一不需要找到位置的情况是，如果您保留某种指向它的指针（在某些情况下，就像头部和尾部一样）。因此，我们不能断然地说链表在插入/删除选项方面总是胜过数组。
您是对的，本文将“索引”视为单独的操作。所以插入本身是 O(1)，但到达中间节点是 O(n)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
