根据这个程序，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));

}

输出：

在 ArrayList 中花费的时间：38 在链表中花费的时间：537

Answer 1

您这里是单例。在这种情况下，您要在索引处添加和删除。链表实现不知道哪个项目在那个位置，所以它每次都必须在那里计数。这个操作会比较慢。

如果相反，您有一个指向链表中某个项目的迭代器，那么此时的插入和删除会变得非常快，因为没有数组的复制或容器数组的扩大。这就是为什么链表更快的一般情况。

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

因此，链接列表普遍更快或更好的说法是不正确的，这就是我们仍然使用常规数组和列表的原因。它们的随机访问速度很慢，但如果使用得当则速度更快。

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

ArrayList is faster than LInkedList in inserting and removing the elements at the middle according to this program

java

linked-list

arraylist