Write a C function to reverse a given Doubly Linked List
See below diagrams for example.
(a) Original Doubly Linked List
(b) Reversed Doubly Linked List
Here is a simple method for reversing a Doubly Linked List. All we need to do is swap prev and next pointers for all nodes, change prev of the head (or start) and change the head pointer in the end.\
[ad type=”banner”]Java programming:
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20reverse%20a%20doubly%20linked%20list%0A%20%0Aclass%20LinkedList%20%7B%0A%20%0A%20%20%20%20static%20Node%20head%3B%0A%20%0A%20%20%20%20static%20class%20Node%20%7B%0A%20%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%2C%20prev%3B%0A%20%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20prev%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Function%20to%20reverse%20a%20Doubly%20Linked%20List%20*%2F%0A%20%20%20%20void%20reverse()%20%7B%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20Node%20current%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20swap%20next%20and%20prev%20for%20all%20nodes%20of%20%0A%20%20%20%20%20%20%20%20%20doubly%20linked%20list%20*%2F%0A%20%20%20%20%20%20%20%20while%20(current%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20current.prev%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20current.prev%20%3D%20current.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20current.next%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.prev%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Before%20changing%20head%2C%20check%20for%20the%20cases%20like%20empty%20%0A%20%20%20%20%20%20%20%20%20list%20and%20list%20with%20only%20one%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20(temp%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20head%20%3D%20temp.prev%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%20%20%20%20%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginging%20of%20the%20Doubly%20Linked%20List%20*%2F%0A%20%20%20%20void%20push(int%20new_data)%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20since%20we%20are%20adding%20at%20the%20begining%2C%20%0A%20%20%20%20%20%20%20%20%20prev%20is%20always%20NULL%20*%2F%0A%20%20%20%20%20%20%20%20new_node.prev%20%3D%20null%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20change%20prev%20of%20head%20node%20to%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20(head%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20head.prev%20%3D%20new_node%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20doubly%20linked%20list%20%0A%20%20%20%20%20This%20function%20is%20same%20as%20printList()%20of%20singly%20linked%20lsit%20*%2F%0A%20%20%20%20void%20printList(Node%20node)%20%7B%0A%20%20%20%20%20%20%20%20while%20(node%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(node.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%20list%20%3D%20new%20LinkedList()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20create%20a%20sorted%20linked%20list%20to%20test%20the%20functions%0A%20%20%20%20%20%20%20%20%20Created%20linked%20list%20will%20be%2010-%3E8-%3E4-%3E2%20*%2F%0A%20%20%20%20%20%20%20%20list.push(2)%3B%0A%20%20%20%20%20%20%20%20list.push(4)%3B%0A%20%20%20%20%20%20%20%20list.push(8)%3B%0A%20%20%20%20%20%20%20%20list.push(10)%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Original%20linked%20list%20%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(head)%3B%0A%20%0A%20%20%20%20%20%20%20%20list.reverse()%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22The%20reversed%20Linked%20List%20is%20%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(head)%3B%0A%20%20%20%20%7D%0A%7D%0A%20″ message=”” highlight=”” provider=”manual”/]Time Complexity: O(n)
We can also swap data instead of pointers to reverse the Doubly Linked List. Method used for reversing array can be used to swap data. Swapping data can be costly compared to pointers if size of data item(s) is more.