Python - Insert a new node at a given position in the Circular Singly Linked List
In this method, a new element is inserted at the specified position in the circular singly linked list. For example - if the given list is 10->20->30 and a new element 100 is added at position 2, the list becomes 10->100->20->30.
First, create two nodes: 1. newNode with given element and 2. temp to traverse through the list. After that count the number of elements in the list to check whether the insertion position is valid or not (It must lie in the range of [1, n + 1], where n is number of elements in the list). If the insertion position is valid and equal to 1 then make the newNode as head and adjust links accordingly. If the insertion position is valid and greater than 1 then traverse to the specified position and insert the newNode and adjust links accordingly.
The function push_at is created for this purpose. It is a 5-step process.
def push_at(self, newElement, position): #1. allocate node to new element and # create a temp node to traverse the list newNode = Node(newElement) temp = self.head NoOfElements = 0 #2. Find the number of elements in the list if(temp != None): NoOfElements += 1 temp = temp.next while(temp != self.head): NoOfElements += 1 temp = temp.next #3. check if the insertion position is valid if(position < 1 or position > (NoOfElements+1)): print("\nInavalid position.") elif (position == 1): #4. if the position is 1, make next of the # new node as head and new node as head if(self.head == None): self.head = newNode self.head.next = head else: while(temp.next != self.head): temp = temp.next newNode.next = self.head self.head = newNode temp.next = self.head else: #5. Else, traverse to the node previous to # the given position, make newNode next # as temp next and temp next as newNode. temp = self.head for i in range(1, position-1): temp = temp.next newNode.next = temp.next temp.next = newNode
The below is a complete program that uses above discussed concept to insert a new node at given position in the circular singly linked list.
# node structure class Node: def __init__(self, data): self.data = data self.next = None #class Linked List class LinkedList: def __init__(self): self.head = None #Add new element at the end of the list def push_back(self, newElement): newNode = Node(newElement) if(self.head == None): self.head = newNode newNode.next = self.head return else: temp = self.head while(temp.next != self.head): temp = temp.next temp.next = newNode newNode.next = self.head #Inserts a new element at the given position def push_at(self, newElement, position): newNode = Node(newElement) temp = self.head NoOfElements = 0 if(temp != None): NoOfElements += 1 temp = temp.next while(temp != self.head): NoOfElements += 1 temp = temp.next if(position < 1 or position > (NoOfElements+1)): print("\nInavalid position.") elif (position == 1): if(self.head == None): self.head = newNode self.head.next = self.head else: while(temp.next != self.head): temp = temp.next newNode.next = self.head self.head = newNode temp.next = self.head else: temp = self.head for i in range(1, position-1): temp = temp.next newNode.next = temp.next temp.next = newNode #display the content of the list def PrintList(self): temp = self.head if(temp != None): print("The list contains:", end=" ") while (True): print(temp.data, end=" ") temp = temp.next if(temp == self.head): break print() else: print("The list is empty.") # test the code MyList = LinkedList() #Add three elements at the end of the list. MyList.push_back(10) MyList.push_back(20) MyList.push_back(30) MyList.PrintList() #Insert an element at position 2 MyList.push_at(100, 2) MyList.PrintList() #Insert an element at position 1 MyList.push_at(200, 1) MyList.PrintList()
The above code will give the following output:
The list contains: 10 20 30 The list contains: 10 100 20 30 The list contains: 200 10 100 20 30