Linked Lists

Hi! If you are thinking where have you arrived and have no clue of whats going on then visit this page.

Here is the lecture on queues and linked lists by Prof Naveen Garg.

Learn Linked Lists in 10 minutes from the following video:

This video is also a very good source:
http://www.csanimated.com/animation.php?t=Linked_list

1. Singly Linked List:
A singly link list consists of one or more nodes with each node having a next pointer that points to the next node.

A very simple Node with all the operations might look like this in Python:

#node of a Singly Linked List
class Node:
    #constructor
    def __init__(self):
        self.data = None
        self.next = None
    
    #method for setting the data field of the node    
    def setData(self,data):
        self.data = data
     
    #method for getting the data field of the node   
    def getData(self):
        return self.data
    
    #method for setting the next field of the node
    def setNext(self,next):
        self.next = next
    
    #method for getting the next field of the node    
    def getNext(self):
        return self.next

Now that we have dealt with the nodes. Lets deal with the actual Linked List that contain these nodes.

The basic operations in a singly linked list are:

1. Traversing a Linked List
2. Inserting an element in the Linked List
3. Deleting an element in the Linked List

The code for implementing a Singly Linked List is as follows:

#A Singly Linked List
class SinglyLinkedList:
    #constructor
    def __init__(self):
        self.head = None
        self.length = 0
    
    #method for setting the head of the Linked List
    def setHead(self,head):
        self.head = head
                
    #method for inserting a new node at the beginning of the Linked List (at the head)    
    def insertAtBeg(self,data):
        newNode = Node()
        newNode.setData(data)
        if self.length == 0:
            self.head = newNode
        else:
            newNode.setNext(self.head)
            self.head = newNode
        self.length += 1
    
    #method for inserting a new node at the end of a Linked List   
    def insertAtEnd(self,data):
        newNode = Node()
        newNode.setData(data)
        
        current = self.head
        while current.getNext() != None:
            current = current.getNext()
            
        current.setNext(newNode)
        self.length += 1
        
    #method for inserting a new node at any position in a Linked List
    def insertAtPos(self,pos,data):
        if pos > self.length or pos < 0:
            return None
        else:
            if pos == 0:
                self.insertAtBeg(data)
            else:
                if pos == self.length:
                    self.insertAtEnd(data)
                else:
                    newNode = Node()
                    newNode.setData(data)  
                    count = 0
                    current = self.head
                    while count < pos-1:
                        count += 1
                        current = current.getNext()
                        
                    newNode.setNext(current.getNext())
                    current.setNext(newNode)
                    self.length += 1
                    
    #method for traversing and printing the Linked List
    def printList(self):
        current = self.head
        while current != None:
            print current.getData()
            current = current.getNext()
    
    #method for deleting a node having a certain data        
    def delete(self,data):
        current = self.head
        previous = self.head
        
        if self.head.getData() == data:
            self.head = self.head.getNext()
        else:
            while (current.getData() != data):
                previous = current
                current = current.getNext()
            
            if current.getData() == data:
                previous.setNext(current.getNext())
            else:
                return None
                          
                
                
if __name__ == "__main__":
    ll = SinglyLinkedList()
    ll.insertAtBeg(1)
    
    ll.insertAtBeg(2)
    ll.insertAtEnd(3)
    ll.insertAtPos(0, 4)
    ll.insertAtPos(4,5)
    ll.insertAtPos(2,9)
    
    
    ll.printList()

    ll.delete(9)
    
    print "Linked List After Deletion"
    ll.printList()
    
    print "Deleting the last element"
    ll.delete(5)
    ll.printList()
                

2. Doubly Linked List
A node in a doubly linked list can be defined using a class. It might look as follows:

class Node:
    #constructor
    def __init__(self):
        self.data = 0
        self.next = None
        self.previous = None
     
    #method for setting the value of a node   
    def setValue(self,value):
        self.data = value
    
    #method for getting the value of a node    
    def getValue(self):
        return self.data
    
    #method for setting the next node of a node
    def setNext(self,next):
        self.next = next
    
    #method for getting the next node of a node    
    def getNext(self):
        return self.next
    
    #method for setting the previous node of a node
    def setPrevious(self,previous):
        self.previous = previous
    
    #method for getting the previous node of a node    
    def getPrevious(self):
        return self.previous

The basic operations in a Doubly Linked List is again
1. Insertion
2. Deletion
3. Traversal

The class for Doubly Linked List along with its operations is defined as follows:

class DoublyLinkedList:
    #constructor
    def __init__(self):
        self.head = None #head of the list
        self.length = 0 #length of the list
    
    #method for inserting at the beginning of the list    
    def insertAtBeg(self,value):
        newNode = Node()
        newNode.setValue(value)
        newNode.setNext(None)
        newNode.setPrevious(None)
        if self.length == 0:
            self.head = newNode
            self.length += 1
        else:
            newNode.setNext(self.head)
            self.head.setPrevious(newNode)
            self.head = newNode
            self.length += 1
    
    #method for inserting a node at the end        
    def insertAtEnd(self,value):
        newNode = Node()
        newNode.setValue(value)
        
        current = self.head
        while(current.getNext() != None):
            current = current.getNext()
            
        newNode.setNext(current.getNext())
        newNode.setPrevious(current)
        current.setNext(newNode)
        self.length += 1
        
    #method for inserting a node at the middle    
    def insertAtMid(self,pos,value):
        newNode = Node()
        newNode.setValue(value)
        current = self.head
        count = 0
        while(count < pos-1):
            current = current.getNext()
            count += 1
            
        current.getNext().setPrevious(newNode)
        newNode.setNext(current.getNext())
        current.setNext(newNode)
        newNode.setPrevious(current)
        self.length += 1
        
    #method for traversing and printing the list    
    def printList(self):
        current = self.head
        while current != None:
            print current.getValue()
            current = current.getNext()

3. Circular Linked List

Here is a list of problems related to Linked Lists.

1. Find the nth node from the end of a singly linked list.
2. Write a program to implement ordered singly linked lists.
3. Write a program to detect a cycle in a linked list.

Advertisement

Detecting Cycles in Linked List (Hare and Tortoise)

The problem is as follows:
Check whether the given linked list is NULL terminated or ends in a cycle.

Sample Input: 1->2->3->4->5->6->7->8->3
where the numbers 1,2… are the positions in the linked list instead of actual entries.
The node at the 8th position again points to the node at the 3rd position forming a cycle.

Sample Output: True

A very good discussion of how the cycles are detected can be found in wikipedia over here:http://en.wikipedia.org/wiki/Cycle_detection

The Floyds’ algorithm commonly referred as tortoise and hare method is often used for detecting cycles. It could be an interesting read.

We can think of a hare and a tortoise running on a track. The faster running hare will catch up with the tortoise if they are running in a loop.

The basic algorithm is as follows:
Step 1. Start Tortoise and Hare at the first node of the List.
Step 2. If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare one step forward.
Step 3. If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare and Tortoise one step forward.
Step 4. If Hare and Tortoise pointing to same Node return, we found loop in the List.
Else start with STEP-2.

'''Complexity
Space : O(n) Time: O(1)'''


class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
    def setData(self,data):
        self.data = data
    
    def getData(self):
        return self.data
    
    def setNext(self, next):
        self.next = next
        
    def getNext(self):
        return self.next
    
    
class LinkedList:
    def __init__(self):
        self.head = None
        
    def isEmpty(self):
        return self.head == None
    
    def insertAtBeg(self,item):
        node = Node(item)
        node.setNext(self.head)
        self.head = node
        
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count
    
    def search(self,item):
        found = False
        current = self.head
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
                
        return found
    
    def insertAtEnd(self,item):
        current = self.head
        
        while current.getNext() != None:
            current = current.getNext()
            
        node = Node(item)
        current.setNext(node)
        
    def insertBeforeItem(self,inItem,item):
        current = self.head
        previous = None
        found = False
        stop = False
        
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
                stop = True
            else:
                previous = current
                current = current.getNext()
                
        node = Node(inItem)
        previous.setNext(node)
        node.setNext(current)
        
        
    def insertAfterItem(self,inItem,item):
        current = self.head
        
        found = False
        stop = False
        
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
                stop = True
            else:
#                previous = current
                current = current.getNext()
        successor = current.getNext()       
        node = Node(inItem)
        current.setNext(node)
        node.setNext(successor)
        
            
        
        
        
    def printList(self):
        current = self.head
        
        while current != None:
            print current.getData()
            current = current.getNext()
            
            
    def remove(self,item):
        found = False
        current = self.head
        previous = None
        
        while current.getNext() != None and not found:
            if current.getData() == item:
                print current.getData()
                print previous.getData()
                found = True
                previous.setNext(current.next)
            else:
                previous = current
                current = current.getNext()
                
    def induceCycle(self,end,start):
        current = self.head
        stop = False
        endnodeFound = False
        endnodePointer = None
        count = 0
        while current!= None and not stop:
            count += 1
            if count == end:
                endnodeFound = True
                endnodePointer = current.getNext()
                
            else:
                if count == start:
                    stop = True
                else:
                    current = current.getNext()
                    
        current.setNext(endnodePointer)
        
    def detectCycle(self):
        hare = self.head
        tortoise = self.head
        
        while (hare and tortoise):
            hare = hare.getNext()
            if (hare == tortoise):
                return True
            
            if hare == None:
                return False
            
            hare = hare.getNext()
            if (hare == tortoise):
                return True
            
            tortoise = tortoise.getNext()
            
        
        
        
                
        
        
            
        
        
if __name__ == "__main__":
    ll = LinkedList()
    ll.insertAtBeg(1)
    ll.insertAtBeg(2)
    ll.insertAtEnd(3)
    ll.insertBeforeItem(4, 3)
    ll.insertAfterItem(5, 1)
    ll.insertAtEnd(6)
    ll.insertAtEnd(8)
    ll.insertAtEnd(7)
    
    
    ll.printList()
    
    ll.induceCycle(2, 8)
    print ll.detectCycle()

Getting nth node of a linked list from the end

The problem is as follows:
Find the nth node from the end of a singly linked list.

Sample Input : 2->1->5->4->3 and n = 3
Sample Output : 5

'''Complexity
Space:  O(n) and Time: O(1)'''


class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
    def setData(self,data):
        self.data = data
    
    def getData(self):
        return self.data
    
    def setNext(self, next):
        self.next = next
        
    def getNext(self):
        return self.next
    
    
class LinkedList:
    def __init__(self):
        self.head = None
        
    def isEmpty(self):
        return self.head == None

    def insertAtBeg(self,item):
        node = Node(item)
        node.setNext(self.head)
        self.head = node
        
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count
    
    def search(self,item):
        found = False
        current = self.head
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
                
        return found
    
    def insertAtEnd(self,item):
        current = self.head
        
        while current.getNext() != None:
            current = current.getNext()
            
        node = Node(item)
        current.setNext(node)
        
    def insertBeforeItem(self,inItem,item):
        current = self.head
        previous = None
        found = False
        stop = False
        
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
                stop = True
            else:
                previous = current
                current = current.getNext()
                
        node = Node(inItem)
        previous.setNext(node)
        node.setNext(current)
        
        
    def insertAfterItem(self,inItem,item):
        current = self.head
        
        found = False
        stop = False
        
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
                stop = True
            else:
#                previous = current
                current = current.getNext()
        successor = current.getNext()       
        node = Node(inItem)
        current.setNext(node)
        node.setNext(successor)
        
            
        
        
        
    def printList(self):
        current = self.head
        
        while current != None:
            print current.getData()
            current = current.getNext()
            
            
    def remove(self,item):
        found = False
        current = self.head
        previous = None
        
        while current.getNext() != None and not found:
            if current.getData() == item:
                print current.getData()
                print previous.getData()
                found = True
                previous.setNext(current.next)
            else:
                previous = current
                current = current.getNext()
                
         
    def nthNodeFromEnd(self,n):
        
        if self.isEmpty():
            print "There are no items in the list"
            return
        
        if n > self.length():
            print "N is greater than the lenght of the list and is not possible to fetch it"
            return
        
        
        current = self.head
        previous = self.head
        count = 0
        while count < n and current != None:
            count += 1
            current = current.getNext()
            
        while current != None:
            previous = previous.getNext()
            current = current.getNext()
            
        return previous.getData()
    
    
if __name__ == "__main__":
    ll = LinkedList()
    ll.insertAtBeg(1)
    ll.insertAtBeg(2)
    ll.insertAtEnd(3)
    ll.insertBeforeItem(4, 3)
    ll.insertAfterItem(5, 1)
    print "The linked list is as follows:"
    ll.printList()
    print "\n\n"
    print "The 2nd item from the end is:",ll.nthNodeFromEnd(2)
    print "The 3rd item from the end is:", ll.nthNodeFromEnd(3)

 

Ordered Singly Linked List

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
    def setData(self,data):
        self.data = data
    
    def getData(self):
        return self.data
    
    def setNext(self, next):
        self.next = next
        
    def getNext(self):
        return self.next
    
    
class LinkedList:
    def __init__(self):
        self.head = None
        
    def isEmpty(self):
        return self.head == None
    
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count
    
    def search(self,item):
        found = False
        stop = False
        current = self.head
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()
                
        return found
    
    def insertion(self,item):
        if self.head == None:
            node = Node(item)
            node.setNext(self.head)
            self.head = node
        else:
            current = self.head
            previous = None
            stop = False
            
            while current != None and not stop:
                if current.getData() > item:
                    stop = True
                else:
                    previous = current
                    current = current.getNext()
            
            node = Node(item)        
            previous.setNext(node)
            node.setNext(current)
            

    def remove(self,item):
        found = False
        current = self.head
        previous = None
        
        while current.getNext() != None and not found:
            if current.getData() == item:
                print current.getData()
                print previous.getData()
                found = True
                previous.setNext(current.next)
            else:
                previous = current
                current = current.getNext()
                
    def printList(self):
        current = self.head
        
        while current != None:
            print current.getData()
            current = current.getNext()        
        
            
        
        
if __name__ == "__main__":
    ll = LinkedList()
    ll.insertion(1)
    ll.insertion(2)
    ll.insertion(3)
    ll.insertion(6)
    ll.insertion(4)
    
    
    ll.printList()