Singly Linked Lists
by Jakub Brettl
Linked lists are perhaps the most simple abstract data type (ADT) and they can serve as a relatively easy entry point to all other - more complex - algorithms and data structures. Understanding linked lists can be an easy gateway (drug) to begin uncovering the mechanics of other algorithms.
A linked list is a linear dynamic data structure. What do we mean by that? It means that linked lists can grow/shrink dynamically as elements are being added/removed. This is unlike arrays, for example.
Linked lists are composed of nodes which are connected to construct a chain-like structure via pointers. The last node, too, has pointer (pointing to "None").
The first node -- called the "head" -- in the linked list is also special as it is the entry point to the linked list.
Example of a singly linked list:
Linked Lists versus Arrays
Linked lists are conceptually similar to arrays. Arrays, same as linked lists, are used to store a collection of data. One key characteristic of arrays is that one memory block is allocated for the entire array. When new items need to be added to already full array, we must create a new empty array (with more space in it) and copy items from the old array to it. Linked lists, on the other hand, allocate memory dynamically as new items (nodes) are being added/removed to/from the list.
Example of an array:
It is clear from the example above there is a potential performance penalty for arrays over linked lists. There are, of course, instances where linked lists have disadvantages over arrays. Possibly the most important disadvantage of linked lists is access time to the individual elements. While in arrays the individual elements are accessible via the index in a constant time (Θ(1)). Linked lists, in many use cases take (Θ(n)). In other words, it always takes constant amount of time to access elements in array irrespective of its size. The access time to elements in linked lists grows linearly with the size of the linked list. This can lead to large differences in access time for very large linked lists and arrays. Hopefully, the reason why this is so will be clear by the end of this blog post.
Linked List Operations
Key operations on linked lists are as follows:
- Inserting element into the list
- Deleting element from the list
Addition operations may be:
- Deleting all elements in the list at once
- Counting all elements on the list
- Finding Nth node in the list
Linked List Node and Linked List Instance
Linked list consists of individual nodes. Each node is equipped to a pointer to the next node. Two special nodes are the head (the first node in the list) and the tail (the last node in the list). The head has an additional pointer to it indicating that the node is indeed the first node in the list. The tail has a point which points to None.
The Python code below is a an example of implementation to initialise Node and LinkedList instances. The node has additionally some helper methods to, for example, set/get node's payload ('data') and its pointer ('next').
The LinkedList instance is initialised with its head pointer only.
class Node:
"""Create and initialise Node class instance."""
def __init__(self, data=None, next=None):
self.data = data
self.next = next
def set_data(self, data):
self.data = data
def get_data(self):
return self.data
def set_next(self, next):
self.next = next
def get_next(self):
return self.next
def has_next(self):
return self.next != None
def __repr__(self):
"""Create string representation of Node instance."""
return f"Node({self.data})"
class LinkedList(object):
"""Create and initialise an instance of linked list."""
def __init__(self, node = None):
self.head = node
Traversing the list
In order to traverse a linked list one follows the pointers of each node. Normally traversing of the list starts at the head of the list (the node with the 'head' pointer) and stops when a node with 'None' pointer is reached.
In Python the process to travers the list can be implemented very simply using the 'while' statement as follows:
node = self.head
while node:
node = node.next
The above code starts at the head ('node = self.head') and proceed to loop over the entire list until it reaches the end when the 'while' statement will return 'False' (when 'node = None').
A more sophisticated implementation of way to traverse the list can be made using the iter dunder method of Python and 'yield' keyword which turns the function to a generator object.
def __iter__(self):
"""
Make Linked List an iterrator.
linked_list = LinkedList()
linked_list.insert_head(4)
linked_list.insert_head('Hi.')
for node in linked_list:
node
"""
node = self.head
while node:
yield node.data
node = node.next
In this implementation 'yield' returns the payload of the node ('node.data').
Singly linked list insertion
There are three basic cases to make insertion to a list:
- Insert new head
- Insert new tail
- Insert at specified position of the list
Insertion at the beginning
Inserting a new node at the begging of a list is rather inexpensive operation. All that needs to be done is:
- Initiate a new instance of a node with its payload (data);
- Point the new node's pointer to the existing head of list; and
- Reassign the 'head' pointer from the existing head to the new node.
In practice, the operation is done in two steps only.
Create a new head (node) and set its pointer to the existing head of the list:
Mode the head pointer to the new new node:
In Python, the implementation of the above is done exactly the way it is described above. The only additional step that one can see bellow is that a check is made on where or not there is an already existing head in the instance of the linked list ('if self.head == 0:'). If this is the case, the only thing that needs to be done is to set the new node as the head ('self.head = newNode'). If there is at least one node in the existing instance of linked list then the two steps described above are performed, i.e. set the pointer of the new node to the existing head ('newNode.next = self.head') and set the head of the linked list to be the new node (self.head = newNode).
def insert_head(self, data):
"""Insert new node at the head of the linked list instance."""
newNode= Node()
newNode.data = data
if self.head == 0:
self.head = newNode
else:
newNode.next = self.head
self.head = newNode
Insertion at the end
Inserting new node at the end of the existing linked list is somewhat more complex than inserting at its head. The additional step that needs to be done is that one needs to traverse across the entire list to find the list node and only then insert the new node and reset pointers accordingly.
Create a new node and its pointer is set to 'None':
Last node of the existing tail is set from 'None' to point to the new node:
As mentioned above, from implementation point of view, the additional step that is need is to traverse the list to find the list node. This is achieved through the following mechanism:
while current.next != None:
current = current.next
Because of this extra step, i.e. traversing across the list, one immediately see that the adding a new node at the head of the list is done at constant time Θ(1) while adding a node at its tail is done at Θ(n).
def insert_tail(self, data):
"""Insert new node at the tail of the linked list instance."""
newNode = Node()
newNode.data = data
current = self.head
while current.next != None:
current = current.next
current.next = newNode
Insertion at a given position
In order to insert a new node in a given position, one has to traverse the list to one position before the desired position. Then we can insert the new node at the desired position (one position after the one we stopped at) and set its pointer to the following node. Finally, we set the pointer of the proceeding node to point to the new node. Schematically, the operations are performed as follows:
Create a new node and set its pointer to the node in the following position:
Set the pointer of node in the position where we want to place the new node to point to the new node:
In Python, one first needs to check whether or not the desired position actually exists. If the desired position is 0, the new node is placed at the head of the list. Otherwise the script performs the operations described above.
def insert_anywhere(self, data, position):
"""Insert node at specified position."""
if position > len(self) or position < 0:
return None
else:
if position == 0:
self.insert_head(data)
else:
newNode = Node()
newNode.data = data
count = 1
current = self.head
while count < position-1:
count += 1
current = current.next
newNode.next = current.next
current.next = newNode
Singly linked list deletion
Similar to inserting new nodes to the list, there are three basic cases for deleting nodes from a list:
- Deletion of a first node (the head)
- Deletion of the last node (the tail)
- Deletion of a node at some given position
In addition the three basic use cases above, I will also cover the case of deleting all data from the list.
Deletion at the begging
When deleting the head of the list one simply resets the head pointer from the first node to the second. Subsequently the old head is deleted.
- Set the current head pointer to the next node in the list:
In Python, the deletion is performed as described above: 'self.head = self.head.next'.
def delete_head(self):
"""Delete head of the linked list instance."""
if len(self) == 0:
raise ValueError('Empty instance of linked list, nothing to delete.')
else:
self.head = self.head.next
Deletion at the end
When deleting nodes at the tail of the list one needs to travers the list to the position before the last. Subsequently the pointer of the second to last node is set to None and the previously last node is discarded.
- Traverse across the list to the second to last position and set the pointer to 'None':
From Python implementation point of view, the above described mechanism is implemented via the following code:
while current.next != None:
previous = current
current = current.next
previous.next = None
Full implementation of the method is presented below.
def delete_tail(self):
"""Delete tail of the linked list instance."""
if len(self) == 0:
raise ValueError('Empty instance of linked list, nothing to delete.')
else:
current = self.head
previous = self.head
while current.next != None:
previous = current
current = current.next
previous.next = None
Deletion at an intermediate position
Deleting nodes at an intermediary position, neither the head or the tail are affected. The removal is done in two steps:
Once we find the position to delete, we set the pointer of the previous node to point the node after the one that is being deleted. Finally, we discard the unwanted node.
- Traverse across the list to the desired position and set pointer of the previous node to point to the node after the one being deleted:
In Python the above described mechanism is implemented below. The key mechanism of deleting the node and reassigning pointers is implemented in the following way: 'previous.next = current.next'.
def delete_position(self,position):
"""Delete node at specified position."""
count = 0
current = self.head
previous = self.head
if position > len(self) or position < 0:
raise ValueError('Position does not exist.')
else:
while current.next != None or count < position:
if count == position:
previous.next = current.next
return
else:
previous = current
current = current.next
count += 1
Delete all data
Deleting a linked list is rather easy. All that needs to be done is to set the head of the linked list instance to 'None'.
In Python this is implemented as follows:
def delete_instance(self):
"""Delete all data in linked list."""
self.head = None
Concluding notes
I hope you find he explanation on the functioning and implementation of singly linked list is useful.
I wrote other blog posts on the implementation of linked lists. Namely:
All code that used in the blog post can be found in this GitHub repo.