Python Linked List

A linked list is a linear data structure referred to as a collection of similar elements linked in a linear order. The basic unit in a linked list is a node. Node is constructed with a data part and a link part. Data part contains the value you wish to store for a node. Address part contains the address of next node in Python linked list.

You can think of linked list as a list of clues for a treasure hunt. Each clue will tell you where you have to go next in search of the treasure. In linked list the address part also called next, tells the program where to find the next node of the liked list.

This node structure of the linked list allows efficient memory management. Unlike an array, contiguous memory is not required to store the elements of a linked list. As and when you need to insert a new node in linked list you can do so by updating the links of nodes. Any node can be deleted by updating pointers again. This gives a dynamic nature to a Linked list.

In this post you will understand how to create a Python linked list using Python classes. So let’s begin.

Declaring Node Class

First we declare a Node class. Node objects will be created whenever a new node is to be added in the linked list.

class Node:
    def __init__(self, data=None, link=None):
        self.data=data
        self.link=link
    def __str__(self):
        return str(self.data)

Declaring Linked List Class

The second class for this program is the LinkedList. In this class the start address is used to store the address of first node of the Python Linked List.

class LinearList:
    def __init__(self, start=None):
        self.start=start

Operations of Python Linked List

Display Node values of the Linked List

This is the traversal operation of linked list. In this method of LinkedList class, a pointer ptr is assigned the address start of first node. The function iterates through linked list using while loop until ptr becomes null indicating that the linked list is traversed to the end.

def printList(self):
        ptr=self.start
        while ptr:
            print(ptr)
            ptr=ptr.link
        print()

Creating three nodes, linking them together and passing the address of first node while creating LinkedList object.

node1=Node('amy')
node2=Node('Bob')
node3=Node('Cathy')
node1.link=node2
node2.link=node3
ll=LinearList(node1)
print('Initially list elements')
ll.printList()
Create Python Linked List

Add a Node at the Beginning

In this method of LinkedList a new node is assigned the value to be added in linked list at the beginning. New node’s link part is updated with start and start is updated with the address of the new node.

 def addBegNode(self, value=None):
        node=Node(value)
        node.link=self.start
        self.start=node
print('After inserting element at beginning')
ll.addBegNode('Alia')
ll.printList()
Insert at Beginning

Add a Node at the End

In this method of LinkedList a new node is assigned the value to be updated at the end in the linked list. The linked list is traversed to reach the last node. In each iteration of while loop Save  stores address of previous node and ptr is updated with address of next node. When this loop terminates new node’s link part is updated with None and the link part of save is updated with address of new node, thus adding it at the end of Python linked list.

 def addEndNode(self, value=None):
        ptr=self.start
        while ptr:
            save=ptr
            ptr=ptr.link
        node=Node(value)
        save.link=node
        node.link=None
print('After inserting element at end')
ll.addEndNode('Zoe')
ll.printList()
Insert at the end

Add a Node Before a Given Node

ptr node is assigned start address. The linked list is traversed to find the node whose data part matches the value before which the new node is to be inserted. In each iteration of while loop save stores address of previous node and ptr is updated with address of next node. The link part of save is updated with address of new node and new node’s link part is updated with ptr thus adding it before the given node.

def addBeforeNode(self, value=None,bef=None):
        ptr=self.start
        while ptr:
            save=ptr
            ptr=ptr.link
            if (ptr.data==bef):
                break
        node=Node(value)
        save.link=node
        node.link=ptr
    def addAfterNode(s
print('After inserting element before an existing element')
ll.addBeforeNode('Yera','Zoe')
ll.printList()
Insert Before

Add a node after a given node

ptr node is assigned start address. The linked list is traversed to find the node whose data part matches the value after which the new node is to be inserted. If the given after value matches the first node’s data part while loop is skipped completely. Else in iteration of the loop ptr is updated with address of next node till the data part of ptr does not match the after value. New node’s link part is updated with link part of ptr and link part of ptr is updated with the address of the new node.

def addAfterNode(self, value=None,aft=None):
        ptr=self.start
        if(ptr.data!=aft):
            while ptr:
                ptr=ptr.link
                if (ptr.data==aft):
                    break
        node=Node(value)
        node.link=ptr.link
        ptr.link=node
print('After inserting element after an existing element')
ll.addAfterNode('Bill','Alia')
ll.printList() 

Delete a Given Node

First the value of the node to be deleted in compared with value of first node. If does not match then ptr is assigned start address. The linked list is traversed to find the node whose data part matches the value to be deleted. In iteration of the loop save is updated with ptr and ptr is updated with address of next node till the data part of ptr does not match value to be deleted. When the node to be deleted is found, save’s link part is updated with link part of ptr thus deleting the given node.

def delNode(self, value=None):
        if (self.start.data==value):
            self.start=self.start.link
        else:    
            ptr=self.start
            while ptr:
                save=ptr
                ptr=ptr.link
                if (ptr.data==value):
                    break
        save.link=ptr.link
           
print('After deleting an element ')
ll.delNode('Cathy')
ll.printList() 

Complete Program of Python Linked List

class Node:
    def __init__(self, data=None, link=None):
        self.data=data
        self.link=link
    def __str__(self):
        return str(self.data)

class LinearList:
    def __init__(self, start=None):
        self.start=start
    def printList(self):
        ptr=self.start
        while ptr:
            print(ptr)
            ptr=ptr.link
        print()
    def addBegNode(self, value=None):
        node=Node(value)
        node.link=self.start
        self.start=node
    def addEndNode(self, value=None):
        ptr=self.start
        while ptr:
            save=ptr
            ptr=ptr.link
        node=Node(value)
        save.link=node
        node.link=None
    def addBeforeNode(self, value=None,bef=None):
        ptr=self.start
        while ptr:
            save=ptr
            ptr=ptr.link
            if (ptr.data==bef):
                break
        node=Node(value)
        save.link=node
        node.link=ptr
    def addAfterNode(self, value=None,aft=None):
        ptr=self.start
        if(ptr.data!=aft):
            while ptr:
                ptr=ptr.link
                if (ptr.data==aft):
                    break
        node=Node(value)
        node.link=ptr.link
        ptr.link=node

    def delNode(self, value=None):
        if (self.start.data==value):
            self.start=self.start.link
        else:    
            ptr=self.start
            while ptr:
                save=ptr
                ptr=ptr.link
                if (ptr.data==value):
                    break
        save.link=ptr.link
           
        
node1=Node('amy')
node2=Node('Bob')
node3=Node('Cathy')
node1.link=node2
node2.link=node3
ll=LinearList(node1)
print('Initially list elements')
ll.printList()
print('After inserting element at beginning')
ll.addBegNode('Alia')
ll.printList()
print('After inserting element at end')
ll.addEndNode('Zoe')
ll.printList()
print('After inserting element before an existing element')
ll.addBeforeNode('Yera','Zoe')
ll.printList()
print('After inserting element after an existing element')
ll.addAfterNode('Bill','Alia')
ll.printList() 
print('After deleting an element ')
ll.delNode('Cathy')
ll.printList()     

You can read the basics of a Linked List here

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *