5 Best Ways to Find the Length of a Linked List in Python Without Using Recursion

Rate this post

πŸ’‘ Problem Formulation: In this article, we’ll address a common challenge in data structures: determining the length of a singly linked list without utilizing recursion. Linked lists are fundamental structures that lack a built-in length property, so devising methods to ascertain their size is crucial. If our linked list is 3 -> 4 -> 2 -> 7 -> None, our goal is to output the length as 4.

Method 1: Iterative Approach

The iterative approach involves traversing the linked list from the head node to the end node while maintaining a count of nodes visited. The function iterates over the list using a while loop, incrementing the count until the end of the list is reached. This method is straightforward and does not require additional memory aside from the counter variable.

Here’s an example:

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

def find_length(head):
    count = 0
    current = head
    while current:
        count += 1
        current = current.next
    return count

# Sample Linked List Creation
head = Node(3)
head.next = Node(4)
head.next.next = Node(2)
head.next.next.next = Node(7)

# Find length of the linked list
print(find_length(head))

Output: 4

The code snippet defines a simple Node class and includes a find_length function, which measures the length of the list by iterating through each element until it reaches the end. This loop ensures that each node is counted exactly once, providing an accurate length without using additional memory for recursion stacks.

Method 2: Using a Counter Object

By encapsulating the count in an object, we can track the length throughout the linked list traversal. A counter object can be a simple wrapper around an integer that is passed by reference, enabling the count to persist and increase as the list is traversed.

Here’s an example:

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

class Counter:
    def __init__(self):
        self.count = 0

def find_length(head, counter):
    current = head
    while current:
        counter.count += 1
        current = current.next
    return counter.count

# Sample Linked List Creation
head = Node(3)
head.next = Node(4)
head.next.next = Node(2)
head.next.next.next = Node(7)

# Find length using a Counter object
counter = Counter()
print(find_length(head, counter))

Output: 4

The code demonstrates an alternative iterative method using a custom Counter class, which retains the count as its current attribute. This may be overengineering for this simple task but can be useful if additional functionality associated with counting is needed.

Method 3: Using a List Comprehension

Taking advantage of Python’s list comprehension feature, we can create a list of ones representing each node in the linked list and then sum them up to get the length. This method is concise but not memory-efficient, as it requires storing a list of the same length as the linked list.

Here’s an example:

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

def find_length(head):
    return sum([1 for node in iter_nodes(head)])

def iter_nodes(head):
    current = head
    while current:
        yield current
        current = current.next

# Sample Linked List Creation
head = Node(3)
head.next = Node(4)
head.next.next = Node(2)
head.next.next.next = Node(7)

# Find length of the linked list using list comprehension
print(find_length(head))

Output: 4

This snippet includes a generator function iter_nodes() that yields each node of the list, along with a succinct list comprehension within the find_length() function that sums up 1 for each node given by the generator. It’s a more Pythonic approach but uses extra space to store temporary lists.

Method 4: Using the Collection’s Counter

Python’s Collections module offers a Counter class designed for fast tallying of hashable objects. By iterating over the nodes and using None as a common object to count, we can determine the length of the list in just two lines of code.

Here’s an example:

from collections import Counter

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

def find_length(head):
    return Counter(node is not None for node in iter_nodes(head))[True]

def iter_nodes(head):
    current = head
    while current:
        yield current
        current = current.next

# Sample Linked List Creation
head = Node(3)
head.next = Node(4)
head.next.next = Node(2)
head.next.next.next = Node(7)

# Find length of the linked list using Collections Counter
print(find_length(head))

Output: 4

In this code, the iter_nodes() generator is used along with a Collections Counter to tally the presence of nodes. This is a trick to reduce looping code, but it’s not the most intuitive way to count nodes, and like the list comprehension, it accumulates counts in a data structure.

Bonus One-Liner Method 5: Using itertools and sum

Lastly, Python’s itertools module provides a memory-efficient way to handle iterators. Using the itertools’s count function with sum, we can find the length in a single, albeit not very readable, line of code.

Here’s an example:

import itertools

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

def find_length(head):
    return sum(1 for _ in itertools.takewhile(lambda x: x, iter_nodes(head)))

def iter_nodes(head):
    current = head
    while current:
        yield current
        current = current.next

# Sample Linked List Creation
head = Node(3)
head.next = Node(4)
head.next.next = Node(2)
head.next.next.next = Node(7)

# Find length of the linked list in one line 
print(find_length(head))

Output: 4

This method employs the takewhile() function from the itertools module, which takes an iterator and a predicate and yields elements from the iterator as long as the predicate is true. The result is summed, counting the length of the list in a memory-efficient and concise manner. It’s elegant but less readable for beginners.

Summary/Discussion

  • Method 1: Iterative Approach. Strengths: Simple and straightforward, no additional memory usage. Weaknesses: Generic, not Python-specific.
  • Method 2: Counter Object. Strengths: Could extend for more complex counting logic. Weaknesses: Overkill for simple counting tasks.
  • Method 3: List Comprehension. Strengths: Pythonic and readable. Weaknesses: Inefficient with memory for large lists.
  • Method 4: Collection’s Counter. Strengths: Quick and compact. Weaknesses: Unintuitive and memory-intensive for the task.
  • Method 5: Bonus One-Liner Using itertools. Strengths: Memory-efficient and slick. Weaknesses: Readability could be a concern.