Reversing a Doubly linked list | Data structures

To Reverse a doubly linked list we have two approaches either reverse the links of every node or either reverse the values of nodes. in this tutorial, we are going to reverse a doubly-linked list by reversing their links.

like if we have a doubly-linked list that has four nodes. as you see in the image given below.


after reversing this linked list the start variable refers to the last node of the list and the first node becomes the last node and the last node becomes the first node. so our new reversed linked list should be like this as you see in the image given below.

Method to Reversing a Doubly linked list

so to reverse a linked list first we need two references p1 and p2. initially, we set p1 pointing to the first node of the linked list and p2 pointing to the second node of the linked list.


after that, we store the p1 node's previous link part into the p1 node's next link part. as you see in the given below image.


and then we store the p2 node's reference into the p1 node's previous link part.


after that, we start a loop and that will be run till the value of variable p2 does become None or Null. it means the loop will run until we reached the last node of the linked list.

in every iteration first, we store the p2 node's next link part's value into the p2 node's previous link part.


second, we store the p1 node's reference into p2 node's next link part.


third, we set p1 to the next node that comes after the node p1 using the p2 node.


fourth we set p2 to the next node that comes after the node p2 using the previous link part of node p2.


so in every iteration, these four conditions will apply and this condition will run till we don't reach the last node of the linked list or till the value of the node, p2 becomes None or Null.












so now the value of variable p2 becomes None means we reached the last node of the linked list so we store the p1 node's reference into the start variable because the start variable always refers to the first node of the linked list.

Python program for reversing a doubly linked list.

class Node(object):

    def __init__(self, value):
        self.info = value
        self.prev = None        self.next = None

class DoubleLinkedList(object):

    def __init__(self):
        self.start = None
    def display_list(self):
        if self.start is None:
            print("LIst is empty")
            return
        print("List is : ")
        p = self.start
        while p is not None:
            print(p.info, " ", end='')
            p = p.next
        print()

    def insert_in_beginning(self, data):
        temp = None(data)
        temp.next = self.start
        self.start.prev = temp
        self.start = temp

    def insert_in_empty_list(self, data):
        temp = Node(data)
        self.start = temp

    def insert_at_end(self, data):
        temp = Node(data)
        p = self.start
        while p.next is not None:
            p = p.next
        p.next = temp
        temp.prev = p

    def create_list(self):
        n = int(input("Enter the number of nodes : "))
        if n == 0:
            return        data = int(input("Enter the first element to be inserted : "))
        self.insert_in_empty_list(data)

        for i in range(n - 1):
            data = int(input("Enter the next element to be inserted : "))
            self.insert_at_end(data)

    def insert_after(self, data, x):
        temp = Node(data)
        p = self.start
        while p is not None:
            if p.info == x:
                break            p = p.next

        if p is None:
            print(x, " not present in the list")
        else:
            temp.prev = p
            temp.next = p.next
            if p.next is not None:
                p.next.prev = temp
            p.next = temp

    def insert_before(self, data, x):
        if self.start is None:
            print("List is empty")
            return
        if self.start.info == x:
            temp = Node(data)
            temp.next = self.start
            self.start.prev = temp
            self.start = temp
            return
        p = self.start
        while p is not None:
            if p.info == x:
                break            p = p.next

        if p is None:
            print(x, " not present in the list")
        else:
            temp = Node(data)
            temp.prev = p.prev
            temp.next = p
            p.prev.next = temp
            p.prev = temp

    def delete_first_node(self):
        if self.start is None:
            return        if self.start.next is None:
            self.start = None            return        self.start = self.start.next
        self.start.prev = None
    def delete_last_node(self):
        if self.start is None:
            return        if self.start.next is None:
            self.start = None            return
        p = self.start
        while p.next != None:
            p = p.next
        p.prev.next = None
    def delete_node(self, x):
        if self.start is None:
            return        if self.start.next is None:
            if self.start.info == x:
                self.start = None            else:
                print(x, " not found")
            return
        if self.start.info == x:
            self.start = self.start.next
            self.start.prev = None            return
        p = self.start.next
        while p.next is not None:
            if p.info == x:
                break
            p = p.next

        if p.next is not None:
            p.prev.next = p.next
            p.next.prev = p.prev
        else:
            if p.info == x:
                p.prev.next
            else:
                print(x, " not found")

    def reverse_list(self):
        if self.start is None:
            return
        p1 = self.start
        p2 = p1.next
        p1.next = None        p1.prev = p2
        while p2 is not None:
            p2.prev = p2.next
            p2.next = p1
            p1 = p2
            p2 = p2.prev
        self.start = p1


#################################################################3
list = DoubleLinkedList()

list.create_list()

while True:
    print("1. Display list")
    print("2. Insert in empty list")
    print("3. Insert a node in the beginning of the list")
    print("4. Insert a node at the end of the list")
    print("5. Insert a node after a specified node")
    print("6. Insert a node before a specified node")
    print("7. Delete first node")
    print("8. Delete last node")
    print("9. Delete any node")
    print("10. Reverse the list")
    print("11. Quit")

    option = int(input("Enter your choice : "))

    if option == 1:
        list.display_list()
    elif option == 2:
        data = int(input("Enter the element to be inserted : "))
        list.insert_in_empty_list(data)
    elif option == 3:
        data = int(input("Enter the element to be inserted : "))
        list.insert_in_beginning(data)
    elif option == 4:
        data = int(input("Enter the element to be inserted : "))
        list.insert_at_end(data)
    elif option == 5:
        data = int(input("Enter the element to be inserted : "))
        x = int(input("Enter the element after which to insert : "))
        list.insert_after(data, x)
    elif option == 6:
        data = int(input("Enter the element to be inserted : "))
        x = int(input("Enter the element before which to inserted : "))
        list.insert_before(data, x)
    elif option == 7:
        list.delete_first_node()
    elif option == 8:
        list.delete_last_node()
    elif option == 9:
        data = int(input("Enter the element to be deleted : "))
        list.delete_node(data)
    elif option == 10:
        list.reverse_list()
    elif option == 11:
        break    else:
        print("Wrong option")
    print()

Also, read other tutorials as well

• What are Data Structures and algorithms
• Algorithm design and analysis
• Classification of algorithms
• How to calculate the running time of an algorithm.
• Worst Average and Best-case analysis of the algorithm.
• Big o notation
• Big o notation examples
• Linked List in Data Structures
• Traversing in Linked list
• Operations on the linked list
• Insertion in the linked list
• Deletion in a linked list
• Reversing a linked list
• Sorting a linked list
• Find and remove the loop in the linked list
• Doubly linked list
• Insertion in the doubly linked list
• Deletion in the doubly linked list
• Circular linked list
• Insertion in the circular linked list
• Deletion in the circular linked list
• Merge two linked list
• Header linked list
• Sorted linked list
• Stack in data structures
• Queue in data structures
• Circular queue
• Dequeue in the data structure
• Priority queue
• Polish notation
• Tree in the data structure
• Binary tree
• Array representation of the binary tree
• linked representation of a binary tree
• Traversing in the binary tree
• Inorder traversal in the binary tree
• Preorder traversal in the binary tree
• Postorder traversal in the binary tree
• Level order traversal in the binary tree
• Binary search tree
• Insertion in the binary search tree
• Deletion in the binary search tree
• Heap in data structures