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