为什么ArrayList在开头插入元素比在java中的LinkedList花费更多时间

Question

我认为ArrayList在开头插入元素的复杂度为O(n),因为它会将其余元素向右移动一个位置.和LinkedList有O(n)在最后插入元素,因为它必须遍历每个元素.因此,上述两种操作所花费的时间应该是比较的,但是当我实际操作时,在开始时插入arraylist需要34057毫秒,而在末尾插入LinkedList只需要41毫秒,而两者都具有O(n)时间复杂度.为什么会这样？

在空间复杂性方面哪个更好？

这是我的代码

public void timeTakenEnd(String name, List<Integer> list) {


    for (int i = 0; i < 1E5; i++) {
        list.add(i);

    }


    long start = System.currentTimeMillis();
    for (int i = 0; i < 1E5; i++) {
        list.add(i);

    }

    long end = System.currentTimeMillis();

    System.out.println("time taken for: " + name + " to insert elements in the end is  " + (end - start));

}

public void timeTakenBeg(String name, List<Integer> list) {


    for (int i = 0; i < 1E5; i++) {
        list.add(i);

    }


    long start = System.currentTimeMillis();
    for (int i = 0; i < 1E5; i++) {
        list.add(0, i);

    }

    long end = System.currentTimeMillis();

    System.out.println("time taken for: " + name + "to insert elements in the beginning is  " + (end - start));

}

public static void main(String[] args) {

    ArrayList<Integer> alist = new ArrayList<Integer>();
    LinkedList<Integer> llist = new LinkedList<Integer>();

    TimeComplexity demo = new TimeComplexity();

    demo.timeTakenEnd("arrarylist", alist); //25 miliseconds on my machine
    demo.timeTakenEnd("linkedlist", llist);//41 miliseconds on my machine

    demo.timeTakenBeg("arraylist", alist);// 34057 miliseconds on my machine
    demo.timeTakenBeg("linkedlist", llist); //60 miliseconds on my machine

}

}

Answer 1

LinkedList是一个双重链表.它会记住它的第一个和最后一个元素,并允许在两个方向上遍历列表.

所以增加了端部的元件只是一个创建节点的梅特和分配last,next以及一个previous指针.这是O(1).

请注意,Java是开源的,源代码随JDK一起提供.您可以轻松找到实现:

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}