1

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?

Rocky Hu
  • 1,326
  • 4
  • 17
  • 32
  • http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Trudbert Aug 14 '14 at 05:56
  • There are cases where LinkedList is the better choice. In ten years I needed it once. Generally, it make sense to use it if you list gets updateted very very often. In any other case there is no performance boost but always a memory penalty to suffer from. So stick to the ArrayList and you will be fine. – Hannes Aug 14 '14 at 06:12

3 Answers3

2

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

ekostadinov
  • 6,880
  • 3
  • 29
  • 47
1

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;
}
TheLostMind
  • 35,966
  • 12
  • 68
  • 104
1

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.

Selali Adobor
  • 2,060
  • 18
  • 30