Java LinkedList 快速写入（移动、删除或添加），但访问对象是 slow.That 为什么？

Question

很多人说 Java LinkedList 添加对象比访问更快 objects.I 我检查了 Java LinkedList 源代码，我发现不像 this.Code 如下：

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

在 add 方法中，if index!=size so node 方法将是 called.The get 也是如此。

对于节点方法，它会遍历到节点before.So我认为add方法和get方法是相同的performance.i我很困惑。

感谢您的帮助。

Answer 1

你是对的。 That add() 方法是 O(N)。 这是无参数 add() 方法，即 O(1)，或者如果在末尾添加这个。

Answer 2

一个LinkedList实际上是一个称为节点的对象列表。每个节点都有一个它包含的对象和对下一个节点的引用。当您将一个对象添加到列表中时，您实际上是在创建一个包含该对象的新节点，而旧的最后一个节点现在具有对新的最后一个节点的引用。

假设您有 LinkedList 个字符串，其中包含 2 个字符串。列表中的第一个对象是一个带有第一个字符串的节点和对下一个节点的引用，第二个字符串在节点中（第一个对象有一个引用）。现在如果你想添加一个字符串，一个新的节点被创建并且字符串被放置在节点中。具有第二个字符串的节点现在被赋予对具有第三个字符串的节点的引用。

get in LinkedList 的工作方式是它从第一个节点开始，并不断查看对下一个节点的引用，直到它位于您放置在 [=12 中的索引处=] 参数，此时它 returns 该节点中的对象。这就是为什么需要这么长时间。每次调用get方法都需要从头开始迭代到索引处。

Java LinkedList 快速写入（移动、删除或添加），但访问对象是 slow.That 为什么？

Java LinkedList fast writes (moving, removing or adding),but accessing objects is slow.That is Why?

java

linked-list