Python - Count nodes in the Circular Doubly Linked List
Counting nodes in a circular doubly linked list is very useful while working on it. It requires creating a temp node pointing to the head of the list and a variable called i with initial value 0. If the temp node is not null, increase i by 1 and move to the next node using temp next. Repeat the process till the temp node reaches the head. The final value of i will be the total number of nodes in the circular doubly linked list.
The function countNodes is created for this purpose. It is a 4-step process.
def countNodes(self): #1. create a temp node pointing to head temp = self.head #2. create a variable to count nodes i = 0 #3. if the temp node is not null increase # i by 1 and move to the next node, repeat # the process till the temp becomes null if (temp != None): i += 1 temp = temp.next while (temp != self.head): i += 1 temp = temp.next #4. return the count return i
The below is a complete program that uses above discussed concept of counting the total number of nodes of a circular doubly linked list.
# node structure class Node: def __init__(self, data): self.data = data self.next = None self.prev = 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 newNode.prev = self.head return else: temp = self.head while(temp.next != self.head): temp = temp.next temp.next = newNode newNode.next = self.head newNode.prev = temp self.head.prev = newNode #count nodes in the list def countNodes(self): temp = self.head i = 0 if (temp != None): i += 1 temp = temp.next while (temp != self.head): i += 1 temp = temp.next return i #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 four elements in the list. MyList.push_back(10) MyList.push_back(20) MyList.push_back(30) MyList.push_back(40) #Display the content of the list. MyList.PrintList() #number of nodes in the list print("No. of nodes: ", MyList.countNodes())
The above code will give the following output:
The list contains: 10 20 30 40 No. of nodes: 4