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

count = 0
while current:
count += 1
current = current.next
return count

# Find length of the linked list
```

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

while current:
counter.count += 1
current = current.next
return counter.count

# Find length using a Counter object
counter = 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

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

while current:
yield current
current = current.next

# Find length of the linked list using list comprehension
```

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

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

while current:
yield current
current = current.next

# Find length of the linked list using Collections Counter
```

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

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

while current:
yield current
current = current.next

# Find length of the linked list in one line
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.