Python - Count nodes in the Doubly Linked List
Counting nodes in a 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 becomes null. The final value of i will be the total number of nodes in the 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 while (temp != None): 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 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 return else: temp = self.head while(temp.next != None): temp = temp.next temp.next = newNode newNode.prev = temp #count nodes in the list def countNodes(self): temp = self.head i = 0 while (temp != None): i += 1 temp = temp.next return i #display the content of the list def PrintList(self): temp = self.head if(temp != None): print("\nThe list contains:", end=" ") while (temp != None): print(temp.data, end=" ") temp = temp.next else: print("\nThe 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("\nNo. of nodes: ", MyList.countNodes())
The above code will give the following output:
The list contains: 10 20 30 40 No. of nodes: 4