Linked lists
Linked lists are an example of a linear data structure, with linked lists the elements are not stored at
contiguous locations but are rather linked through pointers… they form a set or series of nodes.
The structure of a node
Nodes typically contain two components:
• Data – this is the actual value or data assigned to the node
• Pointer – this stores the memory address of the next node in the sequence
The head of the linked list is the first node in the sequence, and the tail of the linked list is the last
node in the sequence… the last node in the list points to NULL which indicates that there isn’t a
node that comes after.
Why do we use linked lists?
• They are a dynamic data structure – this means the size of the linked list can be altered at
runtime as a result of the insertion and deletion operations
• The ease of insertion and deletion operations – the insertion and deletion of elements from a
linked lists is a much simpler process than with arrays. There is no shifting of memory
locations that needs to happen when performing these operations, you would simply just
update the memory address
• They have efficient memory utilisation – Since linked lists are dynamic data structures and
they allow us to alter their size accordingly, this avoids the wastage of memory
What different types of linked lists are there?
We will touch on mainly two types of linked lists:
• Single linked lists
• Double linked lists
• Circular linked lists
In a singly linked list, the nodes contain a reference to the next node that’s in the sequence and
when we traverse a single linked lists, we do so in a forward direction.
In a doubly linked list, the nodes contain references to both, the next and previous node in the
sequence. This property allows us to traverse a doubly linked lists in both, a forwards and
backwards direction… traversing in a backwards direction however, requires more memory than
traversing in a forwards direction.
In circular linked lists, the tail points back to the head and this creates a circular pattern. A circular
linked list can either be singly linked or doubly linked.
What operations are performed on linked lists?
• Insertion – this is adding a new node to an existing linked list, it requires adjusting the
pointers of the other nodes in order to maintain the proper sequence. Insertion can happen at
any position in the list (beginning, middle, end)
• Deletion – this is removing a nodes from an existing linked list, it also requires us to adjust
the pointers of the other nodes to accommodate the free location left by the deleted node.
Deletion can also be performed at any position in the list
• Searching – this involves searching for a specific value within the linked list, we do so by
traversing from the head of the list until we reach the specified node or until we reach the
end of the list
What are the advantages and disadvantages of linked lists?
Advantages:
• They have dynamic size – they have the ability to increase or decrease dynamically because
memory allocation is done at runtime
• Inserting or deleting nodes from a linked list is efficient, regardless of the size of the list
• Linked lists are flexible – this means they can be easily reorganised and modified without
requiring a contiguous block of memory
Disadvantages
• No random access – unlike with arrays, linked lists don’t allow us to directly access a node
using an index, so we need to implement the traversal operation in order to find a given node
• Additional memory – linked lists require more memory in order to store their pointers,
unlike with arrays
