java - java的LinkedList类中的元素是否有索引？

Question

java的LinkedList类中的元素有索引吗？如果是 那么当它可以直接使用对象的索引进行搜索时，为什么在搜索操作的最坏情况下它的性能为 o(n)？如果否 那么我们如何使用void add(int index, Object item) 方法在链表的中间插入一个对象？

Answer 1

它们有一个逻辑索引，是的 - 实际上是您需要迭代的次数，从头部开始，在到达该节点之前。

这与说“它可以使用对象的索引直接搜索”不同——因为它不能。

通常 O(1) 的索引访问是通过使用数组查找执行的，在链表的情况下，不是数组 - 只有节点链。要访问索引为 N 的节点，您需要从头部开始并沿着链走 N 次...这是一个 O(N) 操作。