当插入和删除列表中间时，LIKEDLIST比ARARYLIST快。只是“在中间”？

Question

好吧，关于LinkedList和ArrayList有很多讨论，但当我在《用Java思考》中看到这个描述时，我仍然感到困惑：

LIKEDList还实现了基本的列表接口，如ARARYLIST DO，但是它比ARARYList更有效地执行某些操作（列表中的插入和删除）。

我不知道为什么它强调“在列表的中间”，我想在列表的开头插入时，ArrayList也需要转移后面的元素，而且它比LinkedList快吗？

Answer 1

ArrayList由数组支持，而LinkedList由2个引用（下一个和上一个即，由DoublyLinkedList支持）支持。LinkedList更快，因为它不需要复制数组并在调用add（int index，E元素）时将元素向右移动一个单元格。当插入中间（或索引0和当前大小之间的任何位置）时，ArrayList复制/移动元素，因此需要更多时间。而LinkedList只需要更改2个指针/引用。

ArrayList。爪哇：

public void add(int index, E element) {
..
// copying elements
System.arraycopy(elementData, index, elementData, index + 1,
             size - index);
..
}

LinkedList。JAVA

public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}

private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
// just changing the pointers
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}

Answer 2

重点是暗示ArrayList在内部需要移动元素，并为进一步插入保持开放内存，从而导致其移动和复制元素。LinkedList只需创建一个节点，然后将上一个节点的next节点设置为新节点，并将新节点的next节点设置为列表中的下一个节点。

还应该注意的是，虽然经典的LIKEDLIST会在中间插入，但是ArayLIST也会经常执行，或者比链接列表更好（这实际上是在不止一种语言之间常见的，包括C（Bjarne Stroustrup实际上有一个关于概念的讲座））。你应该仔细考虑你在做什么，并用基准来做出正确的决定。

Answer 3

之前的答案很好，但这些帮助我想象发生了什么，以及何时需要更详细的解释：

删除

和

插入