Find the Length of a Linked List

Introduction

Linked lists are fundamental data structures used in computer science and programming to organize and store data. One common operation when working with linked lists is finding the length of the list. In this blog, we’ll delve into the concept of linked lists, explore how they work, and understand different approaches to find the length of a linked list. We’ll keep things simple and provide plenty of examples to make the learning experience enjoyable.

What is a Linked List?

A linked list is a data structure consisting of a sequence of elements, where each element points to the next one in the sequence. Unlike arrays, linked lists do not have a fixed size, allowing for dynamic memory allocation. The basic building blocks of a linked list are nodes, and each node contains data and a reference (or link) to the next node in the sequence.

Let’s visualize a simple linked list:

Node 1        Node 2        Node 3
+------+      +------+      +------+
| Data | ---> | Data | ---> | Data |
+------+      +------+      +------+
| Next |      | Next |      | Next | --> NULL
+------+      +------+      +------+

Here, each node holds data (the actual information you want to store) and a reference to the next node. The last node typically points to NULL, indicating the end of the list.

Finding the Length of a Linked List

The length of a linked list is the number of nodes it contains. There are multiple ways to calculate this, each with its own advantages and considerations. We’ll explore two common approaches: iterative and recursive.

Iterative Approach

In the iterative approach, we traverse the linked list from the beginning to the end, counting the nodes as we go along. Here’s a simple algorithm in pseudo-code:

function findLengthIterative(head):
    length = 0
    current = head

    while current is not NULL:
        length = length + 1
        current = current.next

    return length

Let’s break this down step by step. We start at the head of the linked list (head) and initialize a counter (length) to zero. We then iterate through the list, incrementing the counter for each node, until we reach the end (NULL).

Example:

Consider the following linked list:

1 -> 2 -> 3 -> 4 -> NULL

Let’s apply the iterative approach:

1. Start at the head (1), set length to 0.
2. Move to the next node (2), increment length to 1.
3. Move to the next node (3), increment length to 2.
4. Move to the next node (4), increment length to 3.
5. Reach the end (NULL), exit the loop.

The length of the linked list is 3.

Recursive Approach

The recursive approach involves defining the length of the linked list in terms of the length of the rest of the list. Here’s a recursive algorithm in pseudo-code:

function findLengthRecursive(node):
    if node is NULL:
        return 0
    else:
        return 1 + findLengthRecursive(node.next)

In this approach, we check if the current node is NULL. If it is, we return 0 (base case). Otherwise, we add 1 (for the current node) to the length of the rest of the list.

Example:

Let’s use the same linked list as before:

1 -> 2 -> 3 -> 4 -> NULL

Applying the recursive approach:

1. Start at the head (1).
2. Call findLengthRecursive with the current node (1).

• Check if 1 is NULL (no).
• Return 1 + findLengthRecursive(2). Now, the focus shifts to the next node (2).

1. Call findLengthRecursive with the current node (2).

• Check if 2 is NULL (no).
• Return 1 + findLengthRecursive(3). Again, shift focus to the next node (3).

1. Call findLengthRecursive with the current node (3).

• Check if 3 is NULL (no).
• Return 1 + findLengthRecursive(4). Shift focus to the next node (4).

1. Call findLengthRecursive with the current node (4).

• Check if 4 is NULL (no).
• Return 1 + findLengthRecursive(NULL). Now, findLengthRecursive(NULL) returns 0 (base case).

1. Substituting values back:

• 1 + (1 + (1 + (1 + 0))) = 4

The length of the linked list is 4.

Practical Implementation

Let’s implement both the iterative and recursive approaches in a programming language, say Python, to solidify our understanding.

Python Implementation

Iterative Approach:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def find_length_iterative(head):
    length = 0
    current = head

    while current is not None:
        length += 1
        current = current.next

    return length

# Example usage:
# Create a linked list: 1 -> 2 -> 3 -> NULL
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

print(find_length_iterative(head))  # Output: 3

Recursive Approach:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def find_length_recursive(node):
    if node is None:
        return 0
    else:
        return 1 + find_length_recursive(node.next)

# Example usage:
# Create a linked list: 1 -> 2 -> 3 -> NULL
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

print(find_length_recursive(head))  # Output: 3

Conclusion

Understanding how to find the length of a linked list is a fundamental skill for any programmer. In this blog, we explored the concept of linked lists, their structure, and two common approaches to determine their length: iterative and recursive. We backed up the theoretical knowledge with practical implementations in Python, providing examples for better comprehension.

As you continue your journey in programming, remember that linked lists are just one of many data structures, each with its own strengths and use cases. The ability to choose the right data structure for a given problem is a crucial skill, and mastering linked lists is an essential step in that direction.

Keep coding and exploring the fascinating world of data structures and algorithms!

Read More-

Delete the node with value X of a Linked List – https://kamleshsingad.com/delete-the-node-with-value-x-of-a-linked-list/

Delete the kth element of a Linked List – https://kamleshsingad.com/delete-the-kth-element-of-a-linked-list/

Search an element in a Linked List – https://kamleshsingad.com/search-an-element-in-a-linked-list/