Write a C function to reverse a given Doubly Linked List
Doubly Linked List:
Doubly Linked List (DLL) is a list of elements and it varies from Linked List. It allows navigation, either forward or backward when compared to Single Linked List. It has two pointers: previous pointer and next pointer. Every element points to next of the list and previous element in list.
Terms used in doubly linked list:
- Link
- Next
- Prev
- 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.
C programming:
[pastacode lang=”c” manual=”%2F*%20Program%20to%20reverse%20a%20doubly%20linked%20list%20*%2F%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F*%20a%20node%20of%20the%20doubly%20linked%20list%20*%2F%0Astruct%20node%0A%7B%0A%20%20int%20data%3B%0A%20%20struct%20node%20*next%3B%0A%20%20struct%20node%20*prev%3B%20%20%20%20%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20reverse%20a%20Doubly%20Linked%20List%20*%2F%0Avoid%20reverse(struct%20node%20**head_ref)%0A%7B%0A%20%20%20%20%20struct%20node%20*temp%20%3D%20NULL%3B%20%20%0A%20%20%20%20%20struct%20node%20*current%20%3D%20*head_ref%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%2F*%20swap%20next%20and%20prev%20for%20all%20nodes%20of%20%0A%20%20%20%20%20%20%20doubly%20linked%20list%20*%2F%0A%20%20%20%20%20while%20(current%20!%3D%20%20NULL)%0A%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20temp%20%3D%20current-%3Eprev%3B%0A%20%20%20%20%20%20%20current-%3Eprev%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20current-%3Enext%20%3D%20temp%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20current%20%3D%20current-%3Eprev%3B%0A%20%20%20%20%20%7D%20%20%20%20%20%20%0A%20%20%20%20%20%20%0A%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%20list%20and%20list%20with%20only%20one%20node%20*%2F%0A%20%20%20%20%20if(temp%20!%3D%20NULL%20)%0A%20%20%20%20%20%20%20%20*head_ref%20%3D%20temp-%3Eprev%3B%0A%7D%20%20%20%20%20%0A%20%0A%20%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginging%20of%20the%20Doubly%20Linked%20List%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%20%20%20%20%0A%20%20%20%20%2F*%20since%20we%20are%20adding%20at%20the%20begining%2C%20%0A%20%20%20%20%20%20prev%20is%20always%20NULL%20*%2F%0A%20%20%20%20new_node-%3Eprev%20%3D%20NULL%3B%0A%20%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%20%20%20%20%0A%20%0A%20%20%20%20%2F*%20change%20prev%20of%20head%20node%20to%20new%20node%20*%2F%0A%20%20%20%20if((*head_ref)%20!%3D%20%20NULL)%0A%20%20%20%20%20%20(*head_ref)-%3Eprev%20%3D%20new_node%20%3B%20%20%20%20%0A%20%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20doubly%20linked%20list%20%0A%20%20%20This%20function%20is%20same%20as%20printList()%20of%20singly%20linked%20lsit%20*%2F%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20while(node!%3DNULL)%0A%20%20%7B%0A%20%20%20printf(%22%25d%20%22%2C%20node-%3Edata)%3B%0A%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%7D%0A%7D%20%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20struct%20node*%20head%20%3D%20NULL%3B%0A%20%20%0A%20%20%2F*%20Let%20us%20create%20a%20sorted%20linked%20list%20to%20test%20the%20functions%0A%20%20%20Created%20linked%20list%20will%20be%2010-%3E8-%3E4-%3E2%20*%2F%0A%20%20push(%26head%2C%202)%3B%0A%20%20push(%26head%2C%204)%3B%0A%20%20push(%26head%2C%208)%3B%0A%20%20push(%26head%2C%2010)%3B%0A%20%20%0A%20%20printf(%22%5Cn%20Original%20Linked%20list%20%22)%3B%0A%20%20printList(head)%3B%0A%20%20%0A%20%20%2F*%20Reverse%20doubly%20linked%20list%20*%2F%0A%20%20reverse(%26head)%3B%0A%20%20%0A%20%20printf(%22%5Cn%20Reversed%20Linked%20list%20%22)%3B%0A%20%20printList(head)%3B%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20getchar()%3B%0A%7D” message=”” highlight=”” provider=”manual”/]Output:
Original Linked list 10 8 4 2 Reversed Linked list 2 4 8 10
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.