By Pankaj Kumar
There are two ways to find the length of a linked list:
We will use the Linked list traversal to find the length of a linked list.
package com.journaldev.ds;
public class MyLinkedList {
public class Node {
int data;
Node next;
}
public Node head;
public Node tail;
public int size;
public int getFirst() throws Exception {
if (this.size == 0) {
throw new Exception("linked list is empty");
}
return this.head.data;
}
public int getLast() throws Exception {
if (this.size == 0) {
throw new Exception("linked list is empty");
}
return this.tail.data;
}
public void display() {
Node temp = this.head;
while (temp != null) {
System.out.println(temp.data + " ");
temp = temp.next;
}
}
public void addFirst(int item) {
Node nn = new Node();
nn.data = item;
if (this.size == 0) {
this.head = nn;
this.tail = nn;
this.size = this.size + 1;
} else {
nn.next = this.head;
this.head = nn;
this.size = this.size + 1;
}
}
public int length() {
Node temp = this.head;
int count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
public static void main(String[] args) {
MyLinkedList ll = new MyLinkedList();
ll.addFirst(10);
ll.addFirst(20);
ll.addFirst(30);
ll.addFirst(40);
ll.addFirst(50);
System.out.println("Length of Linked List is " + ll.length());
}
}
#include <stdio.h>
#include <stdlib.h>
/* A structure of linked list node */
struct node {
int data;
struct node *next;
} *head;
void initialize(){
head = NULL;
}
/*
Inserts a node in front of a singly linked list.
*/
void insert(int num) {
/* Create a new Linked List node */
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = num;
/* Next pointer of new node will point to head node of linked list */
newNode->next = head;
/* make new node as the new head of linked list */
head = newNode;
printf("Inserted Element : %d\n", num);
}
int getLength(struct node *head){
int length =0;
while(head != NULL){
head = head->next;
length++;
}
return length;
}
/*
Prints a linked list from head node till the tail node
*/
void printLinkedList(struct node *nodePtr) {
while (nodePtr != NULL) {
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf("-->");
}
}
int main() {
initialize();
/* Creating a linked List*/
insert(8);
insert(3);
insert(2);
insert(7);
insert(9);
printf("\nLinked List\n");
printLinkedList(head);
printf("\nLinked List Length : %d", getLength(head));
return 0;
}
Output
Base Case:
Recursive Case:
Example: There are 3 elements in the linked list: LL1, LL2, and LL3. We will Observe What happens in the Memory Stack when the Recursive Call is made. MEMORY STACK:
The main function calls LL1, LL1 calls LL2, LL2 calls LL3, LL3 calls null value. As Null value is reached, we return from here. 0 is returned to LL3, LL3 returns 1 to LL2, LL2 returns 2 to LL1. LL1 finally returns 3 to the main function.
package com.journaldev.ds;
public class MyLinkedList {
public class Node {
int data;
Node next;
}
public Node head;
public Node tail;
public int size;
public int getfirst() throws Exception {
if (this.size == 0) {
throw new Exception("linked list is empty");
}
return this.head.data;
}
public int RemoveFirst() throws Exception {
if (this.size == 0) {
throw new Exception("LL is empty");
}
Node temp = this.head;
if (this.size == 1) {
this.head = null;
this.tail = null;
size = 0;
} else {
this.head = this.head.next;
this.size--;
}
return temp.data;
}
public void addFirst(int item) {
Node nn = new Node();
nn.data = item;
if (this.size == 0) {
this.head = nn;
this.tail = nn;
this.size = this.size + 1;
} else {
nn.next = this.head;
this.head = nn;
this.size = this.size + 1;
}
}
public int lengthUsingRecursiveApproach (){
return lengthUsingRecursiveApproach(this.head);
}
private int lengthUsingRecursiveApproach(Node curr) {
// TODO Auto-generated method stub
if (curr == null) {
return 0;
}
return 1 + lengthUsingRecursiveApproach (curr.next);
}
public static void main(String[] args) {
MyLinkedList ll = new MyLinkedList();
// insert elements into the Linked List
ll.addFirst(10);
ll.addFirst(20);
ll.addFirst(30);
ll.addFirst(40);
ll.addFirst(50);
// Length of List
System.out.println("Recursive Approach length " + ll.lengthUsingRecursiveApproach(ll.head));
}
}
#include <stdio.h>
struct Node
{
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
/* link the old list of the new node */
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int getCount(struct Node* head)
{
// Base case
if (head == NULL)
return 0;
return 1 + getCount(head->next);
}
int main()
{
struct Node* head = NULL;
push(&head, 1);
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 1);
printf("count of nodes is %d", getCount(head));
return 0;
}
Output
O(N) in both the recursive and iterative solution, as all we need, is a single traversal to know the length.
Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.
Java and Python Developer for 20+ years, Open Source Enthusiast, Founder of https://www.askpython.com/, https://www.linuxfordevices.com/, and JournalDev.com (acquired by DigitalOcean). Passionate about writing technical articles and sharing knowledge with others. Love Java, Python, Unix and related technologies. Follow my X @PankajWebDev
Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.
Full documentation for every DigitalOcean product.
The Wave has everything you need to know about building a business, from raising funding to marketing your product.
Stay up to date by signing up for DigitalOcean’s Infrastructure as a Newsletter.
New accounts only. By submitting your email you agree to our Privacy Policy
Scale up as you grow — whether you're running one virtual machine or ten thousand.
Sign up and get $200 in credit for your first 60 days with DigitalOcean.*
*This promotional offer applies to new accounts only.