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.

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.