Linked List

August 2015 · 1 minute read

The following article, assisted with representational diagrams, describes in simple terms what a linked list is and the data structures which create them.

A linked list is the simplest and most common form of data structure. It consists of a group of nodes which, together represent a sequence.

Fig 1: Single linked list

Each node is composed of 2 elements: data and a reference or link t o the next node in the sequence.

Fig 2: Data structure

This allows for efficient insertion and removal of elements from any position in the sequence. All that is required is a new node-link combo and a link redirection.

Fig 3: Representation of node insertion

Fig 4: Representation of node removal

Because data items don’t need to be stored in continuous memory, list insertion and removal does not require relocation or reorganisation of the entire structure.

Also, insertion and removal of elements can occur at any point on the list and a with a constant number of operations (if previous link is maintained)

A double linked list is slightly more complex and is made up of nodes, composed of 3 elements: data and two links which point to the next and previous node in the sequence.

Fig 5: Double linked list