Python - Delete first node by key of the Circular Singly Linked List
In this method, first node in the circular singly linked list with specified key (value) is deleted. For example - if the given list is 10->20->30->10->20 and the first occurrence of 20 is deleted, the list becomes 10->30->10->20.
First, the head of the linked list is checked for null value. If the head is not null, the value stored in it is equal to the key, and head is the only element in the list then make the head as null. If the head is not null, the value stored in it is equal to the key, the list contains more than one element then make head next as head and update the link of last element of the list with the new head. Else, traverse to the node previous to the node with value equal to key, and adjust links.
The function pop_first is created for this purpose. It is a 4-step process.
def pop_first(self, key): #1. if head is not null, create two nodes- temp # and nodeToDelete - to traverse and track # the node to delete if(self.head != None): temp = self.head nodeToDelete = self.head #2. if the value store at head is the key and head # is the only element in the list, make it null if(temp.data == key): if(temp.next == self.head): self.head = None else: #3. if the value store at head is the key and list # contains more than 1 elements, traverse to the # last element of the list and link it to the new head while(temp.next != self.head): temp = temp.next self.head = self.head.next temp.next = self.head nodeToDelete = None else: #4. Else, traverse to the node previous to the # node with value equal to key, and adjust links while(temp.next != self.head): if(temp.next.data == key): nodeToDelete = temp.next temp.next = temp.next.next nodeToDelete = None break temp = temp.next
The below is a complete program that uses above discussed concept to delete first occurrence of the specified key (if exists) of 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 #Delete first node by key def pop_first(self, key): if(self.head != None): temp = self.head nodeToDelete = self.head if(temp.data == key): if(temp.next == self.head): self.head = None else: while(temp.next != self.head): temp = temp.next self.head = self.head.next temp.next = self.head nodeToDelete = None else: while(temp.next != self.head): if(temp.next.data == key): nodeToDelete = temp.next temp.next = temp.next.next nodeToDelete = None break temp = temp.next #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 five elements in the list. MyList.push_back(10) MyList.push_back(20) MyList.push_back(30) MyList.push_back(10) MyList.push_back(20) MyList.PrintList() #Delete first occurrence of 20 MyList.pop_first(20) MyList.PrintList()
The above code will give the following output:
The list contains: 10 20 30 10 20 The list contains: 10 30 10 20