Linked Lists in Python

Introduction

Like an array, a linked list is a linear data structure. A linear data structure is one where its elements are arranged sequentially in order. Linked Lists are dynamically expanding and contracting forms of data structure implementations in various programming languages such as ‘vectors’ in C++, ‘Lists’ in Java and Python etc., are made.

Generally, people use Linked Lists heavily for storing and structuring data when there is a need to use a contiguous memory block to store references to their data. Linked lists hold references as part of their elements. It forms the basis of more complex structures like hash tables and trees. 

Linked lists differ from an array in the way that it stores data in memory. Unlike a collection, the elements of a linked list don’t need to be next to each other.

 

An array has a contiguous block of memory because its size must be determined at compile-time, i.e. before the program runs. It cannot grow and shrink freely when the program is running. In formal terms, an array is a static data structure.

On the other hand, the size of a linked list does not have to be predetermined. It can grow and shrink freely. New memory can be added to it at runtime, i.e. when the program is running. It makes the linked list a dynamic data structure.

Before moving on to more depth on the operations, structures, uses and types of linked lists, let us understand the essential elements of linked lists in python and the parts that it comprises which we require for implementing linked lists in python.

Structuring Linked Lists in Python

Linked lists are a collection of elements called ‘nodes’ where each node element has the following two different properties:

1. Data contains the value which we will store in the node.

2. Next (or often also know as Link) contains a reference to the next node on the list.

A node consists of two parts: one part holds the data, and the other holds a pointer/reference to the next node. 

These nodes in a linked list connect each other sequentially with pointers/references. It forms a chain of nodes, which is what a linked list is all about. 

A linked list is a collection of various nodes. Here, The first node is called the head, and it’s used as the starting point for any iteration through the list. In comparison, The last node must have its following reference pointing to None to determine the end of the list.

Meanwhile, the last node of a linked list is called a tail node. A tail node is particular in the sense that it points to nothing. In some programming languages, this can be interpreted as pointing/referring to None.

Above, for example, is a drawing of a linked list containing the integers 1, 3, and 5. Each rectangle is a Node, and each arrow is a pointer to the next Node. The pointer’s value in the Node containing 5 is None (Python’s equivalent of a null pointer) because there are no more nodes for it to point. The first Node in the Linked List is commonly referred to as the “head,” while the last is the “tail.”

Implementing Linked Lists in Python 

1. Creating Linked List: 

            First of all, let’s create a class to represent our linked list. The only data you need to store in a linked list is starting from the list (i.e. the head of the list). Next, try to create another class to represent each node of the linked list:

Python Code:

class LinkedList:
    def __init__(self):
        self.head = None

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

In the class definition above, you can see the two main elements of every single node: data and next. You can also add a  ‘__repr__’ method to both classes to have a more helpful representation of the objects:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __repr__(self):
        return self.data

class LinkedList:
    def __init__(self):
        self.head = None

    def __repr__(self):
        node = self.head
        nodes = []
        while node is not None:
            nodes.append(node.data)
            node = node.next
        nodes.append("None")
        return " -> ".join(nodes)

Now let’s take a look at an example of using the above classes to create a linked list with three nodes quickly:

>>> llist = LinkedList()
>>> llist
output:
None

>>> first_node = Node("a")
>>> llist.head = first_node
>>> llist
output:
a -> None

>>> second_node = Node("b")
>>> third_node = Node("c")
>>> first_node.next = second_node
>>> second_node.next = third_node
>>> llist
output:
a -> b -> c -> None

By defining a node’s data and following values, you can create using a linked list quickly. The LinkedList and Node classes are starting points for our implementation. From nowhere on, it’s all about increasing its functionality.

Here’s a slight change to linked list’s ‘__init__()’ that allows you to create linked lists with some data quickly:

def __init__(self, nodes=None):
    self.head = None
    if nodes is not None:
        data=nodes.pop(0)
        node = Node(data)
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next

The modification above, creating linked lists to use in the examples below that will be much faster.

2. Traversing Linked Lists: 

One of the most frequent operations that you will do with linked lists is to traverse them. Traversing means going through every node, starting with the head of the linked list and ending on the node with the next value as None.

Traversing is just a fancier way to quote iterating. So, with that, create an ‘__iter__’ to add the same behaviour to linked lists that you would expect from normal lists:

def __iter__(self):
    node = self.head
    while node is not None:
        yield node
        node = node.next

The above method goes through the list and yields every single node. The most significant thing to remember about the ‘__iter__’ is that you need to validate that the current node is None constantly. When the condition is True, it means you’ve reached the end of the linked list.

After yielding current node, you want to move to next node on our list. That’s why you add the following node = node.next. Here’s an example of following a traversing in a random list and printing each node:

>>> llist = LinkedList(["a", "b", "c", "d", "e"])
>>> llist
a -> b -> c -> d -> e -> None

>>> for node in llist:
...    print(node)
a
b
c
d
e

3. Inserting a new node in Linked List:

There are various ways to insert new nodes into a linked list, each with implementations and levels of complexity, which is why you’ll see them split into specific methods, i.e. for inserting at the beginning, end, or in-between nodes in a list.

Inserting at Beginning:

Inserting new nodes at the beginning of a list is probably one of the most straightforward insertions since you don’t need to traverse the whole list to do this. It’s all about creating new nodes and then pointing the head of the linked list to it.

Let’s have a look at the following implementation of the ‘add_first()’ method for this class here ‘LinkedList’:

def add_first(self, node):
    node.next = self.head
    self.head = node

In the example above, you’re setting self.head as the following reference to the new node so that the new node points the old self.head. After which, you need to state that the new head of the list is now the node inserted.

Here’s how it now behaves with a sample list:

>>> llist = LinkedList()
>>> llist
output:
None

>>> llist.add_first(Node("b"))
>>> llist
output:
b -> None

>>> llist.add_first(Node("a"))
>>> llist
output:
a -> b -> None

You can see here, the ‘add_first()’ method always adds the node to the head of the list, even when the list was empty before.

Inserting at the End:

You insert a new node at the end of the list; it forces you to traverse the whole linked list first and add the new node when you reach the end. Here, You can’t just append to the end as you would have with a typical list because, in linked lists, you don’t know which node is the last.

Here’s an example implementation of the ‘add_last’ function for inserting a new node at the end of linked list:

def add_last(self, node):
    if self.head is None:
        self.head = node
        return
    for current_node in self:
        pass
    current_node.next = node

Here, you want to traverse the whole list until you have reached the end (that is, until the for loop raises a ‘StopIteration’ Exception). Next, you want to set the ‘current_node’ as the last node of the list. Finally,  add the new node as the ‘next’ value of the current_node.

Here’s an example of ‘add_last()’ in action:

>>> llist = LinkedList(["a", "b", "c", "d"])
>>> llist
output:
a -> b -> c -> d -> None

>>> llist.add_last(Node("e"))
>>> llist
output:
a -> b -> c -> d -> e -> None

>>> llist.add_last(Node("f"))
>>> llist
output:
a -> b -> c -> d -> e -> f -> None

You create a list with four values (a, b, c, and d). Then, when you add new nodes using ‘add_last()’, you can see that nodes are always appended in the end of the list.

Insertions between any two nodes in the list:

Insertions between two nodes add another layer of complexity to the linked list’s already complex insertions as there are two different approaches that you can use:

1. Inserting after an existing node
2. Inserting before a current node

It might seem weird to split them into two methods, but linked lists behave differently than standard lists, and you need a different implementation for each case.

Here’s a method that adds the node after an existing node with specific data values:

def add_after(self, target_node_data, new_node):
    if self.head is None:
        raise Exception("List is empty")

    for node in self:
        if node.data == target_node_data:
            new_node.next = node.next
            node.next = new_node
            return

    raise Exception("Node with data '%s' not found" % target_node_data)

In the code above, you’re traversing the linked list looking for the node with the data indicating where you want the new node to be inserted. When you find the node you’re looking for, you’ll insert the new node immediately after it and rewire the following reference to maintain the consistency of the list.

The only exceptions here are if the list is empty, making it impossible to insert new node from an existing node, or if the list doesn’t contain the value you’re searching for. Here are a few examples of how ‘add_after()’ behaves:

>>> llist = LinkedList()
>>> llist.add_after("a", Node("b"))
output:
Exception: List is empty

>>> llist = LinkedList(["a", "b", "c", "d"])
>>> llist
output:
a -> b -> c -> d -> None

>>> llist.add_after("c", Node("cc"))
>>> llist
output:
a -> b -> c -> cc -> d -> None

>>> llist.add_after("f", Node("g"))
output:
Exception: Node with data 'if not found

You are trying to use ‘add_after()’ on an empty list, resulting in an exception. The same happens when you try to add after a nonexistent node. Everything else works as expected.

Now, if you want to implement ‘add_before()’, then it will look something like this:

def add_before(self, target_node_data, new_node):
   
    if self.head is None:
        raise Exception("List is empty")
   
    if self.head.data == target_node_data:
        return self.add_first(new_node)
       
    prev_node = self.head
    for node in self:
        if node.data == target_node_data:
            prev_node.next = new_node
            new_node.next = node
            return
           
        prev_node = node
       
    raise Exception("Node with data '%s' not found" % target_node_data)

There are a few things to keep in mind while implementing the above. First, as with ‘add_after()’, you want to make sure to raise an exception if the linked list is empty (line 2) or the node you’re looking for is not present (line 16).

Second, if you’re trying to add a new node before the head of the list (line 5), you can reuse ‘add_first()’ because the node you’re inserting will be the new head of the list.

Finally, for any other case (line 9), you should keep track of the last-checked node using the prev_node variable. Then, when you find the target node, you can use that prev_node variable to rewire the following values.

Once again, an example is worth a thousand words:

>>> llist = LinkedList()
>>> llist.add_before("a", Node("a"))
output:
Exception: List is empty

>>> llist = LinkedList(["b", "c"])
>>> llist
output:
b -> c -> None

>>> llist.add_before("b", Node("a"))
>>> llist
output:
a -> b -> c -> None

>>> llist.add_before("b", Node("aa"))
>>> llist.add_before("c", Node("bb"))
>>> llist
output:
a -> aa -> b -> bb -> c -> None

>>> llist.add_before("n", Node("m"))
output:
Exception: Node with data 'n' not found

With ‘add_before()’, you now have all the methods you need to insert nodes anywhere you’d like in your list.

4. Removing a node from a Linked List:

To remove a node from a linked list, you first need to traverse the list until you find the node you want to remove. Once you find the target, you want to connect its previous and next nodes. This re-linking is what eliminates the target node from the list.

That means you need to keep track of the previous node as you traverse the list. Have a look at an example implementation:

def remove_node(self, target_node_data):
    if self.head is None:
        raise Exception("List is empty")
   
    if self.head.data == target_node_data:
        self.head = self.head.next
        return
   
    previous_node = self.head
    for node in self:
        if node.data == target_node_data:
            previous_node.next = node.next
            return
        previous_node = node
       
    raise Exception("Node with data '%s' not found" % target_node_data)

In the above code, you first check that your list is not empty (line 2). If it is, then you raise an exception. After that, you check if the node to be removed is the current head of the list (line 5). If it is, then you want the next node in the list to become the new head.

If none of the above happens, start traversing the list to remove the node (line 10). If you find it, you need to update its previous node to its next node, automatically removing the found node from the list. Finally, you raise an exception if you traverse the whole list without finding the node removed (line 16).

Notice how in the above code, you use previous_node to keep track of the, well, previous node. Doing so ensures that the process will be more straightforward when you find the right node to be deleted.

Here’s an example using a list:

>>> llist = LinkedList()
>>> llist.remove_node("a")
output:
Exception: List is empty

>>> llist = LinkedList(["a", "b", "c", "d", "e"])
>>> llist
output:
a -> b -> c -> d -> e -> None

>>> llist.remove_node("a")
>>> llist
output:
b -> c -> d -> e -> None

>>> llist.remove_node("e")
>>> llist
output:
b -> c -> d -> None

>>> llist.remove_node("c")
>>> llist
output:
b -> d -> None

>>> llist.remove_node("a")
Exception: Node with data 'a' not found.

That’s it! Voila, You now know how to implement a linked list and all primary methods for traversing, inserting, and removing nodes.

Approaching Doubly and Circularly implemented Linked Lists in Python

Looking at the linked list above, how can we improve it? What are its limitations?

Until now, you’ve been learning about a specific type of linked list called singly-linked lists. But more types of linked lists can be used for slightly different purposes.

Doubly linked lists are different from singly linked lists in that they have two references:

• The previous field references the last node.
• The following field references the next node.

The result looks like this:

If you wanted to implement the above idea, then you could make some of the following changes to your existing Node class to include a previous field:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.previous = None

This kind of implementation would allow you to traverse a list in both directions instead of only traversing using next. You could now use next to go forward and previous to go backward.

Circular linked lists are lists in which the last node now points back to the head of a list instead of pointing to None. It is what makes them circular. Circular linked lists have quite a few and compelling use cases, for instance:

• Going around every player’s turn in a multiplayer game that is
• Managing the application life cycle of a given operating system
• Implementing a Fibonacci heap.

One of the advantages of using circular linked lists is that you can traverse the whole list starting from any node. Since now, the last node points to the head of the list, which you need to make sure that you stop traversing as soon as you reach the starting point. Otherwise, you’ll end up in infinite loops.

In terms of implementations, circular linked lists are very similar to singly-linked lists. The only difference that we see here is that you can define the starting point while you traverse the list:

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def traverse(self, startingPoint = None):
        if startingPoint is None:
            startingPoint = self.head
        node = startingPoint
        while node is not None and node.next != startingPoint:
            yield node
            node = node.next
        yield node

    def print_list(self, startingPoint = None):
        nodes = []
        for node in self.traverse(startingPoint):
            nodes.append(str(node))
        print(" -> ".join(nodes))

It is an advanced variation of a linked list where the tail node points to the head node instead of None.

Applications, Performance, and Final Thoughts

Linked lists serve a variety of purposes in the real world. One can also use it to implement (spoiler alert!) queues or stacks and graphs. They’re also helpful for more complex tasks, such as lifecycle management for an operating system application.

Some of the standard data structures you may have come across like heaps, stacks, trees and hash tables. Each of them has a different implementation, and they perform well in different scenarios but have an internal implementation using linked lists in some way or the other.

Because of how insertion and retrieval of elements occur from the edges of queues and stacks, linked lists are often one of the most convenient ways to implement these data structures. That is why in terms of both speed and memory, often implementing graphs using adjacency lists is an efficient method in comparison with, for example, an adjacency matrix. That’s why linked lists are so helpful for graph implementation as well.

Now, something you need to know about Python lists is inserting or removing elements that are not present at the end of the index require some part shifting in the background (beforehand), making the operations more complex in terms of time spent.

With all this, even though while inserting elements at the end of a list using .append() or .insert(), it will have constant time, O(1), when you try inserting an element closer to or at the beginning of a list, then the average time complexity will grow by order of the size of the list: O(n).

On the other hand, linked lists are much more straightforward when it comes to the insertion and deletion of elements from the beginning or end of a list, where their time complexity is always (mostly) constant: O(1).

As a result, linked lists have a performance advantage over usual lists while implementing a queue (FIFO). The elements are continuously inserted and removed from the beginning of the list. But they perform similarly in a list while implementing a stack (LIFO), where the elements are inserted and removed from the end of the list.

Frequently Asked Questions

Key Takeaways

This blog  has attempted to give a detailed explanation about linked lists in python and other valuable topics such as:

1. What linked lists in python are when you should use them.
2. We also saw ways to understand how to implement your own linked list in python and node classes, plus its appropriate methods.
3. We also got to know the other types of linked lists and how one can utilise them.
4. Other data structures that use linked lists, their different applications and the performance gains over other alternatives they give.

If you intend to learn to program, you might want to check out the courses. Also, if you are interested in practising different coding problems asked in Amazon, Google, Microsoft or other product based companies, you should check out our CodeStudio platform. Guided Paths are another attraction on our platform!

By: Dhruv Sharma