根据这个程序，ArrayList在插入和删除中间元素的速度比LInkedList快

Question

根据下面的程序，ArrayList中的插入和删除比LinkedList要快。请给我证明在LinkedList中插入和删除应该比在ArrayList中更快。

public static void main(String args[]) {
    ArrayList al = new ArrayList();
    LinkedList ll = new LinkedList();
    int max_value = 10000000;
    // --------------------------------ArrayList-----------------------------------
    for (int i = 0; i <= max_value; i++) {
        ll.add(Integer.valueOf(i));
        al.add(Integer.valueOf(i));
    }
    int middle = max_value / 2;
    long d1 = System.currentTimeMillis();
    al.add(middle,Integer.valueOf(5));
    al.add(middle,Integer.valueOf(5));
    al.remove(middle);
    al.add(middle,Integer.valueOf(5));
    al.remove(middle);
    al.add(middle,Integer.valueOf(5));
    al.remove(middle);
    al.add(middle,Integer.valueOf(5));
    al.remove(middle);
    al.add(middle,Integer.valueOf(5));
    long d2 = System.currentTimeMillis();
    System.out.println("Time Taken in ArrayList:  " + (d2 - d1));
    // --------------------------------LinkedList-----------------------------------
    long d3 = System.currentTimeMillis();
    ll.add(middle,Integer.valueOf(5));
    ll.add(middle,Integer.valueOf(5));
    ll.remove(middle);
    ll.add(middle,Integer.valueOf(5));
    ll.remove(middle);
    ll.add(middle,Integer.valueOf(5));
    ll.remove(middle);
    ll.add(middle,Integer.valueOf(5));
    ll.remove(middle);
    ll.add(middle,Integer.valueOf(5));
    long d4 = System.currentTimeMillis();
    System.out.println("Time Taken in LinkedList:  " + (d4 - d3));
}

---

输出:

Time Taken in ArrayList: 38在LinkedList中花费的时间:537

Answer 1

你这里有一个单一的情况。在本例中，您是在索引处添加和删除。链表实现不知道哪个元素在那个位置，所以它每次都要计数。此操作将较慢。

如果你有一个迭代器指向链表中的一个元素，那么在这个点上插入和删除会变得非常快，因为不需要复制数组或扩大容器数组。这就是为什么链表更快的一般情况。

这种行为的一个例子是当你迭代列表并需要基于某些条件删除项时。然后，每次需要删除一个项时，一个链表就会将前一个项设置为指向被删除元素之后的元素，并销毁被删除的元素。这是常数时间操作。对于数组(列表)，这需要将数组的其余部分向后复制一项，这是一个非常慢的操作，并且取决于数组(列表)的位置和大小。

所以链表并不总是更快或更好，这就是为什么我们仍然使用常规的数组和列表。它们在随机访问时速度很慢，但如果使用得当，速度会更快。