Python Data Structures - Doubly Linked List Other Related Topics

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("The list contains:", end=" ")
      while (temp != None):
        print(temp.data, end=" ")
        temp = temp.next
      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