Linked List with Python #singlylinkedlist #insertion #deletion

Linked List

• 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.
• Each node is composed of data and a reference (in other words, a link) to the next node
• Compared to arrays:
• Advantages:
• Dynamically allocated memory and hence need not be contiguous
• Unlike Arrays, updation (Deletion or addition or modify) does not involve lot of data movement
• Disadvantages
• Has to store pointers or addresses
• No linear access and needs to be traversed to fetch the data whereas array elements can be accesses with the o(1) when index is known

Node Structure:

        Singly linked list node contains a data and a link say next

        Data_1|Next_1--->   Data_2|Next_2  ....  Data_n|Next_n ---> Null

Example:

        1|101 --->2|109 ---> 3|809 ---> NULL

        As you see, by linked list property the address need not be contiguous.

CODE:

##Node Structure

def __init__ self, dx):

      self.dx = dx

      self.next = None

#-------------------------------------------------------------------------------

# Name:        Linked List

# Purpose:     To my blog

#

# Author:      Hari Priya

#

# Created:     11/12/2016

# Copyright:   (c) Hari Priya 2016

#

#-------------------------------------------------------------------------------

class Node:

    def __init__(self, dx):

        self.dx = dx

        self.next = None

class LL:

    def __init__(self):

        self.head = None

    #Insert in the beginning

    def insert(self, dx):

        new_node = Node(dx)

        new_node.next = self.head

        self.head = new_node

       

    #Insert in the end    

    def append(self, dx):

        new_node = Node(dx)

         #Handle Single node case

        if self.head:

            if not self.head.next:

                self.head.next = new_node

            else:

                curr = self.head

                while (curr):

                    prev = curr

                    curr = curr.next

                prev.next = new_node

        else:

            self.head = new_node

    #Deletion
      def delete(self, dx):
        node_found = False
        
        #Empty linked list
        if not self.head:
            return

        #single node case
        if not self.head.next:
            if self.head:
                self.head = None
            return

        curr = self.head
        prev = None
        while(curr):
            if curr.dx == dx:
                node_found = True
                break
            prev = curr
            curr = curr.next
        if node_found:
            if prev:
                prev.next = curr.next          
            else:
                #First node deletion
                self.head = self.head.next
        else:
            print("Node not found")
          
    #Override __str__ to print the list object
     def __str__(self):
        li = []
        temp = self.head
        while(temp):
            li.append(temp.dx)
            temp = temp.next
        return (str(li))


def main():
    sinLL = LL()
    #create a list of 10 numbers
    for i in range(10):
        sinLL.append(i+1)
    print (sinLL)
    #1->2->3->4->5->6->7->->8->9->10   
    #Deleting 2
    sinLL.delete(2)
    print ("List after deletion %s" %(sinLL))
    #1->3->4->5->6->7->->8->9->10           
 
#Entry Point
if __name__ == '__main__':
    main()

Tested cases:

1. Deletion in the beginning
2. Deletion in the middle
3. Single node case
4. Two node case
5. Node not found