# Alternating Node Values: Traversing Linked Lists in Python without Recursion

Rate this post

π‘ Problem Formulation: Consider a singly linked list where each node has a single reference to the next node. The goal is to print the data from every alternate node starting with the first node, without using recursion. For instance, given a linked list 1 -> 2 -> 3 -> 4 -> 5, the desired output would be 1, 3, 5.

## Method 1: Iterative Traversal with a Counter

This method involves traversing the linked list using a loop with a counter that keeps track of the node position. When the counter is even, the node’s data is printed. This method is straightforward, requiring only basic knowledge of loops and conditionals.

Here’s an example:

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

count = 0
while current:
if count % 2 == 0:
print(current.data)
current = current.next
count += 1

# Example usage
```

Output:

```1
3
5
```

This code snippet creates a simple linked list with five nodes and prints the data of every alternate node starting from the head. The `print_alternate_nodes` function iteratively traverses the linked list while incrementing a counter to keep track of the current position, printing the data of nodes at even positions.

## Method 2: Boolean Toggle

A boolean toggle can be used to control the printing of nodes during iteration. The boolean value is flipped at each node, causing every other node to be printed. This method reduces the need for a counter variable.

Here’s an example:

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

toggle = True
while current:
if toggle:
print(current.data)
toggle = not toggle
current = current.next

# Example usage
```

Output:

```1
3
5
```

The boolean `toggle` starts as `True` and is negated at each iteration, ensuring that the `print` statement is executed for every alternate node, resulting in a concise and elegant solution.

## Method 3: Using Single Loop with Index Variable

This method leverages the direct access to the next nodeβs reference in a singly linked list. Instead of a counter or toggle, it simply jumps to the next of the next node in a single loop, thus printing every other node.

Here’s an example:

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

while current:
print(current.data)
if current.next is not None:
current = current.next.next
else:
break

# Example usage
```

Output:

```1
3
5
```

In this code snippet, by advancing the `current` pointer to `current.next.next`, the program effectively skips every second node, therefore achieving the task with minimal code and no auxiliary variables.

## Bonus One-Liner Method 4: Generator Expression with Itertools

While not strictly without advanced techniques, using Python’s built-in itertools library and a generator could provide a concise one-liner solution. Note that itertools is not a form of recursion but a Pythonic way to handle iterators.

Here’s an example:

```from itertools import islice

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

# Example usage
```

Output:

```1 3 5
```

This advanced one-liner uses `islice` from the `itertools` module to slice the generator that yields nodes from the linked list. The third parameter of `islice` specifies the step, which is set to 2 to skip every alternate node.

## Summary/Discussion

• Method 1: Iterative Traversal with a Counter. Straightforward and intuitive. The need for a counter variable can be seen as an overhead.
• Method 2: Boolean Toggle. Simpler than Method 1. Flipping a boolean is less overhead than incrementing a counter, but the difference is minor.
• Method 3: Using Single Loop with Index Variable. Most direct approach without any extra variables. It requires careful handling to avoid IndexError in case of a list with an odd number of elements.
• Method 4: Generator Expression with Itertools. The most Pythonic and elegant, though it’s less intuitive for beginners. The dependency on the itertools library means it’s not the most elementary solution.