Reversing a Singly Linked List in Python

In this guide, we will write a Python program to reverse a singly linked list. We will also walk through the structure of the program and explain each part in detail.

Program Structure

The program consists of the following components:

1. Definition of a Node class.
2. Definition of a LinkedList class.
3. Method to reverse the linked list.
4. Utility methods to add elements and display the list.

Python Program

class Node:
    """
    A class representing a node in a singly linked list.

    Attributes:
    -----------
    data : any
        The data stored in the node.
    next : Node or None
        The reference to the next node in the linked list.
    """

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


class LinkedList:
    """
    A class for creating and manipulating a singly linked list.

    Attributes:
    -----------
    head : Node or None
        The head (first node) of the linked list.
    
    Methods:
    --------
    append(data):
        Adds a new node with the given data to the end of the list.
    
    display():
        Displays the elements of the list.
    
    reverse():
        Reverses the linked list in place.
    """

    def __init__(self):
        self.head = None

    def append(self, data):
        """
        Adds a new node with the given data to the end of the list.

        Parameters:
        -----------
        data : any
            The data to be added to the list.
        """
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def display(self):
        """
        Displays the elements of the linked list.
        """
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    def reverse(self):
        """
        Reverses the singly linked list in place.
        """
        previous = None
        current = self.head
        while current:
            next_node = current.next  # Temporarily store the next node
            current.next = previous  # Reverse the current node's pointer
            previous = current  # Move the previous pointer up
            current = next_node  # Move to the next node in the list
        self.head = previous  # Update the head to the new first node
    

Explanation of the Code

1. Node Class

The Node class is a blueprint for creating individual nodes in a singly linked list. Each node contains two attributes:

• data: Stores the value of the node.
• next: A reference to the next node in the list (or None if it’s the last node).

2. LinkedList Class

The LinkedList class provides a structure for the linked list and includes methods to manipulate it. This class includes:

• append(data): Adds a node with the given data to the end of the list.
• display(): Prints out the linked list elements in order.
• reverse(): Reverses the linked list in place.

3. Reversing the Linked List

The reverse method works by iterating through the linked list and reversing the direction of the pointers. The process is as follows:

1. Start with previous set to None and current set to the head of the list.
2. Iterate through the list, reversing the next pointer of each node to point to the previous node.
3. After the loop, the head of the list is updated to the last node, which becomes the new head of the reversed list.

Example Usage

# Creating a linked list and adding elements
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)

print("Original List:")
ll.display()

# Reversing the linked list
ll.reverse()

print("Reversed List:")
ll.display()
    

In this example, we first create a linked list with four nodes. We then reverse the list and display the result. The output should be:

Original List:
1 -> 2 -> 3 -> 4 -> None

Reversed List:
4 -> 3 -> 2 -> 1 -> None