If you are learning data structures, a Linked List is one of the data structures you should know, albeit not so common, linked lists are similar to Lists (or arrays); you probably never heard or used them until now, but in the right context they prove to be useful.

In this article, you will learn:

• What linked lists are.
• Performance of linked lists.
• Types of linked lists.
• How to Implement your own linked list.

What are linked lists?

A linked list is a sequence of data elements, which are connected together via links. Each element (node) in a linked list contains a connection to another data element in form of a pointer.

You should know:

That every element in a linked list is called a Node, and every node contains a data (value to be stored) and next (reference to the next node) fields.

A linked list therefore is a collection of nodes, with the last node pointing to None

Performance of linked lists.

In a linked list, the time complexity for the operations is given as:

• Indexing - O(n)
• Insertion - O(1)
• Deletion - O(1)
• Search - O(n)

Space complexity however is O(n).

Types of linked lists.

There are 3 main types of linked lists;

• Singly-linked lists: Each node consists of only one pointer to the next (which we are learning)
• Doubly-linked lists: Each node contains two pointers, a pointer to the next node and a pointer to the previous node.

• Circular-linked lists: In a circular linked list the last node points to the first node or any other node before it thereby forming a loop

Implementing a linked list in Python

This comes in 2 parts, creating our list Node, and the Linked List itself. So, first thing first, create a class to represent each Node of the linked list

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

As you can see each node contains just 2 fields, the data, and next.

Next, create a class to represent your linked list :

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

Putting it all together

Let's update each of our classes with a repr function so our new code looks like this :

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

    def __repr__(self):
        return self.data

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

    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)

The code above would rightly allow us to create a linked list, notice that in the LinkedList init function if the node is not passed we initialized it to None.

my_list = LinkedList()
firstNode = Node("1")
my_list.head = firstNode
secondNode = Node("2")
firstNode.next = secondNode
print(my_list)

>>> 1 -> 2 -> None

Linked Lists Methods

To help us use our linked lists even more efficiently, we would implement some methods to:

• Traverse a linked list.
• Insert a new node at the beginning.
• Insert a new node at the end.

Traverse a linked list

Traversing a linked list means iterating through the list, and we add the iter function to allow us to replicate the same behavior from regular lists (arrays)

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

The code above goes through the list if it does not equal to None and yields every node before re-assigning the node to the next node if it exists.

Insert node at the beginning

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

In the above code, you're setting the next value to the present head value before re-assigning head to the new node

Insert node at the end

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

While inserting at the end is similar to inserting at the beginning, first, you want to traverse the whole list until you reach the end. Next, you want to set current as the last node on the list. Finally, you want to add the new node as the next value of that current.

Our final code containing our methods should look like this

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

    def __repr__(self):
        return self.data

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

    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)

    # Traverse a Linked List
    def __iter__(self):
        node = self.head
        while node is not None:
            yield node
            node = node.next

    # Insert a new node at the beginning
    def add_at_beginning(self, node):
        node.next = self.head
        self.head = node

    # Insert a new node at the end
    def add_at_end(self, node):
        if self.head is None:
            self.head = node
            return
        for current_node in self:
            pass
        current_node.next = node

To wrap up a final example, have a look at how it works:

my_list = LinkedList()
firstNode = Node("1")
secondNode = Node("2")
my_list .head = firstNode
firstNode.next = secondNode
my_list.add_at_beginning(Node("3"))
my_list.add_at_end(Node("4"))
print(my_list)

>>>  3 -> 1 -> 2 -> 4 -> None

Conclusion

In this article, you learned quite a few things, The most important are:

• What linked lists are
• What the other types of linked lists are
• Time and Space Complexities of a linked list
• How to implement your own linked list and node classes, plus relevant methods

I hope you enjoyed reading it as much as I enjoyed writing it :)

Learn more about me