Find length of Doubly Linked List

This is basic problem how to count length of doubly linked list. We can solve this problem using by linked list traversal.

Process: Use one counter integer variable, and use one Linked list pointer which that is point to front node of linked list. and iterate one by one nodes of this linked list and increment counter value one by one. When this pointer are NULL then stop execution process and display counter value. Time complexity of this process are O(n). n is number of linked list nodes.

Suppose we are inserted the following (4, 3, 2, 5, 3) node in a sequence.

Find length of doubly linked list

Here given code implementation process.

//C Program
//Find the length of doubly linked list
#include <stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node
{
  int data;
  struct Node*next;
  struct Node*prev;
};


//insert Node element of end of linked list
void insert(struct Node**head,int value)
{

  //Create a dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL)
  {
    printf("Memory overflow\n");
  }
  else
  {
    //set data value
    node->data=value;
    node->next=NULL;
    node->prev=NULL;
    if(*head==NULL)
    {
      *head=node;
    }
    else
    {
      struct Node*temp=*head;
        //find last node
      while(temp!=NULL && temp->next!=NULL)
      {
        temp=temp->next;
      }
        //add new node to last positions
      temp->next=node;
      node->prev=temp;

    }
  }
}
//display element of Node
void display(struct Node*temp)
{

  if(temp==NULL)
  {
    printf("Empty linked list");
  }
  else
  {
    printf("\nLinked List Elements :");

    //Traverse doubly linked list from front to rear
    while(temp!=NULL)
    {
      //print node value
      printf("%d  ",temp->data);
      temp=temp->next;
    }
  }

}
//count length of doubly linked list
void  length_count(struct Node*temp)
{
  if(temp!=NULL)
  {

    int counter=0;
      //get remove node
    while(temp!=NULL)
    {
      temp=temp->next;
      counter++;
    }
    printf("\nLength  %d\n",counter);


  }else
  {
    //when linked list is empty
    printf("Empty linked list");

  }
}

int main()
{
  //set node pointer value
  struct Node*head=NULL;
  //Insert element of linked list
  insert(&head,4);
  insert(&head,3);
  insert(&head,2);
  insert(&head,5);
  insert(&head,3);



  //display all node
  display(head);

  length_count(head);
  return 0;
}

Output

Linked List Elements :4  3  2  5  3  
Length  5
//C++ Program
//Find the length of doubly linked list
#include <iostream> 
using namespace std;
//create structure
struct Node
{
  int data;
  Node*next;
  Node*prev;
};
class DoublyList
{
  struct Node*head;
public:
  DoublyList();
  void insert(int);
  void display();
  void length_count();
};
//set inital value
DoublyList::DoublyList()
{
  head=NULL;
}

//insert a linked list Node element
void DoublyList:: insert(int value)
{
  //Create a dynamic node
  Node*node=new Node;
  if(node==NULL)
  {
    cout<<"Memory overflow\n";
  }
  else
  {
    //set data value
    node->data=value;
    node->next=NULL;
    node->prev=NULL;
    if(head==NULL)
    {
      head=node;
    }else
    {
      Node*temp=head;
      //find last node
      while(temp!=NULL && temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add new node to last positions
      temp->next=node;
      node->prev=temp;

    }
  }
}
//display all element of doubly linked list
void DoublyList::display()
{

  if(head==NULL)
  {
    //when linked list is empty
    cout<<"Empty linked list";
  }
  else
  {
    cout<<"Linked List Element :";
    Node*temp=head;
    while(temp!=NULL)
    {
      //display node elemement
      cout<<" "<<temp->data;
      temp=temp->next;
    }
  }

}
//count length of doubly linked list
void  DoublyList:: length_count()
{
  if(head==NULL)
  {
    //when linked list is empty
    cout<<"Empty linked list";
  }
  else
  {
    struct Node*temp=head;
    int counter=0;
      //get remove node
    while(temp!=NULL)
    {
      temp=temp->next;
      counter++;
    }
    cout<<"\nLength "<<counter<<endl;


  }
}

int main()
{
  DoublyList obj=DoublyList();

  //Insert element of linked list
  obj.insert(4);
  obj.insert(3);
  obj.insert(2);
  obj.insert(5);
  obj.insert(3);
  obj.display();
  obj.length_count();
  return 0;
}

Output

Linked List Element : 4 3 2 5 3
Length 5
//Java program
//Find the length of doubly linked list
class Node
{
  public int data;
  public Node next,prev;
}
public class LinkedList
{


  //head of linked list
  public Node head;
  //Class constructors
  LinkedList()
  {
    head=null;
  } 
  //add newly created node at End of linked list
  public void insert(int value)
  {
        //Create a dynamic node
    Node node=new Node();
        //add node value and pointer value
    node.data=value;
    node.next=null;
    node.prev=null;
        //when no element
    if(head==null) head=node;
    else
    {
      Node temp=head;
          //find last node
      while(temp.next!=null) temp=temp.next;
          //add node
      node.prev=temp;
      temp.next=node;
    }
  }
    //display all Linked List node value
  public void display()
  {
    if(head!=null)
    {
      System.out.print(" Linked List Element :");
      Node temp=head;
      while(temp!=null)
      {
                //display node value
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
    }
    else
    {
      System.out.println("Empty Linked list"); 
    }
  }
      //count length of doubly linked list
  public void  lengthCount()
  {
    if(head==null)
    {
      //when linked list is empty
      System.out.println("Empty linked list");
    }
    else
    {
      Node temp=head;
      int counter=0;
      //get remove node
      while(temp!=null)
      {
        temp=temp.next;
        counter++;
      }
      System.out.println("\n Length "+counter);


    }
  }


  public static void main(String[] args) 
  {

    LinkedList obj=new LinkedList();


    //Insert element of linked list
    obj.insert(4);
    obj.insert(3);
    obj.insert(2);
    obj.insert(5);
    obj.insert(3);

    //display all node
    obj.display();

    obj.lengthCount();

  }
}

Output

 Linked List Element :  4  3  2  5  3
 Length 5
Find the length of doubly linked list
#Python Program
#Find the length of doubly linked list
class Node:
  def __init__(self,data):
    self.data=data
    self.next=None
    self.prev=None

#create class LinkedList    
class LinkedList:
  def __init__(self):
    #set initial head value
    self.head=None


  #insert new node to end of Linked List  
  def insert(self,data):
    #make a new node
    node=Node(data)

    if(self.head==None):
      #when empty list
      self.head=node
    else:
      temp=self.head
      #find last node
      while temp.next!=None:
          temp=temp.next
      #add node    
      temp.next=node
      node.prev=temp
  #find length   
  def lengthCount(self):
      if self.head==None:
        print("Linked List Empty : ")
      else:
        temp=self.head
        counter=0
        while temp!=None:
          temp=temp.next
          counter+=1
        print("Length : ",counter)

  #view all node values    
  def display(self):
    if self.head==None:
      print("Linked List Empty : ")
      return
    temp=self.head
    print("Linked List Elements : ")

    while(temp!=None):
      #print node value
      print(temp.data,end=" ")
      temp=temp.next
    print("\n")
def main():

    #Create Object of class LinkedList
    obj=LinkedList()
   
    #Insert element of linked list
    obj.insert(4);
    obj.insert(3);
    obj.insert(2);
    obj.insert(5);
    obj.insert(3);
    #display all node
    obj.display();

    obj.lengthCount();
  

if(__name__=="__main__"):
    main()

Output

Linked List Elements : 
4 3 2 5 3 

Length :  5
//C# program
//Find the.Length of doubly linked list
using System;
public class Node
{
  public int data;
  public Node next,prev;
}
public class LinkedList
{


  //head of linked list
  public Node head;
  //Class constructors
  LinkedList()
  {
    head=null;
  } 
  //add newly created node at End of linked list
  public void insert(int value)
  {
    //Create a dynamic node
    Node node=new Node();
    //add node value and pointer value
    node.data=value;
    node.next=null;
    node.prev=null;
    //when no element
    if(head==null) head=node;
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null) temp=temp.next;
      //add node
      node.prev=temp;
      temp.next=node;
    }
  }
  //display all Linked List node value
  public void display()
  {
    if(head!=null)
    {
      Console.Write(" Linked List Element :");
      Node temp=head;
      while(temp!=null)
      {
        //display node value
        Console.Write("  "+temp.data);
        temp=temp.next;
      }
    }
    else
    {
      Console.WriteLine("Empty Linked list"); 
    }
  }
  //count.Length of doubly linked list
  public void lengthCount()
  {
    if(head==null)
    {
      //when linked list is empty
      Console.WriteLine("Empty linked list");
    }
    else
    {
      Node temp=head;
      int counter=0;
      //get remove node
      while(temp!=null)
      {
        temp=temp.next;
        counter++;
      }
      Console.WriteLine("\n.Length "+counter);


    }
  }


  public static void Main(String[] args) 
  {

    LinkedList obj=new LinkedList();


    //Insert element of linked list
    obj.insert(4);
    obj.insert(3);
    obj.insert(2);
    obj.insert(5);
    obj.insert(3);

    //display all node
    obj.display();

    obj.lengthCount();

  }
}

Output

Linked List :  4  3  2  5  3
Length 5
<?php
//Php program 
//Find the length of doubly linked list
class Node
{
  public $data;
  public $next;
  public $perv;
  function __construct($data)
  {
    $this->data = $data;
    $this->next = NULL;
    $this->prev = NULL;
  }
}
class LinkedList
{

  private $head;
  function __construct()
  {
    $head=NULL;
  }
  /*
  * Append the Given data value at Beginning of linked list
  * Fun : insert
  * Parm: data value
  *@return None
  */
  function insert($data)
  {
    //Create a dynamic node
    $node=new Node($data);
    if($node==NULL)
    {
      echo "Memory overflow\n";
    }
    else
    {
      if($this->head==NULL)
      {
        $this->head=$node;
      }
      else
      {
        $temp=$this->head;
        //find last node
        while($temp!=NULL && $temp->next!=NULL)
        {
          $temp=$temp->next;
        }
        //add new node to last positions
        $temp->next=$node;
        $node->prev=$temp;

      }
    }
  }
    //Display all inserted node in linked list
  function display()
  {
    if($this->head==NULL)
    {
      echo "Empty Linked List";
    }
    else
    {
      $temp=$this->head;
      echo "Doubly Linked List :";
      while($temp!=NULL)
      {
        //display node value
        echo "  ".$temp->data;
        $temp=$temp->next; //visit to next node
      }
    }   
  }
  //count length of doubly linked list
  public function  length_count()
  {
    if($this->head==NULL)
    {
      //when linked list is empty
      echo "Empty linked list";
    }
    else
    {
      $temp=$this->head;
      $counter=0;
      //get remove node
      while($temp!=NULL)
      {
        $temp=$temp->next;
        $counter++;
      }
      echo "\nLength ".$counter."\n";


    }
  }
}
function main()
{
  //Make a object of LinkedList class
  $obj= new LinkedList();


  //Insert element of linked list
  $obj->insert(4);
  $obj->insert(3);
  $obj->insert(2);
  $obj->insert(5);
  $obj->insert(3);
  $obj->display();
  $obj->length_count();
}
main();
?>

Output

Doubly Linked List :  4  3  2  5  3
Length 5

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved