Algorithms: Coding a linked list in python

Algorithms: Coding a linked list in python
5 (100%) 3 votes

So next in the algorithm section we are going to write a linked list using python. If you don’t know what is linked list you can read it here.

Algorithms: Coding a linked list in python

A linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence.

Algorithms: Coding a linked list in python
[taken from:https://people.engr.ncsu.edu/efg/210/s99/Notes/LLdefs.gif]

The above is a representation of linked list.

For linked list we need a class node which represent each data element in linked list. The class will be like below

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

Here the class contains data element, next_node in the __init__ function. You can also write a getter setter function to make it accessible by calling functions.

Next we need a class for linked list which will hold the head of the linked list. Look at the class below.

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

We will now write functions to insert, delete, search and get size of the linked list.

Insertion

def insert_at_start(self, data):
   tmpnode = node(data)
   tmpnode.next_node = self.head
   self.head = tmpnode

def insert_at_end(self, data):
   tmpnode = node(data)
   current = self.head
   while current.next_node:
       current = current.next_node
       current.next_node = tmpnode

The first function is used to insert at the start and second function for inserting at the end.

How does these work.

Insert at Start: Here to initialize a node with data element. Then assign the next_node as head of the linked list and head as the newly created linked list. Thus resulting in insertion at the start.

Insert at End: Here we initialize a node, traverse to the end of the linked list and assign current.next_node to the newly created one.

Search

def search(self, data):
   current = self.head
   found = False
   while current and found is False:
       if current.data == data:
           found = True
       else:
           current = current.next_node
   if current is None:
       current= {}
       current.data = "Not found"
   return current

Here we traverse the list and search for the data present on any node. Else returning Not found in current.data.

Delete:

def delete(self, data):
   current = self.head
   if current.data == data:
       self.head = current.next_node
   while current.next_node:
       if current.next_node.data == data:
           current.next_node = current.next_node.next_node
       else:
           current = current.next_node

I am leaving this one and other functions for you to understand. Below is the whole code. Have a look try to understand and comment if you don’t understand.

 

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


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

 def insert_at_start(self, data):
   tmpnode = node(data)
   tmpnode.next_node = self.head
   self.head = tmpnode

 def insert_at_end(self, data):
   tmpnode = node(data)
   current = self.head
   while current.next_node:
   current = current.next_node
   current.next_node = tmpnode

 def search(self, data):
   current = self.head
   found = False
   while current and found is False:
     if current.data == data:
       found = True
     else:
       current = current.next_node
   if current is None:
     print "Data not in list"
   return current

 def size(self):
   current = self.head
   count = 0
   while current:
     count += 1
     current = current.next_node
   return count

 def traversal(self):
   current = self.head
   while current.next_node:
     print current.data
     current = current.next_node
   print current.data

 def delete(self, data):
   current = self.head
   if current.data == data:
     self.head = current.next_node
   while current.next_node:
     if current.next_node.data == data:
       current.next_node = current.next_node.next_node
     else:
       current = current.next_node


a = linked_list()
a.insert_at_start(1)
a.insert_at_start(2)
a.insert_at_start(3)
a.insert_at_start(4)
a.insert_at_end(5)
a.traversal()
# 4
# 3
# 2
# 1
# 5
print a.search(1).data
# 1
a.delete(1)
print 'deleted 1'
a.traversal()
# 4
# 3
# 2
# 5
a.delete(5)
print 'deleted 5'
a.traversal()
# 4
# 3
# 2
print a.size()
# 3

Try running the code and modify it to find out mistake and comment if you find one. I know there is one and I was too lazy to fix that đŸ˜›

Like the article share and subscribe.


Gaurav Yadav

Gaurav is a Full Stack Web Developer and Blogger. Sportsperson by heart and loves football. He has experience with various frameworks in php, python and javascript. Loves to explore new frameworks and evolve with the trending technology.

Leave a Reply

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