Linked Lists

A linked list is a dynamic data structure that store item in nodes.

• Can dynamically add new items, it has no fixed size

Arrays can mimic this but they essentially create copies of themselves with new dimensions when resizing 

• This has implications for both memory and processor usage

Each node in a linked list has a pointer which points to the address of the next node.  Each element of a linked list is called a node.

The start of a linked list is called the HEAD and the last element points to the NULL.  Each node has its own address in memory, and stores the data item and a pointer to the next node. The following diagram represents a node.

Example Single Linked List

A simple example of a single linked list with four nodes is shown below. The four node linked list stores the words ‘Computing’, ‘Science’, ‘is’, and 'fun'.

• A linked list can store data of multiple data types; a 1-D array is usually limited to one.

• A linked list is a linear data structure; to get to a specific data item, it must always start at the HEAD and work through each node until the data is found.

  • A single linked list can only be traversed in one direction,  from HEAD to NULL.

• Inserting and deleting data into/from a linked list is more efficient than a 1-D array

  • When inserting only a pointer is changed rather than shifting the contents of the list (array) into different memory locations.

  • When deleting only a pointer is changed rather than shifting the contents of the list (array) into different memory locations.

To insert new data into the list, for example inserting the word ‘really’ between ‘is’ and ‘fun’.

1. A new node is created somewhere in memory.

2. The list is traversed until ‘is’ is found.

3. The pointers for the node (is) is updated to refer to the new node.

4. The pointer for the new node is set as the next existing item in the list. 

To remove data from the list, for example removing the word ‘Science’

1. The memory location where the node is stored is freed up.

2. The list is traversed until the node before ‘Science’ is found.

3. The pointer before science is updated to the pointer for the node after ‘Science’.

• Adding a new node at the end

The pointer of the last node will have to point to the newly created node.

• Inserting between existing nodes

When a new node is added then the pointer of the previous node has to be amended to point to the new node and the new node has to point to the node that was previously next in the list.

• Deleting nodes

The pointer of the previous node before the item to be deleted will be amended to point to the next item in the list.

• Traversing lists

Each node has to be visited and the pointer followed to the address of the next node.

A double linked list is very similar to a single linked list, but has an additional pointer in each node that stores the address of the previous node. This means the list can be traversed in both directions.

The following diagram represents a node in a double linked list.

To insert new data into the list, for example inserting the word ‘really’ between ‘is’ and ‘fun’

1. A new node is created somewhere in memory

2. The list is traversed until ‘is’ is found.

3. The pointers for the node (is) is updated to refer to the new node

4. The previous pointer for the new node is set as the next existing item in the list (is).

5. The next pointer for the new node is set to the address for the next node ( fun) 

To remove data from the list, for example removing the word ‘really’

1. The memory location where the node is stored is freed up

2. The list is traversed until the node before ‘really’ is found.

3. The next node pointer before really is updated to the pointer for the node after ‘really’

4. The previous node pointer of the next item in the list is set to the new previous node ('is)