Everything About Linked List Data Structure in Python: Intermediate Guide

This article was first published on PyShark , and kindly contributed to python-bloggers. (You can report issue about the content on this page here)
Want to share your content on python-bloggers? click here.

In this article we will focus on a complete walk through of a Python linked list data structure.

Table of Contents


What is a linked list

A linked list is a data structure that consists of nodes, where each nodes contains two fields:

  1. Value
  2. Pointer (reference link) to the next node

It is a collection of nodes which make a sequence using the pointers, where the first node of the linked list is called the head node, and the last node has a reference link to NULL.

What is a linked list

How to create a linked list in Python

We already know that a linked list is a sequence made from nodes.

The first step to creating a linked list is to create a structure of a node (as its own class).

When initialized, a node should take some data to use as the value, as well as have a default pointer to next node set to None, which will be changed as we add more nodes together to form a sequence.

class Node:

    
    def __init__(self, data):
        self.data = data
        self.next_node = None

To test the code, let’s create a node that will have a value equal to 5, and print out the value and the pointer to next node:

first_node = Node(5)

print(first_node.data)
print(first_node.next_node)

And you should get:

5
None

As we expected, the values stored is 5 and reference link to next node is None.


Let’s go ahead and create a few more individual nodes:

second_node = Node(7)
third_node = Node(15)

At this point we have three nodes which are not connected to each other: first_node, second_node, third_node.


The next step is to create a structure for a linked list (as its own class).

When initialized, a linked list should only have the head node set to NULL, in order to start an empty linked list:

class LinkedList:

    
    def __init__(self):
        self.head = None

To start adding nodes to a linked list we want the first_node we created to be the head node of the linked list:

llist = LinkedList()

llist.head = first_node

This will create a linked list with one node (which will be the head node).

Recall that each node has a reference link set to NULL. In order to create a sequence of nodes, we will set each reference link to point to the next node:

llist.head.next_node = second_node

second_node.next_node = third_node

And now we have successfully created a linked list with three nodes which should look like this:

How to create a linked list

In this section we have been adding nodes to the linked list rather manual than programmatically. In the next sections we will explore to to insert nodes at the end, and the beginning, and at a specific position of the linked list.


How to traverse a linked list in Python

In the previous section we created the linked list llist and now we would like to traverse the linked list and print out values of each node.

Recall that the initial construction of linked list is given by:

class LinkedList:

    
    def __init__(self):
        self.head = None

A singly linked list can only be traversed in forward direction.

The logic is fairly simple: we will start at the head node, print its current value, and move to the next node (given that the reference link is not NULL).

We will continue moving to the next node as long as the node has data in it.

How to traverse a linked list

In this section we will implement a method print_llist() for traversing a linked list and printing values of each node for the LinkedList() class.

def print_llist(self):
    current_node = self.head
    while current_node is not None:
        print(current_node.data)
        current_node = current_node.next_node

It will be added as a method of the LinkedList() class:

class Node:

    
    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList:

    
    def __init__(self):
        self.head = None

        
    def print_llist(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next_node

Let’s test create the same list as in the previous section and print out the values of each node:

llist = LinkedList()

llist.head = first_node
llist.head.next_node = second_node
second_node.next_node = third_node

llist.print_llist()

And you should get:

5
7
15

How to insert a node at the end of a linked list in Python

In the one of the previous sections we showed an example of how to create a linked list in Python.

The approach we used was rather manual then programmatic because we had to manually link the nodes together and add reference links to the next node.

In this section we will implement a method insert_at_end() for inserting nodes at the end of a linked list (basically appending new nodes) for the LinkedList() class.

Let’s reuse the linked list we have built in the previous section:

class Node:

    
    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList:

    
    def __init__(self):
        self.head = None

        
    def print_llist(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next_node

In order to add nodes at the end of the linked list in Python, we should follow a logic that is similar to traversing the linked list in Python.

We start at the head node:

  • if the head node exists, then we move to the next node
  • if the head node is NULL, then the node we want to add becomes the head node

Assuming that the head node exists, we move to the next node (given that the reference link is not NULL).

We will continue moving to the next node as long as the reference link is pointing to another node that has a value and it’s not the last node (with reference link NULL).

Once we reach the last node, we will insert the new node right after it, and have its reference link as NULL.

How to insert a node at the end of a linked list

In this section we will implement a method insert_at_end() for inserting nodes at the end of a linked list for the LinkedList() class.

def insert_at_end(self, data):
    new_node = Node(data)

    if self.head is None:
        self.head = new_node
        return

    last_node = self.head
    while last_node.next_node is not None:
        last_node = last_node.next_node

    last_node.next_node = new_node

It will be added as a method of the LinkedList() class:

class Node:

    
    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList:
    
    
    def __init__(self):
        self.head = None
        
    
    def insert_at_end(self, data):
        new_node = Node(data)
        
        if self.head is None:
            self.head = new_node
            return
        
        last_node = self.head
        while last_node.next_node is not None:
            last_node = last_node.next_node
            
        last_node.next_node = new_node
        
    
    def print_llist(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next_node

Now let’s try to create the same list as in the second section of this tutorial and see if we get the same results:

llist = LinkedList()

llist.insert_at_end(5)
llist.insert_at_end(7)
llist.insert_at_end(15)

llist.print_llist()

And you should get:

5
7
15

which is exactly the same as when we created the linked list manually.

How to insert a node at the end of a linked list in Python

Using the insert_at_end() method we can add more nodes at the end of a linked list in Python.


How to insert a node at the beginning of a linked list in Python

In the previous section we implemented a method to insert nodes at the end of a linked list.

But what if we need to add a node in the beginning of a linked list? That’s what we are going to cover in this section!

Inserting a node in the beginning of a linked list is much simpler from the logic and code perspective.

The very first node of a linked list is a head node, and if we need to insert a node before it, we should simply have a node that has a reference link to the head node (of course, if there are no nodes in the linked list, then the new node becomes the head node).

How to insert a node at the beginning of a linked list

In this section we will implement a method insert_at_beginning() for inserting nodes at the beginning of a linked list for the LinkedList() class.

def insert_at_beginning(self, data):
    new_node = Node(data)
    
    if self.head is None:
        self.head = new_node
        return
    
    new_node.next_node = self.head
    self.head = new_node

It will be added as a method of the LinkedList() class:

class Node:
    

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList:
    
    
    def __init__(self):
        self.head = None
        
    
    def insert_at_end(self, data):
        new_node = Node(data)
        
        if self.head is None:
            self.head = new_node
            return
        
        last_node = self.head
        while last_node.next_node is not None:
            last_node = last_node.next_node
            
        last_node.next_node = new_node
        
        
    def insert_at_beginning(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        new_node.next_node = self.head
        self.head = new_node

    
    def print_llist(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next_node

Now let’s create the same list as in the previous section of this tutorial and and add a node with value “9” at the beginning of the linked list:

llist = LinkedList()

llist.insert_at_end(5)
llist.insert_at_end(7)
llist.insert_at_end(15)

llist.insert_at_beginning(9)

llist.print_llist()

And you should get:

9
5
7
15
How to insert a node at the beginning of a linked list in Python

Using the insert_at_beginning() method we can add more nodes at the beginning of a linked list in Python.


How to insert a node after a given node of a linked list in Python

So far in this tutorial we discussed how to add elements at the beginning and at the end of a linked list in Python.

In this section we will explore how to add elements after a given node of a linked list in Python.

When inserting a node after a given node, the first step is to find the previous node in the linked list.

In order to find the previous node, we will traverse the linked list from its head node, all the way until we find the previous node.

Once we find the previous node, we will change the reference link of a new node from NULL to the reference link of the previous node, and then we will change the reference link of the previous node to the new node.

How to insert a node after a given node of a linked list

In this section we will implement a method insert_after_node() for inserting nodes after a given node of a linked list for the LinkedList() class.

def insert_after_node(self, data, previous_node):
    new_node = Node(data)

    current_node = self.head
    while current_node.data != previous_node:
        current_node = current_node.next_node

    new_node.next_node = current_node.next_node
    currentnode.next_node = new_node

It will be added as a method of the LinkedList() class:

class Node:
    

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList:
    
    
    def __init__(self):
        self.head = None
        
    
    def insert_at_end(self, data):
        new_node = Node(data)
        
        if self.head is None:
            self.head = new_node
            return
        
        last_node = self.head
        while last_node.next_node is not None:
            last_node = last_node.next_node
            
        last_node.next_node = new_node
        
        
    def insert_at_beginning(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = newnode
            return

        new_node.next_node = self.head
        self.head = new_node


    def insert_after_node(self, data, previous_node):
        new_node = Node(data)
        
        current_node = self.head
        while current_node.data != previous_node:
            current_node = current_node.next_node
        
        new_node.next_node = current_node.next_node
        current_node.next_node = new_node
        
        
    def print_llist(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next_node

Now let’s create the same list as in the previous section of this tutorial and add a node with value “10” after the node with value “7” the linked list:

llist = LinkedList()

llist.insert_at_end(5)
llist.insert_at_end(7)
llist.insert_at_end(15)
llist.insert_at_beginning(9)

llist.insert_after_node(10,7)

llist.print_llist()

And you should get:

9
5
7
10
15
How to insert a node after a given node of a linked list in Python

Using the insert_after_node() method we can add a node after a given node of a linked list in Python.


How to search a node in a linked list in Python

We already know how to create a linked list, and let’s say we created a linked list in Python.

Now we would like to search a node in this linked list to check whether it exists.

The logic is fairly simple: we will start at the head node and start moving to the next node (node after node and given that the reference link is not NULL).

We will compare the values of each node with the value we are searching, and print “Node found” as soon as the node is found, or print “Node not found” if we traversed the linked list and didn’t find the value we are searching.

How to search a node in a linked list

In this section we will implement a method search_node() for searching a node in the linked list for the LinkedList() class.

def search_node(self, data):
    current_node = self.head
    while current_node is not None:
        if current_node.data == data:
            print('Node found')
            return

        current_node = current_node.next_node

    print('Node not found')

It will be added as a method of the LinkedList() class:

class Node:
    

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList:
    
    
    def __init__(self):
        self.head = None
        
    
    def insert_at_end(self, data):
        new_node = Node(data)
        
        if self.head is None:
            self.head = new_node
            return
        
        last_node = self.head
        while last_node.next_node is not None:
            last_node = last_node.next_node
            
        last_node.next_node = new_node
        
        
    def insert_at_beginning(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = newnode
            return

        new_node.next_node = self.head
        self.head = new_node


    def insert_after_node(self, data, previous_node):
        new_node = Node(data)
        
        current_node = self.head
        while current_node.data != previous_node:
            current_node = current_node.next_node
        
        new_node.next_node = current_node.next_node
        current_node.next_node = new_node
    
    
    def search_node(self, data):
        current_node = self.head
        while current_node is not None:
            if current_node.data == data:
                print('Node found')
                return

            current_node = current_node.next_node
        
        print('Node not found')
        
        
    def print_llist(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next_node

Now let’s create the same list as in the previous section of this tutorial and search for the node with value “15”:

llist = LinkedList()

llist.insert_at_end(5)
llist.insert_at_end(7)
llist.insert_at_end(15)
llist.insert_at_beginning(9)
llist.insert_after_node(10,7)

llist.search_node(15)

And you should get:

Node found
How to search a node in a linked list in Python

Using the search_node() method we can search a node in a linked list in Python.


How to delete a node from a linked list in Python

We already know how to search a node in a linked list in Python.

Now we would like to delete a node from a linked list in Python.

As you can imagine, the process will be similar to traversing a linked list and searching for a given node in a linked list.

How to delete a node in a linked list

The logic is fairly simple: we will start at the head node and check whether it’s the node we would like to remove:

  • If yes, then we will repoint the head node to the next node.
  • If no, then we will use it as current node, and check whether we want to remove the next node (the process continues node after node until we find the node to delete from a linked list).

In this section we will implement a method delete_node() for searching a node in the linked list for the LinkedList() class (this method assumes you are trying to delete a node that exists in a linked list).

def delete_node(self, data):
    current_node = self.head
    
    if self.head.data == data:
        self.head = current_node.next_node
        return
    
    while current_node.next_node.data != data:
        current_node = current_node.next_node
    
    current_node.next_node = current_node.next_node.next_node

It will be added as a method of the LinkedList() class:

class Node:
    

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList:
    
    
    def __init__(self):
        self.head = None
        
    
    def insert_at_end(self, data):
        new_node = Node(data)
        
        if self.head is None:
            self.head = new_node
            return
        
        last_node = self.head
        while last_node.next_node is not None:
            last_node = last_node.next_node
            
        last_node.next_node = new_node
        
        
    def insert_at_beginning(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = newnode
            return

        new_node.next_node = self.head
        self.head = new_node


    def insert_after_node(self, data, previous_node):
        new_node = Node(data)
        
        current_node = self.head
        while current_node.data != previous_node:
            current_node = current_node.next_node
        
        new_node.next_node = current_node.next_node
        current_node.next_node = new_node
    
    
    def search_node(self, data):
        current_node = self.head
        while current_node is not None:
            if current_node.data == data:
                print('Node found')
                return

            current_node = current_node.next_node
        
        print('Node not found')
        
    
    def delete_node(self, data):
        current_node = self.head
        if self.head.data == data:
            self.head = current_node.next_node
            return

        while current_node.next_node.data != data:
            current_node = current_node.next_node

        current_node.next_node = current_node.next_node.next_node
        
        
    def print_llist(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next_node

Now let’s create the same list as in the previous section of this tutorial and delete the node with value “5”:

llist = LinkedList()

llist.insert_at_end(5)
llist.insert_at_end(7)
llist.insert_at_end(15)
llist.insert_at_beginning(9)
llist.insert_after_node(10,7)

llist.delete_node(5)

llist.print_llist()

And you should get:

9
7
10
15
How to delete a node from a linked list in Python

Using the delete_node() method we can delete a node from a linked list in Python.


Conclusion

This article is an introductory walkthrough for linked list data structure in Python and its functionality which is important to learn as they are used in many areas of programming and in machine learning.

Feel free to leave comments below if you have any questions or have suggestions for some edits and check out more of my Data Structures articles.

The post Everything About Linked List Data Structure in Python: Intermediate Guide appeared first on PyShark.

To leave a comment for the author, please follow the link and comment on their blog: PyShark .

Want to share your content on python-bloggers? click here.