Friday, May 24, 2013

Finding the length of a linked list

In this post we will see an algorithm to find the length of the linked list. Here singly linked list is implemented in Object Oriented Programming (OOP) paradigm in C++. The algorithm is very simple. Just start at the beginning of the linked list, move to next until you reach the end of the list, incrementing a counter in each iteration. Following is the source C++ code for the same.


#include <iostream>

using namespace std;

//Node definition for a single linked list
class SLLNode
{
 private:
  //data member
  int data;
  //pointer to next node in the linked list
  SLLNode *nextPtr;
 
 public:
  
  //Single argument constructor
  //initializes data with d, next pointer to NULL
  SLLNode(int d):data(d),nextPtr(NULL)
  {
  }
  //to initialize both members
  SLLNode(int d,SLLNode* next):data(d),nextPtr(next)
  {   
  }
  //returns the data
  int getData()
  {
   return data;
  }
  //sets the data
  void setData(int d)
  {
   this->data = d;
  }
  //gets the next pointer
  SLLNode* getNext()
  {
   return this->nextPtr;
  }
  //sets the next pointer
  void setNext(SLLNode *ptr)
  {
   this->nextPtr = ptr;
  }
};

//defines the actual single linked list
class SinglyLinkedList
{
 private:
  //maintain two pointers to the start and the end
  //so that we can append at the end easily (constant time complexity)
  SLLNode * head;
  SLLNode * tail;
 public:
  SinglyLinkedList()
  {
   head = NULL;
   tail = NULL;
  }
  //adds the node to the end of the list
  void appendNode(SLLNode* ptr)
  {
   //check if list is empty
   if( head == NULL)
   {
    //update both the pointers
    head = tail = ptr;
   }
   else //simply append at the end, and move the tail pointer
   {
    tail->setNext(ptr);
    tail = tail->getNext();
   }
  }
  //gets the length of the list
  int getLength()
  {
   int length = 0;
   
   SLLNode* ptr = head;
   
   while ( ptr != NULL )
   {
    length++;
    ptr = ptr->getNext();
   }
   return length;
  }
};

int main()
{
 SinglyLinkedList list;
 list.appendNode(new SLLNode(1));
 list.appendNode(new SLLNode(2));
 list.appendNode(new SLLNode(3));
 list.appendNode(new SLLNode(4));
 cout<<"Length: "<<list.getLength()<<endl;
 return 0;
}