Reversing a Singly Linked List in Python: Step-by-Step Tutorial

What is a Singly Linked List?

"A singly linked list is a fundamental data structure where each node points to the next node."

A singly linked list is a linear data structure where each element (node) points to the next element in the list. The last node points to None, indicating the end of the list.

Here’s an example of a singly linked list: 10 -> 20 -> 30 -> 40 -> None. The goal of reversing the list is to change the direction of the links so that the first node becomes the last node.

Approach to Reverse the Linked List

Reversing a linked list involves changing the direction of the pointers for each node. We’ll use three pointers:

• Previous: Points to the previous node in the list.
• Current: Points to the current node in the list.
• Next: Temporarily stores the next node to avoid losing the reference during the reversal.

The algorithm involves iterating through the list, adjusting the next pointer of each node, and finally updating the head of the list to point to the last node (which is now the first node).

Code Example

Here’s the Python code to reverse a singly linked list:

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def print_list(self):
        temp = self.head
        while temp:
            print(temp.data, end=" -> ")
            temp = temp.next
        print("None")

    def reverse(self):
        previous = None
        current = self.head
        while current:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        self.head = previous
                        

How the Code Works

The code includes a Node class to represent each node in the list and a LinkedList class to manage the linked list. The reverse method iterates through the list, adjusting the pointers to reverse the list.

After the reversal, the head points to the last node, and the list is completely reversed.

Example Output

Let’s see an example where we create a linked list and reverse it:

# Creating the linked list
llist = LinkedList()
llist.append(10)
llist.append(20)
llist.append(30)
llist.append(40)

print("Original Linked List:")
llist.print_list()

# Reversing the linked list
llist.reverse()

print("Reversed Linked List:")
llist.print_list()
                        

Output:

Original Linked List:
10 -> 20 -> 30 -> 40 -> None

Reversed Linked List:
40 -> 30 -> 20 -> 10 -> None

Conclusion

Reversing a singly linked list is a valuable operation that helps you understand pointer manipulation in data structures. Mastering this concept will improve your problem-solving skills and prepare you for more complex algorithms.