How to reverse a doubly linked list in C++

Overview

A doubly linked list (DLL) is a data structure comprising nodes with pointers to the next as well as the previous node. In this Answer, we learn how to reverse a DLL.

Note: For a quick primer on DLLs, we can click here.

We can reverse a DLL in a similar manner to reversing a regular linked list. For this, we need three temporary pointers or nodes, including a tail pointer. Unlike a regular linked list, though, we need to swap around double the number of pointers.

Process

Here are the steps we must follow in our function:

We check for an empty linked list.
We introduce three temporary pointers or nodes.
We introduce a loop that traverses the linked list until the end.

We convert the first element of the linked list to the tail right at the start.
We swap connections between three nodes using one of the temporary pointers or nodes.
We move our three temporary pointers or nodes forward. We repeat this step (3) and the previous one (2) until we reach the end of the linked list.
We put a condition in place to ensure that, during traversal, none of the temporary pointers is assigned anything other than nodes or NULL.

We convert the last element, probably pointed towards by one of the temporary pointers or stored in a temporary node, into the head of the linked list.

A visual representation of the steps above is as follows:

main.cpp

linked_list.cpp

linked_list.h

#ifndef __LIST_CPP
#define __LIST_CPP
#include "linked_list.h"
#include <cstdlib>
#include <iostream>
using namespace std;
// Constructor: Set both head and tail to NULL
template <class T>
linked_list<T>::linked_list() {
	head = NULL;
	tail = NULL;
}
// Destructor: Memory management (very important)
template <class T>
linked_list<T>::~linked_list() {
    for(int i = 0; i < length(); i++) {
        delete_head();
    }
}
// Insert elements to the head (left) of the list
template <class T>
void linked_list<T>::insert_head(T item) {
	if(head == NULL) {
        head = new list_item<T>(item);
        tail = head;
        return;
    }
    list_item<T> *Node = new list_item<T>(item);
    head->prev = Node;
    Node->next = head;
    head = Node;
}
// Insert elements to the tail (right) of the list
template <class T>
void linked_list<T>::insert_tail(T item) {
	if(tail == NULL) {
        tail = new list_item<T>(item);
        head = tail;
        return;
    }
    list_item<T> *Node = new list_item<T>(item);
    tail->next = Node;
    Node->prev = tail;
    tail = Node;
}
// For checking purposes
template <class T>
list_item<T>* linked_list<T>::get_head() {
	return head;
}
// For checking purposes
template <class T>
list_item<T>* linked_list<T>::get_tail() {
	return tail;
}
// For the destructor
template <class T>
void linked_list<T>::delete_head() {
	if(head == NULL) {
        return;
    }
    else if(head->next == NULL) {
    	delete head;
        head = NULL;
        tail = NULL;
    }
    else {
        list_item<T> *current = head->next;
        delete head;
        head = current;
        head->prev = NULL;
    }
}
// Good to have
template <class T>
void linked_list<T>::delete_tail() {
	if(head == NULL) {
        return;
    }
    else if(head->next == NULL) {
    	delete head;
        head = NULL;
        tail = NULL;
    }
    else {
        list_item<T> *current = tail->prev;
        delete tail;
        tail = current;
        tail->next = NULL;
    }
}
// For demonstration purposes
template <class T>
int linked_list<T>::length() {
	int count = 0;
    if(head == NULL) {
        return count;
    }
    else {
        list_item<T> *current = head;
        while(current != NULL) {
            count++;
            current = current->next;
        }
        return count;
    }
}
// For demonstration purposes
template <class T>
void linked_list<T>::print() {
    if(head == NULL) {
        cout << "empty list";
    } else {
        list_item<T> *current = head;
        while(current != NULL) {
            if(current->next != NULL) {
                cout << current->value << " <=> ";
            } else {
                cout << current->value;
            }
            current = current->next;
        }
    }
}
// The function we want to learn about
template <class T>
void linked_list<T>::reverse() {
    if(head == NULL) {
        cout << "empty list";
    } else {
        list_item<T> *before = head;
        list_item<T> *current = head->next;
        list_item<T> *after = head->next->next;
        while(current != NULL) {
            if(before->prev == NULL) {
                before->prev = current;
                before->next = NULL;
                tail = before;
            }
            current->next = before;
            current->prev = after;
            before = current;
            current = after;
            if(after != NULL) {
                after = after->next;
            }
        }
        head = before;
    }
}
#endif

Explanation

Here's how the highlighted function in the code above works:

Lines 140–141: The if branch checks whether the linked list has any values or not.
Lines 143–145: We need three temporary nodes (list_item), so we make them here. We use before and after for bookkeeping and tying up loose ends. The current pointer is largely responsible for traversing the linked list, and flipping the next and prev pointers of the nodes.
Lines 147–151: The first if in the loop ensures that the head of the linked list converts into the tail.
Lines 156–158: The second if in the loop ensures that when after is first assigned to NULL in the second-last iteration, it does not traverse further. Without this handling, the function throws a segmentation fault error.
Line 160: We convert the last node into the head.

New on Educative

Learn to Code

Learn any Language as a beginner

Develop a human edge in an AI powered world and learn to code with AI from our beginner friendly catalog

🏆 Leaderboard

Daily Coding Challenge

Solve a new coding challenge every day and climb the leaderboard

Free Resources