(Source code for Linked List can be found here –> Linked List)

Linked List is a list of elements/whatever you say which are of two kinds:

  1. Single Linked List
  2. Double Linked List

Linked list is made up of NODES, which generally have the following properties:

  • Key
  • Next Pointer
  • Previous Pointer (Only with Double Linked List)

Along with nodes every linked list has a HEAD as well as a TAIL which are pointers to its head and tail respectively

 

NODES IN PYTHON:

 

class Node():
    def __init__(self,key):
    self.key = key
    self.next = None
    self.prev = None

 

SIMPLE LINKED LIST IN PYTHON:

 

class SingleLinkedList():

    def __init__(self):
        self.head = None
        self.tail = None

    def getLinkedList(self):
        curr = self.head
        print "head --->",
        while curr != None:
        print curr.key,"-->",
        curr = curr.next
        print "tail"

 

 


 

OPERATIONS ON LINKED LIST

 

PUSH FRONT

 

Takes a key and add a node to the front of the linked list. Time complexity is O(1). Python code:

 

def pushFront(self,key):
    temp = Node(key)
    #Case empty
    if self.head == None:
        self.head = temp
        self.tail = temp
    #Case not empty
    else:
        temp.next = self.head
        self.head = temp

Example

l = SingleLinkedList()
l.pushFront(5)
l.getLinkedList()
l.pushFront(10)
l.getLinkedList()
l.pushFront(20)
l.getLinkedList()

>>>>>>>>>>>OUTPUT<<<<<<<<<<<<<<<<<<

head ---> 5 --> tail
head ---> 10 --> 5 --> tail
head ---> 20 --> 10 --> 5 --> tail

 

TOP FRONT

 

Returns the head of the linked list. Time complexity is O(1). Python code:

 

def topFront(self):
    return self.head

 

POP FRONT

 

Pops out the head of the linked list if it exists otherwise return null. Time complexity is O(1). Python code:

 

def popFront(self):
     if self.head == None:
         return None
     elif self.head == self.tail:
         self.head =None
         self.tail = None
    else:
        self.head = self.head.next

Example :

l = SingleLinkedList()
l.pushFront(5)
l.getLinkedList()
l.pushFront(10)
l.getLinkedList()
l.pushFront(20)
l.getLinkedList()
while l.head != None:
    print l.topFront().key
    l.popFront()
    l.getLinkedList()

>>>>>>>>OUTPUT<<<<<<<<<<<<<<<<

head ---> 5 --> tail
head ---> 10 --> 5 --> tail
head ---> 20 --> 10 --> 5 --> tail
20
head ---> 10 --> 5 --> tail
10
head ---> 5 --> tail
5
head ---> tail

 

PUSH BACK

 

Push Back takes a key and adds it to the end of the linked list. If tail pointer is present which is not necessary for every linked list time complexity will be O(n) since it will have to iterate till the last Node of the linked list otherwise if tail pointer is present time complexity is O(1)

Python Code:

 

def pushBack(self,key):
    temp = Node(key)
    #empty case
    if self.head == None:
        self.head = temp
        self.tail = temp
    #non empty case
    else:
        self.tail.next = temp
        self.tail = temp

Example :

l = SingleLinkedList()
l.pushFront(5)
l.getLinkedList()
l.pushFront(10)
l.getLinkedList()
l.pushFront(20)
l.getLinkedList()
while l.head != None:
    print l.topFront().key
    l.popFront()
    l.getLinkedList()
l.pushBack(5)
l.getLinkedList()
l.pushBack(10)
l.pushBack(20)
l.pushFront(0)
l.getLinkedList()

>>>>>>>>>>>>OUTPUT<<<<<<<<<<<<<<

head ---> 5 --> tail
head ---> 10 --> 5 --> tail
head ---> 20 --> 10 --> 5 --> tail
20
head ---> 10 --> 5 --> tail
10
head ---> 5 --> tail
5
head ---> tail
head ---> 5 --> tail
head ---> 0 --> 5 --> 10 --> 20 --> tail

 

TOP BACK

 

Top Back return the tail of the linked list if it exists otherwise null. The time complexity for Top back is O(1) if the tail pointer exists otherwise O(n). Python code:

 

def topBack(self):
    return self.tail

 

POP BACK

 

Pop Back pops out the tail of the Linked List if it exists otherwise returns null.The Time complexity for pop Back is O(n) since we have to iterate till the second last node of the linked list and set it as the tail of that linked list. Python code:

 

def popBack(self):
    #case empty
    if self.head == None:
        return None
    #case only one node
    elif self.head == self.tail :
        temp_tail = self.head
        self.head = None
        self.tail = None
        return temp_tail
#case otherwise
    else:
        temp = self.head
        temp_tail = self.tail
        while temp.next != self.tail:
        temp = temp.next
        temp.next = None
        self.tail = temp
        return temp_tail

Example

while l.head!=None:
l.popBack()
l.getLinkedList()

>>>>>>>>>>OUTPUT<<<<<<<

head ---> 5 --> 10 --> tail
head ---> 5 --> tail
head ---> tail

 

Add After

 

Add after takes a node and a key pair and add a new node after the given node. The Time complexity is O(1). Python code is:

 

def addAfter(self,node,k):
temp = Node(k)
# case only one node
if self.head == self.tail:
node.next = temp
self.tail = temp
#case node is the tail
elif self.tail = node:
node.next = temp
self.tail = temp
#case otherwise
else:
temp.next = node.next
node.next = temp

 

Add Before

 

Add before is quite similar to add after with the only difference being the previous node is not known. Hence we will have to iterate till the previous of the given node and change its pointer. This leads to the time complexity of O(n). Python code:

 

def addBefore(self,node,k):
temp = Node(k)
curr = self.head
while curr.next != node:
curr = curr.next
temp.next = curr.next
curr.next temp

 

Find

 

Find takes a key and look for it in the linked list. The time complexity for find is O(n). Python code:

 

def find(self,k):
curr = self.head
result = False
while curr != self.tail:
if curr.key == k:
result = True
break
else:
curr = curr.next
if curr.key == k:
result = True
return result

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s