Doubly Linked List

Today we will be working with doubly Linked List. Which is also called the forward and backward moving list. In a traditional Singly Linked List we can only Move forward but in a Doubly Linked List We can also move Backward. We use A concept of tail to move backward from the end. The basic structure of a Node of a double linked list would look like this. The Node has now two pointers as compared to a Singly Linked List. The node would be pointing forward to next node and also pointing to the backward node at the same time. So we can backtrack the list to from end to start. A visual image is added below.

Not the best visuals I know but it does the trick as you see the first element is head so It will have no previous nodes so the prev is pointing to NULL. The last node has nothing in front so we will point it to NULL. Now We will take a look at the code for the node class for the Doubly Linked List.

class node {
private:
 int data;// data variable to store dataa
 node* next;//pointer for next address
 node* prev;//pointer for prev address
public:
 node() {
  this ->data = 0;
  this->next = NULL;
  this->prev = NULL;
 }
 node(int data) {
  this->data = data;
  this->next = NULL;
  this->prev = NULL;
 }
 void setData(int data) {
  this->data = data;
 }
 void setnext(node* next) {
  this->next = next;
 }
 void setprev(node* prev) {
  this->prev = prev;
 }
 int getdata() {
  return data;
 }
 node* getnext() const {
  return this->next;
 }
 node* getprev()const {
  return prev;
 }
};

The code For Node class in Doubly Linked List has two pointers where 1 pointer Will point to the Next Node and the second Node will point to the previous node and also has 1 variable to hold data in itself. In the constructors both the next and previous node will be equal to NULL and pointing to NULL. Then we have the old setters and getters to set and get the variables such as set the next pointer, set the previous pointer, Assign the data to the data variable.

Moving on we will be creating the Class Doubly Linked List this where we see a little change here we will be creating two pointers A head and a tail. The head one will always point to the start of the list (The first Node in the List) The tail Node will always be equal to the Last Node of the list. The code for the Doubly Linked List is Shown Below.

class doublyLinkedList {
private:
 node* head;//pointer for start
 node* tail;//pointer for end
public:
 doublyLinkedList() {
  head = NULL;
  tail = NULL;
 }
 void add(int data) {
  node* N = new node(data);//new node intialized with Data
  if (head == NULL) {//if head found equal to NULL
   head = N;//head = nee node
   tail = N;//tail = new node
  }
  else {
   tail->setnext(N);//set tail's next to New Node
   N->setprev(tail);//Set previous of New node to TAIL
   tail = N;//SET TAIL= NEW NODE
  }
 }
 void display() {
  node* temp = head;//TEMP TO ITERATE THROUGH LIST
  while (temp->getnext() != NULL) {//WHILE TEMP'S NEXT IS NOT null
   cout << temp->getdata()<<endl;//PRINT THE DATA
   temp = temp->getnext();//SET TEMP EQUAL TO THE NEXT NODE.
  }
 }
};

The constructor is simple to understand the pointers are initialized with NULL. The main focus would be the add function. The add function creates a New Node and initializes the Data with it. Then the function checks if the Head pointer is equal to NULL it sets the head pointer to the New node. and Tail pointer to the N node too because the List was empty till now and only One node is added yet so the start and end are the same. If some how there are more than one node in the list then the function will create another node called temp and set it equal to head and then Iterate it to the end of the List Now it will point the last node to the new Node N. it will see the previous pointer of the Last node to the previous node and update the tail of the list and set the tail according to the Last Node. There a much simpler way of adding a node to the end which has the Time complexity of O(1). The Code is mentioned below.

void display() {
  node* temp = head;//TEMP TO ITERATE THROUGH LIST
  while (temp!= NULL) {//WHILE TEMP'S NEXT IS NOT null
   cout << temp->getdata()<<endl;//PRINT THE DATA
   temp = temp->getnext();//SET TEMP EQUAL TO THE NEXT NODE.
  }
 }

What this code is doing is directly setting the next of the tail Node equal to the N node Reason being Before we can change the tail we need to connect the current tail which is pointing to NULL to the next Node and setting the prev of the N node to the tail node Reason being so we can back track wehn moving backward in the list And then setting the Tail node equal to the N node Because we need to update the tail wo we can access the last element when going backward.