Does a linked list use more memory?

This post will discuss differences between the ArrayList and LinkedList in Java.

1. Underlying Data Structure

Both ArrayList and LinkedList are two different implementations of the List interface. ArrayList is a resizable-array implementation, whereas LinkedList is a Doubly-linked list implementation of the List interface.

2. Capacity

An ArrayLists capacity at least as large as the list size, and it grows automatically as more elements are added to it. Its default capacity is just 10 elements. Since resizing degrades performance, it is always better to specify the initial capacity of the ArrayList during initialization itself.

On the other hand, a LinkedLists capacity is exactly equal to the list size, and we cannot specify the capacity during the list initialization.

3. Memory Overhead

LinkedList comes up with memory overhead since every element is a node object which stores pointers to the next and previous elements. But since the memory needed for each node might not be contiguous, LinkedList wont result in any major performance issues.

ArrayList, however, needs a contiguous block of memory in a heap for allocating the dynamic array. This might be space efficient but sometimes costs performance issues when the Garbage Collector ends up doing some work to free up a necessary contiguous block of memory in a heap.

4. Caching

Traversing through the elements of an ArrayList is always faster than a LinkedList. This is because of Sequential locality or locality of reference where hardware will cache contiguous memory blocks for faster read access.

5. Performance

We can measure the performance based on the following parameters:

⮚ Insertion at the end

add[E element]

The add operation for an ArrayList runs in amortized O[1] time, but is O[n] in the worst case. The worst-case happens when the maximum capacity of ArrayList is reached, and elements from the old array are copied to the new array, which is double the size of the old array.

For a LinkedList, add is a O[1] time operation since the specified element is appended at the end of the list and pointer to the last node is maintained by LinkedList class.

⮚ Insertion at the specified index

add[int index, E element]

The add operation at the specified index is O[n] time operation for an ArrayList as it requires shifting of all elements past the insertion point for accommodating the new element.

For a LinkedList, insertion at the specified index costs O[n] as it has to traverse the list from the beginning or the end to get to the specified index.

⮚ Deletion

remove[int index]

For both ArrayList and LinkedList, the remove operation takes O[n] time. For an ArrayList, it requires shifting of all latter elements, and for the LinkedList, it has to traverse the list from the beginning or the end, whichever is closer to the specified index.

⮚ Read

get[int index]

An ArrayList allows fast random read access, so get operation takes only O[1] time.

For a LinkedList, get operation takes O[n] time since it has to traverse the list from the beginning or the end, whichever is closer.

Thats all about the differences between ArrayList and LinkedList in Java.