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.