Linked Lists - Doubly Linked List

Alright, we covered singly linked list in the previous article, now it's time for a doubly linked list, which to be honest isn't that different much from a singly linked list. The only difference is we that each node contains a reference to the previous node also allowing us to walk in both forward and backward direction.

So, we will get three items in each node, the stored value, a pointer for next node and a pointer for previous node. Everything else will be the same as in singly linked list.

We will use two pointer technique here marking both head and tail of our list. Every new node will become the head or tail of our list. So, let's start with the structure of our node:

struct ListNode {
    int val;
    ListNode *next;
    ListNode *prev;
    ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
};

Let’s deep dive in to figure out what this does. First, we have the val field as an integer that will store the actual node data. Next both the next and prev fields are pointers pointing to the next and previous nodes respectively. Finally we got the constructor for this struct which will make both pointer null by default. If you are confused about this constructor syntax, head over to the docs to understand it first.

Here is how the basic List struct will look like.

struct List {
    ListNode *head;
    ListNode *tail;

    List(){
        head = nullptr;
        tail = nullptr;
    }
}

We are just using the ListNode struct to build our List struct just like in singly linked list. But this time we are gonna use two ListNode structs, one for head and one for tail.

Alright, so let’s start with implementing our first method for this list. Which is gonna be push_front, it will be used to push a new node in front of the list as a new head.

void push_front(int x) {
  ListNode *n = new ListNode(x);

  if (head == nullptr) {
    head = n;
    tail = n;
  } else {
    n->next = head;
    head->prev = n;
    head = n;
  }
}

If you understood the singly linked list works in the last article, you should be able to understand this pretty easily. All this does is create a new node using giving data. Then check if its the first node, if yes mark it as both head and tail. Otherwise, make it the head of list.

Same goes for the method push_back but this time we make it the tail.

void push_back(int x) {
  ListNode *n = new ListNode(x);

  if (tail == nullptr) {
    head = n;
    tail = n;
  } else {
    n->prev = tail;
    tail->next = n;
    tail = n;
  }
}

Same thing here, except we mark the new node as tail instead of head.

Here is another method to pop the head node. It will remove the head node and return its data.

int pop_front() {
  int val = head->val;

  ListNode *next = head->next;

  delete head;

  head = next;

  return val;
}

Yes it is actually as simple as it looks. All it does is mark the node pointed in the next property of current head as the new head and delete the current head. And then return the value of the deleted head.

Similarly, the pop_back method will deal with popping the tail node.

int pop_back() {
  int val = tail->val;

  ListNode *prev = tail->prev;

  delete tail;

  tail = prev;

  return val;
}

Now if you want to print the whole list just to see what’s in it. I added a simple method print which you can find in the full code below along with the tests.

#include <iostream>

// ignore/remove the 2 lines below if you don't want any tests
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

using namespace std;

struct ListNode {
  int val;
  ListNode *next;
  ListNode *prev;
  ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
};

struct List {
  ListNode *head;
  ListNode *tail;

  List() {
    head = nullptr;
    tail = nullptr;
  }

  void push_front(int x) {
    ListNode *n = new ListNode(x);

    if (head == nullptr) {
      head = n;
      tail = n;
    } else {
      n->next = head;
      head->prev = n;
      head = n;
    }
  }

  void push_back(int x) {
    ListNode *n = new ListNode(x);

    if (tail == nullptr) {
      head = n;
      tail = n;
    } else {
      n->prev = tail;
      tail->next = n;
      tail = n;
    }
  }

  int pop_front() {
    int val = head->val;

    ListNode *next = head->next;

    delete head;

    head = next;

    return val;
  }

  int pop_back() {
    int val = tail->val;

    ListNode *prev = tail->prev;

    delete tail;

    tail = prev;

    return val;
  }

  void print() {
    ListNode *curr = head;
    while (curr != nullptr) {
      cout << curr->val << endl;
      curr = curr->next;
    }
  }
};

// TESTS
TEST_CASE("push_back") {
  List *list = new List();

  list->push_back(5);
  list->push_back(10);

  CHECK(list->tail->val == 10);
  CHECK(list->head->val == 5);
}

TEST_CASE("push_front") {
  List *list = new List();

  list->push_front(5);
  list->push_front(10);

  CHECK(list->head->val == 10);
  CHECK(list->tail->val == 5);
}

TEST_CASE("pop_front") {
  List *list = new List();

  list->push_front(5);
  list->push_front(10);

  list->pop_front();

  CHECK(list->head->val == 5);
}

TEST_CASE("pop_back") {
  List *list = new List();

  list->push_front(5);
  list->push_front(10);

  list->pop_back();

  CHECK(list->tail->val == 10);
}

Time Complexity

Both push and pop methods have the time complexity of O(1). Because we have direct references to the head and tail nodes.