CODEWITHSUNDEEP
javaarraylistlinked-list
Rocky Hu
Rocky Hu

Reputation: 1346

LinkedList is faster than ArrayList when insertion and removal in the middle of the List. Just "in the middle"?

All right, there are many discussion about LinkedList and ArrayList, but I still feel confused when I saw this description in 《Thinking in Java》 ：

The LinkedList also implements the basic List interface like ArrayList does, but it performs certain operations (insertion and removal in the middle of the List) more efficiently than does ArrayList.

I don't know why it emphasizes “in the middle of the List”, I think when insertion in the beginning of the List, ArrayList also need to transfer the back elements, and it faster than LinkedList?

Upvotes: 1

Views: 2045

Answers (3)

ekostadinov
ekostadinov

Reputation: 6940

Previous answers are very good, but these helped me to visualize whats happening and when I needed more detailed explanation:

Deletion

enter image description here

and

enter image description here

Insertion

enter image description here

Upvotes: 2

TheLostMind
TheLostMind

Reputation: 36304

ArrayList is backed by an array whereas a LinkedList is supported by 2 references (next and previous i.e, backed by a DoublyLinkedList) . LinkedList is faster because It doesn't need to copy the array and shift the elements to the right by one cell once you call add(int index, E element). ArrayList copies / shifts elements when inserting in the middle (or anywhere between index 0 and currentSize) so, it takes more time. Whereas LinkedList just needs to change 2 pointers/references.

ArrayList.java :

public void add(int index, E element) {
..
// copying elements
System.arraycopy(elementData, index, elementData, index + 1,
             size - index);
..
}

LinkedList.java

public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}

private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
// just changing the pointers
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}

Upvotes: 1

Selali Adobor
Selali Adobor

Reputation: 2157

The emphasis is to hint at the fact that internally the ArrayList will need to shift the elements, and maintain open memory for further insertions causing it to shift and copy elements. A LinkedList will simply create a node then set the next node of the previous node to the new node and set the next node of the new node to the next node in the list.

It should also be noted that while classically LinkedList will excel at insertions in the middle, there are often times when an ArrayList will perform as well, or better than a LinkedList (this is actually common between more than one language, including C++ [Bjarne Stroustrup actually has a lecture on the concept]). You should carefully consider what you're doing and use benchmarks to make the right decision.

Upvotes: 1

Related Questions