How to reverse a doubly-linked list

A doubly-linked list is a type of linked list that comes with an additional pointer to the previous node. It works the same as a singly linked list, but each node in a doubly-linked list is connected with its previous and next node through a pointer.

Note: Want to learn about linked list? Click here for more info.

Understanding the problem

Let's consider we get a doubly-linked list and we need to reverse it so that the pointer currently pointing to the head of the list points to the tail of the doubly-linked list. Moreover, other pointers also start pointing to the previous node. In this answer, we'll learn to reverse a doubly-linked list. Here's the visualization of reversed doubly-linked list:

/* Reversing a Doubly Linked List */
void reverse_list(node **head_ptr) 
{ 
    //Creating temporary node
    node *temp_node = NULL; 
    node *current_node = *head_ptr; 
    /* swapping next and previous pointers until all nodes are reversed */
    while (current_node != NULL) 
    {         //swapping
        temp_node = current_node->prev; 
        current_node->prev = current_node->next; 
        current_node->next = temp_node;             
        current_node = current_node->prev; 
    }
    if(temp_node != NULL ) //update head_ptr
        *head_ptr = temp_node->prev;  
}
// Driver Code 
int main(){
  node* head = new node(); //creating head
  head->data=1; //intializing head's value with 1
  head = addAtEnd(head, 2); //Inserting new nodes
  head = addAtEnd(head, 3);
  head = addAtEnd(head, 4);
  print_data(head);  //displaying whole list
  reverse_list(&head); //reverseing list
  cout<<"\n\nAfter reversing \n\n";
  print_data(head); //displying whole list
}

Explanation

Line 3–7: We define a reverse_list() function with a parameter of the address pointer *head_ptr. We create temporary nodes to traverse the doubly-linked list.
Line 9–14: We use while loop to iterate through each node and in while we swap the values of prev, next, and current_node.
Line 16–17: We update the value of head_ptr for the next iteration.

Time complexity

We completely reversed the given doubly-linked with the time complexity being $O(n)$ where $n$ is the number of nodes.

How to reverse a doubly-linked list

Understanding the problem

Steps

Implementation

Explanation

Time complexity