Linked Lists

A linked-list is a dynamic data structure used in computer science. It consists of a collection of nodes where each node contains a piece of data (value) and a pointer (memory location) to the next node in the list.

The first node of the list is called the head, whereas the last node is the tail.

The following tables represent how the above linked list is stored in memory:

Memory Address	Node Value	Pointer
0	21	1
1	35	2
2	47	3
3	89	Null
…	…	…

The linked-list data structure is more flexible than the array data structure as it allows for efficient insertion or removal of elements from any position in the sequence.

Inserting a value in a linked list:

Let’s see how we can add the value 52 in the correct (sorted) position:


As you cans see on the table below, we have been able to add the value 52 to the linked list, in the desired position, without the need to move any other value in memory. The pointer of the previous node in the list has been updated accordingly.

Memory Address	Node Value	Pointer
0	21	1
1	35	2
2	47	4
3	89	Null
4	52	3
…	…	…

Though the data does not appear to be sorted in memory, the use of pointers enables the linked-list to have its own sequence. This makes the process of inserting and removing values from a linked list far more efficient as it does not require other values to be moved around in memory (a fairly slow process when manipulating a large amount of data).

Removing a value from a linked list:

Let’s now remove value 35 from the list:

Memory Address	Node Value	Pointer
0	21	2
1	35	2
2	47	4
3	89	Null
4	52	3
…	…	…

Circular list

Imagine all the children in the “pass the parcel” game. The parcel is passed around the children and when the last child receives the parcel, they then pass it on back to the first child in the list.

A circular list is when the pointer of the tail node points towards the head node of the linked list.

Memory Address	Node Value	Pointer
0	21	1
1	35	2
2	47	3
3	89	0
…	…	…

Double linked list

A double linked list uses two pointers per node, one pointer pointing towards the next node in the list and one pointer pointing towards the previous node in the list. It makes it easier to “navigate through” the list in both directions!

Memory Address	Node Value	Previous Node Pointer	Next Node Pointer
0	21	Null	1
1	35	0	2
2	47	1	3
3	89	2	Null
…	…	…	…

Circular Double linked list

A Circular double linked list is when the tail node points back to the head node and vice versa:

Memory Address	Node Value	Previous Node Pointer	Next Node Pointer
0	21	3	1
1	35	0	2
2	47	1	3
3	89	2	0
…	…	…	…

Other use of linked lists…

Linked-lists can be used to implement more abstract data types such as queues, stacks and binary trees.