Data structures in Python – Linked List

After queues and stacks, the third article on data structures deals with linked lists.

This data structure has nodes that are connected to each other. Each node has a value and a pointer. The following figure shows a singly linked list where each node has only one pointer pointing to the next node. The first node is called the head node. The last node is called the tail node.

There are also doubly linked lists, where the nodes have two pointers. One points to the next node (like the singly linked list), the other points to the previous node.

Advantages and disadvantages

The advantage of a linked list is that the individual elements can be stored in different places in memory. In contrast, other data structures — such as arrays (array.array, numpy.array, or list) — require a contiguous storage sequence. Linked lists are characterized by a high degree of flexibility.

The disadvantage is that the search for a value starts at the top of the linked list (head node) and then jumps from node to node. It is therefore a (relatively slow) linear search (O(n)). If a linked list contains n elements, the search takes n times.

The implementation of a linked list with collections.deque

The collections module implements specialized container data types. If you have read the article on queues, you will know that collections.deque can be used to create a queue. The collections.deque class, which can be used for stacks and queues, is implemented internally as a linked list. Accordingly, it can also be used for a linked list.

Values can be added both at the beginning (with appendleft()) and at the end (with append()). Therefore, collections.deque can be used for both singly linked lists and doubly linked lists. The following example creates a new Linked List and adds four items:

from collections import deque

linked_list = deque()

# Add an item
linked_list.append(5)
linked_list.append(27)
linked_list.append(2)
linked_list.append(20)

print(linked_list)
# -> deque([5, 27, 2, 20])

The pop() method is available for removing the last element. Here, after removing the last node, the node with value 2 becomes the new tail node:

linked_list.pop()
print(linked_list)
# -> deque([5, 27, 2])

As mentioned before, an element can also be added to the beginning. Here the node with the value 100 becomes the new head node:

linked_list.appendleft(100)
print(linked_list)
# -> deque([100, 5, 27, 2])

And removing the first element is done with popleft():

linked_list.popleft()
print(linked_list)
# -> deque([5, 27, 2])

Create your own singly linked list

If you don’t want to use the collections module, you have to create a linked list yourself. This leads to the question of what functionality should be available. In any case, you will want to add a node. In addition, the linked list should also be able to be traversed. And finally, it may also be of interest whether a linked list contains any nodes at all or whether it is empty. So the following methods should be implemented:

push: Add an item
traversal: Go through a linked list
is_empty: Check if the linked list is empty

This could be realized as follows, whereby first a Node class is created, each of which represents a node. This class contains the value and the pointer to the next node:

# A Node of a Singly Linked List
class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next_node = next

Next we come to the LinkedList class, which represents the linked list itself:

# A Linked List Class with a single (head) node
class LinkedList:
    def __init__(self):
        self.head = None

We have thus created a basic structure that serves as a starting point for implementing the required methods. Let’s start with the is_empty() method, which is used to check if the linked list contains nodes:

def is_empty(self):
    return not self.head

Next is the push_node() method, which adds a value to the end of the linked list:

def push_node(self, value):
    new_node = Node(value)
    if self.head:
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node
    else:
        self.head = new_node

Let’s take a closer look at this method. First a new node is created:

new_node = Node(value)

Next, let’s look at the else block of the following if statement:

if self.head:
    …
else:
    self.head = new_node

If no node exists yet, this part is called and a new head node is created:

self.head = new_node

Adding any additional nodes is then handled by the code in the if statement:

if self.head:
    current_node = self.head
    while current_node.next:
        current_node = current_node.next
    current_node.next = new_node

The following happens here: The linked list is traversed to determine the end. When the end has been reached, a new node is added:

current_node.next = new_node

Now let’s get to the method traversal(). It is used to run through the linked list and output all existing elements. This method is similar to push_node(), since the linked list must also be run through there:

def traversal(self):
    current_node = self.head
    while current_node:
        print(current_node.value)
        current_node = current_node.next

With that all methods are implemented and we can create a new linked list:

my_linked_list = LinkedList()

Then we can add nodes:

my_linked_list.push_node(24)
my_linked_list.push_node(7)
my_linked_list.push_node(30)
my_linked_list.push_node(33)

If this linked list is now run through, we get the following output:

my_linked_list.traversal()
24
7
30
33

You can also check if the linked list contains nodes:

print(my_linked_list.is_empty())
False

The implementation shown here is only a suggestion. It could also be implemented differently, and so if you search the internet you will find some other examples. Also, more functionality could be implemented, such as removing a node.