Implementation of Linked list Using Python

Linked list is one of important data structure in software development and if you're from a different background other then CS then it would be quite tedious to master. Here I will present a simple way to represent the Linked list in Python.

So first What is Linked list?

Linked List a kind of Data structure used in software development. In this data structure, data is represented in Nodes where every node contains a pair (data,pointer) where data is from current node and pointer is pointing to next node. Typically Linked list can represented as below.

linked list

Creating a linked list

Now To create a linked list, first we had to create a typical Node which store all the information.

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

    def get_data(self):
    return self.data

    def get_next_node(self):
        return self.next_node

    def set_next_node(self,new_node):
        self.next_node= new_node

Now Let's start with Linked list

class Linkedlist():
    def __init__(self,head=None):
        self.head=head

Define a method to add a new item to linked list. Addition of the data will done on the start of the linked list. So to add a new item, the new node pointer should point where the head node is pointing now (simple logic) and newly created node will became head now.

    def add(self,data):
        new_node= Node(data) #create a new node
        new_node.set_next_node(self.head)
        self.head= new_node

Define a method to get the size of the linked list. For this traverse the entire linked list, start from head node, update the count, visit the next node , until the final node.

    def size(self):
        current_node = self.head
        count =0 
        while current_node:
            count = count + 1
            current_node= current_node.get_next_node()
        return count

Now Let's write a function to search the given data into a given linked list.For this we will use the same logic we used for size method. Start from the head , compare the node-data to the data(search-data), if not matched, then visit the next node, repeat the same. If the data is not in the linked list then raise a ValueError.

    def search(self,data):
        current_node = self.head
        found = False
        while current_node and found is False:
            if current_node.get_data() == data:
                found = True
            else:
                current_node = current_node.get_next_node()
        if current_node is None:
            raise ValueError("Data is not on Show")
        return current_node

Now Let's write a method to delete some data in linked list. But before this, Let's first understand how deletion work in linked list.

linked list

To delete a node, Just remove the pointer pointing to the node(to be deleted). Here We will just update our search method.

    def delete(self,data):
        current_node = self.head
        previous_node =None
        found= False
        while current_node and found is False:
            if current_node.get_data() == data:
                found= True
            else:
                previous_node= current_node
                current_node = current_node.get_next_node()
        if current_node is None:
            raise ValueError("Data is not on Show")
        if previous_node is None:
            self.head= current_node.get_next_node()
        else:
            previous_node.set_next_node(current_node.get_next_node())

Below method is used to print the content of linked list. [This is not a grate way]

    def __str__( self ) :
        string = ""
        p = self.head
        if p != None :
            while p.get_next_node() != None :
                string += str(p.get_data())
                p = p.get_next_node()
            string += str(p.get_data())
        return string

Finally we know how to implement a linked list. Now Implement this and if there is something you need help let us know.