# 5 Best Ways to Determine the Length of a Linked List in Python

Rate this post

π‘ Problem Formulation: When working with linked lists in Python, a common problem is determining the number of elements it contains. This is especially crucial in environments where the linked list size directly impacts performance or available memory resources. For example, if you have a linked list `my_linked_list`, you might want to know if it contains 10 or 1000 nodes.

## Method 1: Iterative Approach

This method involves traversing the linked list from the head to the end, incrementing a counter at each node until the list is fully traversed. This operation has a time complexity of O(n), where n is the number of nodes in the linked list. It’s straightforward and easy to understand.

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

Output: 3

This method involves defining a Node class to represent each element in the linked list and a function `linked_list_length()` that traverses the list. The function starts at the head of the linked list and traverses until it reaches a node that points to None, incrementing a counter for each node visited. This method is simple and doesn’t require any extra data structures to hold intermediate results.

## Method 2: Recursive Approach

The recursive approach involves defining a function that calls itself with the next node of the list until it reaches the end. Each call adds 1 to the result of the subsequent call, finally resulting in the total length of the linked list. This method could lead to a stack overflow for very long lists due to deep recursion.

Here’s an example:

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

if node is None:
return 0
else:

Output: 3

In this recursive version, the function `linked_list_length_recursive()` returns 0 when the end of the list is reached. If the node exists, it returns 1 plus the length of the rest of the list. This continues until the base case (node is None) is encountered, at which point all calls resolve, returning the total length.

## Method 3: Using a Wrapper Class

A wrapper class around the linked list can be used to keep track of the length automatically whenever nodes are added or removed. The class maintains a length attribute that stores the current number of nodes, eliminating the need to traverse the list to count the nodes each time.

Here’s an example:

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

def __init__(self):
self.length = 0

def append(self, data):
else:
while current.next:
current = current.next
current.next = Node(data)
self.length += 1

def get_length(self):
return self.length

# Example usage

Output: 3

The `LinkedList` class encapsulates the linked list functionality. The `append()` method provides the way to add new nodes and updates the length accordingly. The `get_length()` method simply returns the value of the length attribute. This method provides constant-time access to the list’s length but requires careful updating of the length attribute throughout the class implementation.

## Method 4: Using Standard Python Features

This approach leverages standard Python features like the magic method `__len__()` implemented within a custom linked list class. This method can provide a more Pythonic way to obtain the length by leveraging the `len()` function, similar to how it’s used with native Python data types.

Here’s an example:

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

def __init__(self):

def append(self, data):
else:
while current.next:
current = current.next
current.next = Node(data)

def __len__(self):
count = 0
while current:
count += 1
current = current.next
return count

# Example usage

Output: 3

The `LinkedList` now includes the `__len__()` method, which Python automatically calls when the built-in `len()` function is used on an instance of the class. As with other iterable Python objects, this allows for an intuitive and familiar way to access the size of the linked list.

## Bonus One-Liner Method 5: Using the Generators

Python’s generator functions can offer a concise way to iterate over objects such as linked lists without creating an explicit loop. This is a more advanced and Pythonic way to count elements that may be preferrable in certain contexts.

Here’s an example:

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

def node_generator(current_node):
while current_node:
yield current_node
current_node = current_node.next

The generator function `node_generator()` yields nodes one by one from a starting node. The expression `sum(1 for _ in node_generator(head))` takes advantage of Python’s generator expressions and the `sum()` function to count the nodes without storing the entire list or its elements.
• Method 4: Using Standard Python Features. Offers a Pythonic way to use the `len()` function with custom objects. Compatible with Python’s existing conventions.