Doubly Linked List

A doubly linked list consists of two pointers and a data value, where two pointers allow the traversal of lists in two directions. i.e. forward and backwards.

Insertion in Doubly Linked Lists

There are three cases of inserting a node with a data value given a position index in a linked list:

1. Insertion at Beginning

2. Insertion at End

3. Insertion at Middle

How to Construct a Doubly Linked List

class Node {
    public:
        int data;
        Node *next;
        Node *prev;

        Node(int val) {
            this->data = val;
            next = NULL;
            prev = NULL;
        }

};

Insertion in a Doubly Linked List

// A function to insert the nodes in a linked list 
Node* insert(int k, int val, Node* head) {
   //first case:  trying to insert in an empty list 
//so create a node with the given value and then allocate your head pointer to it 
//and return 


    if (head == NULL) {
        Node* value = new Node(val);
        head = value;
        return head;
    } 
//second case : if trying to insert at the start of the list :
//create a node with the data value 
// and then point that node's next  to the head pointer and head prev to value node 
// and allocate head to value and return head;
    else if (k == 0) {
         Node* value = new Node(val);
        // Insertion at the beginning (k == 0).
        value->next = head;
        head->prev = value;
        head = value;
          return head;
    } 
//third case : trying to insert at either the end of list or the middle of lists

    else {
//first traverse to find out whether you want to insert at the middle or end.
//for traversal make a temp node: run a while loop and initilise count variable to 1 
// traverse till the time ypu reach to the place where you want to insert 
//i check then if temp->next ==NULL that is need to insert at the end
// else need to insert at the middle 
        Node* temp = head;
        int count = 1;
        while (count < k) {
            count++;
            temp = temp->next;

        }
        if (temp->next ==NULL) {
            Node* value = new Node(val);
            temp->next = value;
            value->prev = temp;
            return head;
        } else {

           Node* value = new Node(val);
           value ->next = temp->next;
           temp->next= value;
           value->prev = temp;
           value->next->prev = value;
           return head;
        }
    }


}