A Linked list is versatile data structure because of its dynamic nature. Linked list is versatile and dynamic because insertion or deletion can be done at any given location. Algorithm Complexity of insertion and deletion algorithms are of the order of O(1). Reverse a linked list is another important operation. Let’s read how it is done.
How to Reverse a Linked list?
To reverse a linked list, three pointers are required to maintain addresses of the nodes being reconnected. Reversal is done by using the traversal operation. The first node becomes last node and last node of the linked list becomes first node after reversal. For every node these actions are done-
- Store current address of current node in pointer PTR. Store address of previous node in pointer PREV. Store address of next node in pointer NEXT
- Update LINK of PTR node with LINK of PREV node
- Update PREV with PTR, PTR with NEXT and NEXT with LINK of NEXT
- When the PTR is NULL (reaches end of the linked list), update START=PREV
These steps are described in the following images.
Algorithm ReverseLL(START) This algorithm traverses and reverses the nodes by updating their LINK part. 1. [Initialize Pointers] PREV=NULL PTR=START NEXT=START->LINK 2. Repeat step 3 while PTR!= NULL 3. [Update Pointers] PTR->LINK=PREV PREV=PTR PTR=NEXT NEXT=PTR->LINK 4. [Reset Start pointer of Linked List] START=PREV
This is the process of reversing a linear linked list by updating the pointers. You can see that this is done without moving the elements physically. It is traversal along with updating the links. The number of nodes in the linked list define the complexity of the algorithm.
Complexity of Algorithm to Reverse a Linked List
Step 2 of the algorithm described determines the major chunk of steps involved in this process. If the number of elements of a linear linked list is N then N nodes will be updated with new values for LINK parts.
So, it can be said that complexity of reversal of a linked list is O(N) and is linear. Time to reverse a linear linked list grows with number of nodes.