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

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

# Example usage
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
print_alternate_nodes(head)

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

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

# Example usage
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
print_alternate_nodes(head)

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

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

# Example usage
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
print_alternate_nodes(head)

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

def node_generator(head):
    while head:
        yield head.data
        head = head.next

# Example usage
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
print(*islice(node_generator(head), None, None, 2))

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.