根据此程序,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 LinkedList中的时间:537

Answer 1

你在这里有一个案例.在这种情况下,您在索引处添加和删除.链表实现不知道哪个项位于该位置,因此每次都必须在那里计数.此操作将更慢.

相反,如果你有链接列表中项目的迭代器,那么此时的插入和删除变得非常快,因为没有复制数组或放大容器数组.这是链接列表更快的一般情况.

这种行为的一个示例是当您迭代列表并需要根据某些条件删除项目时.然后,每次需要删除一个项目时,单个链接列表只会将前一个项目设置为指向已删除元素之后的元素并销毁已删除的元素.这是恒定时间操作.使用数组(列表),这将需要向后复制数组的其余部分,这是一个慢得多的操作,并取决于数组(列表)的位置和大小.

因此链接列表通常更快或更好是不正确的,这就是我们仍然使用常规数组和列表的原因.它们随机访问速度慢,但正确使用时速度更快.