Java, Adding time LinkedList vs ArrayList

Question

just adding Integer numbers to Arraylist and Linkedlist, to the last position, why adding in arrayList is faster then the linkedlist? I compiled many many times, and adding in arraylist is faster, why?

As I know, ArrayList copies an array by 2^n+1 size. while linkedlist changes only the Node

class Test1 {

public static void main(String[] args) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    LinkedList<Integer> linkedList = new LinkedList<>();

    addToList(arrayList);
    System.out.println("-----------------");
    addToList(linkedList);

}

public static void addToList(List list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 5_000_000; i++) {
        list.add(i);
    }
    long end = System.currentTimeMillis();
    System.out.println(end - start);

}

}

See [here](https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java). P.S.: Could be about the amount of memory required for the operations. — Avi, Oct 09 '19 at 19:30
Plus the usual caveat: https://stackoverflow.com/questions/2441079/java-performance-measurement Add to `linkedList` first and see how the result differs. — Marvin, Oct 09 '19 at 19:32
I have seen that post, and there was said that adding in last position is O(1) for both arraylist and linkedlist — user3422485, Oct 09 '19 at 19:33
Possible duplicate of [Is LinkedList really faster than ArrayList in the case of insertion in the middle of list?](https://stackoverflow.com/questions/16808777/is-linkedlist-really-faster-than-arraylist-in-the-case-of-insertion-in-the-middl) — Tom, Oct 09 '19 at 19:36
My link uses "insertion in the middle", but the general information regarding LL vs AL in the answers are still good. — Tom, Oct 09 '19 at 19:38
That post is not correct. `LinkedList.add()` is *O(N)* unless done with a list iterator. — user207421, Oct 09 '19 at 19:51

score 2 · Accepted Answer · answered Oct 09 '19 at 19:46

When you add to an ArrayList, you just have to store the integer in the backing array. Every once in a while, when the backing array fills up, you have to allocate a new array and copy all the old items to the new array. Given 5 million integers, you'll have to do that allocate-and-copy about 20 times (depends on the initial size of the list).

To add to a linked list, every addition requires that you:

Allocate memory for and initialize a new linked list node.
Link the new node to the end of the list.

All that extra work, for both the ArrayList and the LinkedList is done behind the scenes, by the add method.

The overhead for 5 million linked list node allocations and links is higher than the overhead for 5 million ArrayList insertions, even when you count the 20 or so allocate-and-copy operations that the ArrayList has to make when it fills up.

So, whereas each operation takes constant time (although in the ArrayList case it's really amortized constant time), the constant for appending to a linked list is higher than the constant for appending to an ArrayList.

score 0 · Answer 2 · answered Oct 09 '19 at 19:45

ArrayList does not copy the whole array every time, it creates a new array doubled in size every time there is no more space in the current array.

So if you have an ArrayList with 3 elements, the size of the underlying array is probably 4. Therefore, adding a new element does not require creating a new array and copying the 3 values, and thus has time complexity of O(1).

They are both O(1) now, but ArrayList only needs to put the value in the correct place in memory, whereas LinkedList needs to allocate new space (for the new node).

arraylist size with 3 elements is 3,not 4 – user3422485 Oct 09 '19 at 19:51 — user3422485, Oct 09 '19 at 19:51

Java, Adding time LinkedList vs ArrayList

2 Answers2

Linked