Linked Lists

One can learn the basics of Linked List from the following video tutorial:

 

Here’s a program which implements Singly Linked Lists in python:

The first and the foremost thing is that we must represent a node of a list. Here’s a representation of a node:


#class for defining a Node in a list
class Node(object):
    def __init__(self,value,nextNode=None):
        self.value = value
        self.next = nextNode
        

The value field consists the value assigned to the node, and the next field consists the reference to the next node.

After this we need to create the Linked List class which actually holds the nodes and operates on them. The following class represents Linked Lists and the its basic operations:

#class for defining a linked list   
class LinkedList(object):
    
    #initializing a list
    def __init__(self):
        self.length = 0
        self.head = None
        
    #method to add a node in the linked list
    def addNode(self,node):
        if self.length == 0:
            self.addBeg(node)
        else:
            self.addLast(node)
            
        
    #method to add a node at the beginning of the list with a value   
    def addBeg(self,node):
        newNode = node
        newNode.next = self.head
        self.head = newNode
        self.length += 1
        
    #method to add a node after the node having the value=value1. The value of the new node is value2
    def addAfterValue(self,value1,node):
        newNode = node
        currentnode = self.head
        
        while currentnode.next != None or currentnode.value != value1:
            if currentnode.value == value1:
                newNode.next = currentnode.next
                currentnode.next = newNode
                self.length = self.length + 1
                return
            else:
                currentnode = currentnode.next
                
        print "The value provided is not present"
                
    #method to add a node at a particular position
    def addAtPos(self,pos,node):
        count = 0
        currentnode = self.head
        previousnode = self.head
        
        if pos > self.length or pos < 0:
            print "The position does not exist. Please enter a valid position"
        else:
            while currentnode.next != None or count < pos:
                count = count + 1
                if count == pos:
                    previousnode.next = node
                    node.next = currentnode
                    self.length += 1
                    return
                    
                else:
                    previousnode = currentnode
                    currentnode = currentnode.next
        
        
                
    #method to add a node at the end of a list
    def addLast(self,node):
        currentnode = self.head
        
        while currentnode.next != None:
            currentnode = currentnode.next

        newNode = node
        newNode.next = None
        currentnode.next = newNode
        self.length = self.length + 1
    
    
    #method to delete the first node of the linked list
    def deleteBeg(self):
        if self.length == 0:
            print "The list is empty"
        else:
            self.head = self.head.next 
            self.length -= 1
    
    #method to delete the last node of the linked list
    def deleteLast(self):
        
        if self.length == 0:
            print "The list is empty"
        else:
            currentnode = self.head
            previousnode = self.head
            
            while currentnode.next != None:
                previousnode = currentnode
                currentnode = currentnode.next
                
            previousnode.next = None
            
            self.length -= 1
            
        
    #method to delete a node after the node having the given value
    def deleteValue(self,value):
        currentnode = self.head
        previousnode = self.head
        
        while currentnode.next != None or currentnode.value != value:
            if currentnode.value == value:
                previousnode.next = currentnode.next
                self.length -= 1 
                return
                   
            else:
                previousnode = currentnode
                currentnode = currentnode.next
                
        print "The value provided is not present"
                
        
        
    #method to delete a node at a particular position
    def deleteAtPos(self,pos):
        count = 0
        currentnode = self.head
        previousnode = self.head

        if pos > self.length or pos < 0:
            print "The position does not exist. Please enter a valid position"
        else:        
            while currentnode.next != None or count < pos:
                count = count + 1
                if count == pos:
                    previousnode.next = currentnode.next
                    self.length -= 1
                    return
                else:
                    previousnode = currentnode
                    currentnode = currentnode.next
                    
            

    
    #returns the length of the list        
    def getLength(self):
        return self.length
    
    #returns the first element of the list
    def getFirst(self):
        if self.length == 0:
            print "The list is empty"
        else:
            return self.head.value
    
    #returns the last element of the list
    def getLast(self):
        
        if self.length == 0:
            print "The list is empty"
        else:
            currentnode = self.head
            
            while currentnode.next != None:
                currentnode = currentnode.next
                
            return currentnode.value
    
    #returns node at any position
    def getAtPos(self,pos):
        count = 0
        currentnode = self.head
        
        if pos > self.length or pos < 0:
            print "The position does not exist. Please enter a valid position"
        else:
            while currentnode.next != None or count < pos:
                count = count + 1
                if count == pos:
                    return currentnode.value
                else:
                    currentnode = currentnode.next

                    
    #method to print the whole list
    def print_list(self):
        nodeList = []
        currentnode = self.head
        while currentnode!= None:
            nodeList.append(currentnode.value)
            currentnode = currentnode.next  
            
        print nodeList  

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)


ll = LinkedList()

ll.addNode(node1)
ll.addNode(node2)
ll.addNode(node3)
ll.addNode(node4)

ll.print_list()
#output = [1, 2, 3, 4]

node5 = Node(5)
ll.addAtPos(3,node5)
ll.print_list()
#Output = [1, 2, 5, 3, 4]

ll.deleteAtPos(2)
ll.print_list()
#Output = [1, 5, 3, 4]