Reverse a Doubly Linked List

Reversing a Doubly Linked List

Reversing a doubly linked list involves changing the direction of the next and previous pointers so that the last node becomes the head and the head becomes the last node. This operation requires traversing the list and swapping the next and previous pointers of each node.

---

Step-by-Step Process

Consider a doubly linked list with the following structure before reversal:

Head <-> 1 <-> 2 <-> 3 <-> 4 <-> None

We want to reverse the list so that it becomes:

Head <-> 4 <-> 3 <-> 2 <-> 1 <-> None

Follow these steps to reverse the list:

1. Initialize Pointers: Start with the current node set to the head.
2. Traverse and Swap: For each node, swap its next and previous pointers, then move to the previous node (which is the original next node before the swap).
3. Update the Head Pointer: After the loop, update the head pointer to the last non-None node.

---

Python Program to Reverse a Doubly Linked List

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

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current

    def reverse(self):
        current = self.head
        temp = None
        while current is not None:
            temp = current.prev
            current.prev = current.next
            current.next = temp
            current = current.prev
        if temp is not None:
            self.head = temp.prev

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Example usage:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.append(4)
print("Doubly linked list before reversal:")
dll.traverse()  # Output: 1 <-> 2 <-> 3 <-> 4 <-> None

dll.reverse()
print("Doubly linked list after reversal:")
dll.traverse()  # Output: 4 <-> 3 <-> 2 <-> 1 <-> None

This Python program defines a doubly linked list with methods for appending nodes, reversing the list, and traversing the list. The reverse method traverses the list, swaps the next and previous pointers of each node, and updates the head pointer to the new head of the reversed list.