5 Best Ways to Create a Circular Linked List in Python and Display it in Reverse

Rate this post

πŸ’‘ Problem Formulation: The task is to implement a circular linked list with n nodes using Python, and then to display this list in reverse order. A circular linked list is a sequence of nodes in which every node points to the next node and the last node points back to the first node. If the input is n = 4, with node values 10, 20, 30, 40, the desired output is 40, 30, 20, 10.

Method 1: Iterative Reversal

This method involves iterating over the linked list and reversing the links as we proceed. The reversing process changes the direction of the links such that each node’s next pointer points to the previous node. Due to the circular nature of the list, extra care must be taken to handle the last node correctly to avoid infinite loops.

Here’s an example:

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

def circular_linked_list(n):
    head = current = Node(1)
    for i in range(2, n + 1):
        current.next = Node(i)
        current = current.next
    current.next = head
    return head

def display_reversed(head):
    prev = None
    current = head
    next_node = current.next
    while next_node != head:
        current.next = prev
        prev = current
        current = next_node
        next_node = next_node.next
    current.next = prev
    head = current
    while True:
        print(head.data, end=' ')
        head = head.next
        if head == current:
            break

head = circular_linked_list(4)
display_reversed(head)

Output:

4 3 2 1

In the code snippet, we define a Node class and two functions: circular_linked_list to create the list, and display_reversed to reverse and display it. The reversal is done iteratively, working our way through the list and reversing links between nodes. After reversal, the list is traversed once to print the data in reverse order.

Method 2: Using a Stack

This method employs a stack to reverse the circular linked list. We traverse the list once and push each node onto the stack. Then, we pop nodes from the stack and print their values, which inherently reverses the order of the nodes.

Here’s an example:

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

def circular_linked_list(n):
    head = current = Node(1)
    for i in range(2, n + 1):
        current.next = Node(i)
        current = current.next
    current.next = head
    return head

def display_reversed(head):
    stack = []
    current = head
    while True:
        stack.append(current.data)
        current = current.next
        if current == head:
            break
    while stack:
        print(stack.pop(), end=' ')

head = circular_linked_list(4)
display_reversed(head)

Output:

4 3 2 1

The code snippet demonstrates the creation of a circular linked list and its reversal using a stack data structure. Each node’s data is pushed onto the stack. Popping elements from the stack and printing them results in the reversed list.

Method 3: Recursive Display

This method implements a recursive strategy to print the nodes of a circular linked list in reverse. The recursion ends when the entire list has been traversed; each call prints the current node’s data after making the recursive call, thus achieving the reverse order display.

Here’s an example:

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

def circular_linked_list(n):
    head = current = Node(1)
    for i in range(2, n + 1):
        current.next = Node(i)
        current = current.next
    current.next = head
    return head

def display_reversed_recursive(current, head):
    if current.next != head:
        display_reversed_recursive(current.next, head)
    print(current.data, end=' ')

head = circular_linked_list(4)
display_reversed_recursive(head, head)

Output:

4 3 2 1

The code snippet showcases how recursion is used to display a circular linked list in reverse. By recursively calling display_reversed_recursive before printing the node’s value, the function stack maintains the reverse order, and nodes are printed from last to first when the function stack unwinds.

Method 4: Reversing Using List Comprehension

This method uses Python’s list comprehension and the power of Python’s sequence slicing to reverse the list. We extract the data from the nodes into a list, reverse this list using slicing, and then print the reversed order. It combines creating the list and reversing it in a condensed form.

Here’s an example:

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

def circular_linked_list(n):
    head = current = Node(1)
    for i in range(2, n + 1):
        current.next = Node(i)
        current = current.next
    current.next = head
    return head

def display_reversed(head):
    print(' '.join(str(data) for data in [node.data for node in iter(lambda: head.next, head)][::-1]))

head = circular_linked_list(4)
display_reversed(head)

Output:

4 3 2 1

This code snippet creates a circular linked list and then utilizes Python list comprehension to extract the data from the nodes into a list. The list is then reversed with slicing and printed. The process is compact but quite powerful and pythonic, showcasing Python’s concise syntax capabilities.

Bonus One-Liner Method 5: Using Generators

The bonus method provides a one-liner approach by combining Python’s generator expressions with sequence slicing to reverse and display the circular linked list. It uses a generator to traverse the circular linked list and collects node data in a list, which is then reversed and printed in a compact manner.

Here’s an example:

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

def circular_linked_list(n):
    head = current = Node(1)
    for i in range(2, n + 1):
        current.next = Node(i)
        current = current.next
    current.next = head
    return head

head = circular_linked_list(4)
print(' '.join(map(str, list(node.data for node in iter(lambda: head.next, head))[::-1])))

Output:

4 3 2 1

This code snippet effectively is a condensed form of method 4, using a generator expression to traverse the list and generate a reversed list of node data values, which is then printed. It demonstrates Python’s succinct and expressive capabilities for handling data structures with minimal boilerplate code.

Summary/Discussion

  • Method 1: Iterative Reversal. This approach is straightforward and does not require additional data structures, but it modifies the original list structure.
  • Method 2: Using a Stack. This method leverages the LIFO nature of stacks to achieve the reverse display. It’s intuitive but requires O(n) extra space for the stack.
  • Method 3: Recursive Display. The recursive solution is elegant but could lead to stack overflow for large lists due to the limits of Python recursion depth.
  • Method 4: Reversing Using List Comprehension. It offers a clean one-liner solution, but like Method 2, it requires extra space to hold a temporary list of node data.
  • Bonus Method 5: Using Generators. This is the most Pythonic one-liner, concise and readable but still requires the extra space for the list created by the generator.