Linked List (Unordered)

A linked list is a data structure in which each node points to the next, with a null pointer (usually denoted by -1 in Cambridge exams) representing the end of the list

The tutorial will walk through the following:

1. Declaration & initialisation
2. Adding a node at the beginning of a linked list
3. Adding a node at the end of a linked list
4. Searching for a value in a linked list
5. Removing a node from a linked list
6. Outputting the contents of a linked list

Examples of where singly-linked lists are used in real-life:

• Chaining method for hashing
• A list of tasks to complete

More useful are often doubly linked lists, where we have a pointer to not only the next node, but the previous too - while you are required to know about them for the syllabus, you aren't required to implement them in code. Some possibly uses:

• Navigation history - back & forward buttons in web browsers, media players, image galleries etc
• Undo/redo features in software
• Slideshow

In real life, sometimes an array might also be appropriate - some advantages/disadvantages of linked lists:

• Dynamically-sized - can add or remove nodes (arrays are usually fixed-size - or if arrays/equivalents (e.g. ArrayLists in Java) support dynamic allocation, then resizing the array is slow (requires copying element))
• Nodes don't have to be stored contiguously in memory like arrays, since pointer can point to any memory address
• Inserting & deleting is fast - only pointers have to be updated
• Searching is slow - requires node by node traversal
• And while beyond the scope of the syllabus, cache misses can also be an issue, since consecutive nodes aren't necessarily stored contiguously in memory (unlike with arrays, where an entire page can be loaded into cache which might have e.g. the first 1000 array elements)
• Higher memory requirement - since pointers also need to be stored, along with data
• More complex to implement than arrays

In contrast, some advantages/disadvantages of arrays:

• Accessing a specific element by index is faster (O(1) vs O(n) for linked lists (where node by node traversal is required))
• Inserting/deleting from start/middle is slow - since other elements have to be shifted

For exams, Cambridge often likes to create an array of nodes - hence we first define a node record that contains both the data value the node stores and an integer pointer representing the node this node points to

We then specify the two additional pointers we will need - the freeListPointer which points to the start of the list of unused nodes and the headPointer which points to the start of the active linked list containing the data

A Reset() procedure (could also call Initialise()) is also created to set all nodes as being part of the free list and assigning default values to the pointers

Adding a node at the start of a linked list is fast, since we don't have to traverse through all nodes like we do if we insert at the end - the possible issue is that the nodes will be in "reverse" order to the order we inserted them - if wanting stack behaviour or if order isn't important, then this isn't an issue

Exams will specify whether nodes should be inserted at the start, end or in the correct position in the case of an ordered linked list (next tutorial)

The general idea is quite simple (easier to understand with a diagram...will be added)

1. Store the current head pointer, since we'll need to make the new node point to the old head
2. Take the first element from the free list by assigning the free list pointer value to be the new head pointer
3. Update the free list pointer to point to the next (2nd) element in the free list
4. Assign new node's data and set its pointer to be the previousHeadPointer - i.e. the new node has been inserted before the current first node, hence has to point to it

Adding a node at the start of a linked list is slower since we first have to traverse through all nodes (or we have to store a tail pointer to the last node = fast)

The general idea is quite simple (easier to understand with a diagram...will be added)

1. First we traverse through the list to get to the last element
2. Then we take a node from a free list and update the relevant pointers

In more detail, we'd:

1. Ensure the list isn't full (that there are still nodes in the free list)
2. Assign newNodePointer to be the first node in the free list
3. Set freeListPointer to point to the next node in the free list
4. Assign data and a pointer value of -1 (null pointer - since we're inserting at the end) to the new node
5. If list is empty, set headPointer to be the newNodePointer (we don't have to modify any exist node's pointer - since there is no node in the list)
6. Else, start from the head pointer and traverse the list until finding the node with a pointer value of -1 (i.e. the end)
7. Make this node point to the newNodePointer

We can search for a value in a linked list with a linear search - but rather than simply incrementing the array index variable, we need to traverse the list by following the pointers

1. Start from the headPointer
2. Follow pointers while not reached the null pointer
3. If any node's data value is equal to what we are searching for, then return TRUE
4. Else, if we have left the loop, that means we have searched all values and not found the node we're searching for, hence we can return FALSE

Removing a node from the linked list follows a similar pattern to search - traversing the list node by node until we find the node we are aiming to remove

We then have to update the pointers correctly - there is a special case for if the node to remove is the first node

We also need to keep track of the previous node, since when we find the node to remove, we also have to modify the previous node's pointer to point to the node the current node points to (to remove/"jump over" the current node)

The full algorithm is:

1. Assign current & previous pointers to the head of the list
2. Traverse list until found element
3. Set previous node's pointer to point to the next node (i.e. current node's pointer) to remove the current node from the list
4. Once found, if it's the first node, also set the headPointer point to the new first element
5. Add removed node to beginning of free list pointer by making it point to the current first element in the free list, then making the free list pointer point to this removed node

Outputting the contents of a linked list is relatively simple - just follow the pointers as we've seen before and output each node's value

For debugging/easier understanding, we may also want to loop through the array and output the index, data and pointer value of each node

Here is the full implementation of the linked list: