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.
Article Series
Queue Data Structure
Another simplest data structure after stack is the "Queue" data structure. As we know the stack data…
Stack Data Structure
We covered array and linked lists in previous article. Now we got a much simpler data structure "Sta…
Linked Lists - Singly Linked List
We learned our first data structure "Arrays" in the last article. Now, its time to move on to "Linke…
Array Data Structure
What is an Array? An array is just a collection of variables stored at contiguous locations in the m…
Introduction to DSA
In this series, we will go through all of the concept related to Data Structures and Algorithms. We …