Linked_lists_python.py

#Linked list in python
class node:                     #creating a class called node. All nodes created in code are objects of this node class.
    def __init__(self, value):  #crustructor (automatically called when an object is made)
        self.data=value
        self.next=None          #next contains points to the next node.There is nothing to point at initially so here its None
class LinkedList:
    def __init__(self):
        self.head=node(None)    #head node has no data and points to the  first element in the linked list.
    def append(self, value):    #Member function to append data at end.
        new=node(value)            #created a new node with value to be appended
        current_node=self.head     #creating a variable cur_node to traverse through the linked list.
        while current_node.next!=None:       #Because the last element has next as None
            current_node=current_node.next   #Traversing through the linked list one node at a time
        current_node.next=new                #When last element is found, add a link to the new node
    def insert(self,index,value):   #To insert a value (node) by index.
        new=node(value)
        curr_index=0                #As linked lists have no index, we will count from the beginning as we move forward,
        prev_node=self.head         #Starting prev node from head
        curr_node=self.head.next    #Starting current node from the first element
        while curr_index<index:     #Traverse linked list until index is reached
            prev_node=prev_node.next
            curr_node=curr_node.next
            curr_index+=1
        prev_node.next=new          #When index reached, inserting new node by creating link btw prev_node and new node
        new.next=curr_node          #and creating a link btw new node and curr_node.
    def display(self):
        cur_node=self.head
        while cur_node.next!=None:  #To display, staring with head, traversing list and printing each node until last element is reached
            cur_node=cur_node.next
            print(cur_node.data,end=" ")
        print('\n')
    def delete_last(self):          #To delete the last node
        prev_node=self.head
        cur_node=self.head.next
        while(cur_node.next!=None):    #Traverse until last node is reached
            cur_node=cur_node.next
            prev_node=prev_node.next
        prev_node.next=None             #Simply break linking btw the last node and its prev node(By making prev node point to nothing)
    def delete(self,index):             #To delete a node by index
        prev_node=self.head
        cur_node=self.head.next
        cur_index=0
        while(cur_index<index):         #Traversing the list until index is reached
            cur_node=cur_node.next
            prev_node=prev_node.next
            cur_index+=1
        prev_node.next=cur_node.next        #Hence deleting cur_node( by breaking the link before and reconecting it after cur_node)


A=LinkedList()
A.append(1)
A.append(3)
A.append(4)
A.display()
A.insert(1,2)     #To insert 2 at index 1 (i.e 2nd place)
A.display()
A.delete_last()
A.display()
A.delete(1)       #To delete element at index 1(i.e 2nd place)
A.display()