In this blog post I will discuss one of the basic types of linked lists i.e. singly-linked lists. This is one of the important and simple data structure types. Furthermore, this is a data structure that can be defined by the user / analyst. Besides from this linked lists are mainly known for facilitating efficient insertion and deletion operations.

What is a linked list?

A linked list is a collection of multiple nodes containing data and the addresses of their respective successor or predecessor nodes. These nodes can store any type of data – integers, floats, strings, or any elements of any other data type.

Due to certain drawbacks of arrays, such as fixed memory and inefficient (“expensive”) insertion and deletion operations, linked lists were introduced. They represent an alterantive data structure with much faster insertion and deletion operations and with dynamic memory.

Linked lists store data at random locations in our computer memory. The address of a particular node is stored in the immediate neighbour node, i.e. in the immediate successor and predecessor. There are various types of linked lists, and the fact which neighbour address is stored in which neighbour node depends on the linked-list type. I will explain this now, using a singly-linked list for illustration purposes.

Singly linked lists

As explained above, a linked list is simply a collection of linked nodes. In a singly linked list, a node contains data and the address/reference ID of the next node as given in Figure 1.

The first node of a linked list is called the head. Since there doesn’t exist any node before the first node, I would create a head pointer to address the first node.

The last node of a linked list is called the tail node. There’s no node after the tail node to refer to, hence it points to none.

Implementing a singly linked list from scratch in Python

I will now implement a singly-linked list in Python, from scratch. For this I need to define a data type for the nodes, and one for the linked list itself. In Python I can define a class. Class definitions allow me to implement custom data types.

Implementing custom node class in Python

First of all, I have to create a class for creating a node.

class Node:
      # constructor for Node class
      def __init__(self, data):
            self.data = data
            self.ref = None

Initially, a newly created node will not be pointing to any other node, i.e. it will point to “None”. Besides from this, the node will, upon creation, contain the data to be stored.

Implementing custom linked-list class in Python

After creating a node, I need a linked list structure. A linked list will connect all the nodes I create.

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

As shown in the code above the head is pointing to “None”. This means: The linked list is empty. That is because here I just initialize a linked list with a blank head.

Printing a linked list

To print a linked list I have to traverse through every node.

    def print_linkedlist(self):
        if self.head is None:
            print("The linked list is empty.")
        
        else:
            n = self.head
            while n is not None:
                print(n.data, end=" ---> ")
                n = n.ref

Here, I am initializing the printing procedure with “self.head”.

As I already know that the last node addresses None I will loop through each node unless the reference of the current node is None and print the values contained in each of these nodes.

Adding elements at the beginning of singly linked list

There are multiple ways of adding and deleting elements to and from a linked list in Python. I will explain them one by one.

def add_beginning(self, data):
        new_node = Node(data)
        new_node.ref = self.head
        self.head = new_node

First of all, I will create a new node containing the data I want to store.

I know that “self.head” contains the address/reference ID of the first node. I want to add this new node at the beginning. Hence I will move this reference ID of the first node to the new nodes reference ID section.

Then I will refer to the first node with the head pointer.

Adding elements to the end of singly linked list

To add an element at the end of a singly linked list, I must check whether the linked list is empty or not.

    def add_end(self, data):
        new_node = Node(data)
        if self.head is None:
            print("Linked list is empty. Initiating the linked list with given data")
            self.head = new_node
        else:
            n = self.head
            while n.ref is not None:
                n = n.ref
            n.ref = new_node

As shown in the code above the algorithm implements that if “self.head” is None (Empty linked list), the node is directly added. If the head does not point at None the algorithm proceeds traversing through the linked list until it finds “n.ref = None” which indicates the last node.

Once I find the last node I would change the reference of the last node to the new node as shown in Figure 6, adding a node at the end of the linked list. Since the new node by default contains None as a reference value I do not need to specify this reference explicitly.

Delete object from the beginning and end of the singly linked list

Now, using the same methods for list traversal as mentioned above, I can implement element deletion from list beginning and list end.

    def delete_beginning(self):
        if self.head is None:
            print("Linked list is empty. Cannot delete the elements")
        else:
            self.head = self.head.ref

    def delete_end(self):
        if self.head is None:
            print("Linked list is empty, cannot delete the item.")
        else:
            n = self.head
            while n.ref.ref is not None: #Refrence of second last node will be last node which refers to None. Hence, n.ref.ref
                n = n.ref
            n.ref = None

Creating and printing linked lists in Python

As demonstrated in the code above I can create a basic singly linked list and print it using the print_linkedlist function.

if __name__ == "__main__":
    l1 = LinekdList()

    l1.add_beginning(57)
    l1.add_beginning(25)
    l1.add_beginning(103)
    l1.add_end(83)
    l1.add_end(16)
    l1.print_linkedlist()

O/p:

103 ---> 25 ---> 57 ---> 83 ---> 16 ---> 

I will now introduce additional methods for adding and removing nodes to or from a singly linked list. I will look at adding and removing nodes at or from the beginning, the end or at a random position in the singly linked list. Lastly, I will now also look at how to delete nodes by value.

Adding nodes to random positions in a singly-linked Python list

Adding nodes after a node containing a specific value

To add data after a specific existing data point, I will use two parameters to add data before the existing one. The “data” being the first parameter will be the data we want to add. Parameter “x” will be used as existing data after which I want to add “data”.

As discussed previously in this post, I can traverse through the linked list by initializing variable n with “self.head”.

First of all, I will check whether the linked list is empty. I know that when “self.head” points to None it means that the linked list is empty.

If it is not empty, I will move forward to the next node by changing the value of n to “n.ref”. This will continue until the node reference points to None i.e. the last node of the linked list.

While traversing I will check whether the value “x” is present in any node. If it does exist, I will add the reference of this node to the new node, and then I will change the reference of this node to the new node. Else, the code will just return a message that the data doesn’t exist in the list.

    def add_after(self, data, x): #"data" is the data we want to add after existing data "x"
        n = self.head
        while n is not None:
            if x == n.data:
                break
            n = n.ref
        if n is None:
            print("Item " + str(x) + " is not present in the list.")
        else:
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

Adding nodes before a node containing a specific value

To add a node before an existing node I will use the similar traversal method as mentioned above. But, there will be a small change.

In this case, I will use “n.ref.data” for traversal to check if the data in the next node matches “x”. I do so to avoid going one step backward which would be a difficult task in the singly linked list.

Once I find that perfect match I will use the method given above to add the node before the node containing data “x”.

    def add_before(self, data, x):
        if self.head is None:
            print("Linked List is empty!")
            return
        if self.head.data == x:
            new_node = Node(data)
            new_node.ref = self.head
            self.head = new_node
            return
        n = self.head
        while n.ref is not None :
            if n.ref.data == x:
                new_node = Node(data)
                new_node.ref = n.ref
                n.ref = new_node
                return
            n = n.ref
        print("The data " + str(x) + " is not present in the list.")

Also, as demonstrated in above coding example, I have to consider one edge condition, i.e. adding a node before the head node.

Deleting nodes containing specific values

I have built the deletion function, using the same techniques given in the first parts of this post. See the coding example below:

    def delete__by_value(self, x):
        if self.head is None:
            print("Linked list is empty, cannot delete the item.")
        if x==self.head.data:
            self.head = self.head.ref
        n = self.head
        while n.ref is not None:
            if x==n.ref.data:
                break
            n = n.ref
        if n.ref is None:
            print("The item is not present in the list.")
        else:
            n.ref = n.ref.ref

For more information, feel free to contact us through the contact section. Or leave a comment below.

Tanmay Sawant

Civil engineer interested in automation in core subjects such as civil, mechanical and electrical, using IT skills comprising cloud computing, devops, programming languages and databases along with the technical skills gained while working as a civil engineer since past 3 years.