PHP - 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.
public function countNodes() { //1. create a temp node pointing to head $temp = new Node(); $temp = $this->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 != null) { $i++; $temp = $temp->next; } while($temp != $this->head) { $i++; $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.
<?php //node structure class Node { public $data; public $next; public $prev; } class LinkedList { public $head; public function __construct(){ $this->head = null; } //Add new element at the end of the list public function push_back($newElement) { $newNode = new Node(); $newNode->data = $newElement; $newNode->next = null; $newNode->prev = null; if($this->head == null) { $this->head = $newNode; $newNode->next = $this->head; } else { $temp = new Node(); $temp = $this->head; while($temp->next !== $this->head) { $temp = $temp->next; } $temp->next = $newNode; $newNode->next = $this->head; $newNode->prev = $temp; $this->head->prev = $newNode; } } //count nodes in the list public function countNodes() { $temp = new Node(); $temp = $this->head; $i = 0; if ($temp != null) { $i++; $temp = $temp->next; } while($temp != $this->head) { $i++; $temp = $temp->next; } return $i; } //display the content of the list public function PrintList() { $temp = new Node(); $temp = $this->head; if($temp != null) { echo "The list contains: "; while(true) { echo $temp->data." "; $temp = $temp->next; if($temp == $this->head) break; } echo "\n"; } else { echo "The list is empty.\n"; } } }; // test the code $MyList = new 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 echo "No. of nodes: ".$MyList->countNodes(); ?>
The above code will give the following output:
The list contains: 10 20 30 40 No. of nodes: 4