Internal implementation of ArrayList and LinkedList Collections

ArrayList underlying implementation is based on Traditional Array data structure. Read Arrays in Java , for details on Arrays.

This post focuses on internal working of ArrayList and LinkedList Collections.

java.util.ArrayList class, is internally implemented as array.

What is array data structure?

An Array is a simplest data structure, which stores same type of elements, sequentially in memory.

Static Array
Static Array

Advantage of array

Accessing an element is very fast. Since base address of array is known, the required element which need to be fetched, can be retrieved, just by doing some manipulations on base address.

Disadvantage of array

Adding an element in between or in the beginning is very slow. Reason is, other existing elements need to be moved right by one position, and new element can be added, to the free slot created. This hits performance of program, and hence it is not recommendable to use Arrays for such situations.

java.util.LinkedList class is internally implemented using linked list data structure.

What is linked list data structure

linked list is a data structure, whose elements are not stored sequentially in memory, and are scattered in the memory. As shown in below picture, each node has Element, and reference to next and previous nodes.

what is linked list
linked list data structure

Advantage of link list data structure

An element can be added any where in between, just by changing previous and next references, as shown in below picture. This operation is slow in an array, as briefed above in array section.

Size of linked list can shrink or increase, during run time, based on the requirement.

Disadvantage of link list data structure

To Access an element, all elements need to be traversed, until the specific required element is reached. Hence searching an element is slower.

Another disadvantage of linked list is, there will be wastage of small memory, since each node need to store references to previous and next nodes.

You may also like to read:
Create our own linked list
When to use List and Set
Which are non synchronized Collections?
Generic version HashSet example

One thought on “Internal implementation of ArrayList and LinkedList Collections”

Leave a Reply