Length of a linked list

Find the length of the given input linked list.

Example

Time complexity : O(n)

Method 1

Algorithm

a. Initialize the length as 0.

b. Traverse in the array, node pointer (current) at head

c. Until current is not NULL, current = current -> next and length = length + 1.

d. Return the final length.

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //If this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}
 
// function to get the length of linked list
int getLength(struct LLNode* head)
{
    int length = 0;  // Initialize length
    struct LLNode* current = head;  // Initialize current
    while (current != NULL)
    {
        length++;
        current = current->next;
    }
    return length;
}
 
//Main function
int main()
{
    struct LLNode* head = NULL;//Initial list has no elements
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);           
    
    cout<<"Input linked list is: ";
    display(&head);
    
    cout<<"length of linked list is: "<<getLength(head);
    return 0;
}
Try It

Time complexity : O(logn)

Method 2

Algorithm

We use recursive method here,

a. If head is NULL, return 0

b. Else, return 1 + count(head->next)

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //If this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}
 
// function to get the length of linked list
int getLength(struct LLNode* head)
{
    //if head is null length is 0 
    if (head == NULL)
    {
        return 0;
    }
    //Recursion
    return 1 + getLength(head->next);
}
 
//Main function
int main()
{
    struct LLNode* head = NULL;//Initial list has no elements
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);           
    
    cout<<"Input linked list is: ";
    display(&head);
    
    cout<<"length of linked list is: "<<getLength(head);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top