Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++

How to reverse a doubly linked list in C++

Rehan Jahangir

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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.
    1. We convert the first element of the linked list to the tail right at the start.
    2. We swap connections between three nodes using one of the temporary pointers or nodes.
    3. 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.
    4. 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:

How our reverse() function works
How our reverse() function works

Code

The driver code for our C++ doubly linked list implementation is given below. We coded it using templates. We can use any data type with the implementation, as long as it's consistent, without changing the code itself.

We can see below that we have two linked lists. One of these contains only int values, while the other contains only char values.

Note: If we just want to see the function for a reversal, we can look at the highlighted lines (138–162) in the linked_list.cpp file.

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
The driver code and reversal function for a doubly linked list in C++

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.

RELATED TAGS

c++

CONTRIBUTOR

Rehan Jahangir
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring