PHP Data Structures - Circular Singly Linked List Other Related Topics

PHP - Count nodes in the Circular Singly Linked List



Counting nodes in a circular singly 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 singly 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 singly linked list.

<?php
//node structure
class Node {
  public $data;
  public $next;
}

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; 
    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;
    }    
  }

  //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