Linked List Part 5 || Doubly Linked List || Insertion in DLL || Implementation in C

What is a Doubly Linked List (DLL) ?

Doubly linked list has NULL at both ends i.e., before head as well as after last node we have NULL.

It can store address of both next node and previous node, unlike simple linked list which can have address of only next node

This image will give you a good picture of doubly linked list :

In addition to properties of simple linked list i.e., data (of integer type )and nextAdd (of struct NodeDll type) we will also have

struct NodeDll *prevAdd;

{here NodeDll is the name of structure that we will create}

In simple linked list we can traverse in only one direction but in Doubly linked list as we have address if previous node we can go back and forth as and when needed.

Let's make structure for doubly linked, allocate memory for it's nodes and also link the nodes in the main function, the following bit of code is for the same

struct NodeDll{
  int data;
  struct NodeDll *prevAdd;
  struct NodeDll *nextAdd; 
};


/*
  SAMPLE LINKED LIST :
  
 
egAddr.             101         285        121         662         358
        NULL <=> |2|285| <=> |8|121| <=> |3|662| <=> |6|358| <=> |10|NULL| <=> NULL
        names      head        one         two       three        four              
  
  */
  
int main()                                                                                  //...
{
  struct NodeDll *head = (struct NodeDll *)malloc (sizeof(struct NodeDll));
  struct NodeDll *one = (struct NodeDll *)malloc (sizeof(struct NodeDll));
  struct NodeDll *two = (struct NodeDll *)malloc (sizeof(struct NodeDll));
  struct NodeDll *three = (struct NodeDll *)malloc (sizeof(struct NodeDll));
  struct NodeDll *four = (struct NodeDll *)malloc (sizeof(struct NodeDll));

  head -> data = 2;
  head -> nextAdd = one;
  head -> prevAdd = NULL;
  
  one -> data = 8;
  one -> nextAdd = two;
  one -> prevAdd = head;
  
  two -> data = 3;
  two -> nextAdd = three;
  two -> prevAdd = one;
  
  three -> data = 6;
  three -> nextAdd = four;
  three -> prevAdd = two;
  
  four -> data = 10;
  four -> nextAdd = NULL;
  four -> prevAdd = three;
  
  return 0;
}
  
  

So now our job is to print this doubly linked list so lets make a traversal function and implement that :

void traverse(struct NodeDll *runner){
  printf("[ NULL ] <=> ");
  while(runner != NULL){
    printf("[ %d ] <=> ",runner -> data);
    runner = runner -> nextAdd;
  }
  printf("[ NULL ]");
}

Now, let's make a function insertAtIndex() and deleteAtIndex() which will work for all index from 0^th index till the last index, and I will leave it to you to create and practice insertion and deletion functions of other kind, in case of any doubts comment section is all yours. Feel free to ask us doubts or you can even mail us your questions at aajtcb02@gmail.com 

Now coming back to the topic let's make insertAtIndex() :

INSERTION:

First of all we will create a new node and dynamically allocate memory to it.

We also assign the value of data to be inserted to newNode->data

See this bit of code :

struct NodeDll *newNode = (struct NodeDll *) malloc (sizeof(struct NodeDll));

newNode -> data = newValue;

If you have read our post about Operation on simple linked list (click here for that post) you must be knowing that for insertion of a node at a given index we need to keep a runner pointer at the previous node of the given index ( if your question is why ? Then read that post or continue reading you will soon understand it soon)

So we will create a runner like this 

  struct NodeDll *runner and initialize it with the head node.

Move it forward till we reach the previous node to given index using this while loop

while(runner != NULL){
    printf("[ %d ] <=> ",runner -> data);
    runner = runner -> nextAdd;
  }
  

Once we are at the required node... We will do the main insertion 

We first link the newNode to nextAdd of the runner node

newNode->nextAdd = runner ->nextAdd;

Dont forget that we have one prevAdd also, the prevAdd of runner's nextAdd = new node

and newNode -> prevAdd = runner ;

(runner->nextAdd)->prevAdd = newNode;
newNode -> prevAdd = runner;

Then overwrite nextAdd of runner node to the newly created node.

runner -> nextAdd = newNode;

The above logic works for index 1 to last node so as we had done in Simple linked list we will make a conditional statement that  if (index == 0) {    // some statements for inserting at head}And put the previous code of insertion for other indexes in the else{  } block
For if block we will execute these simple instructions 

if(index == 0){
    newNode -> nextAdd = head;
    newNode -> prevAdd = NULL;
    head -> prevAdd = newNode;
    return newNode;
  }

Now, to prevent this post from getting too long and booring we will continue in the next post with deletionAtIndex(), and also make a reverseTraversal() to see if all the prevAdd are properly linked, for now you can take a look at thus function insertAtindex() here :

struct NodeDll *insertAtIndex(struct NodeDll *head, int newValue, int index ){
  
  struct NodeDll *newNode = (struct NodeDll *) malloc (sizeof(struct NodeDll));
  newNode -> data = newValue;
  
  if(index == 0){
    newNode -> nextAdd = head;
    newNode -> prevAdd = NULL;
    head -> prevAdd = newNode;
    return newNode;
  }
  
  else{
    struct NodeDll* runner = head;
    int runnerIndex = 0;
    while(runnerIndex != index - 1){
      runner = runner -> nextAdd;
      runnerIndex++;
    }
   
    newNode -> nextAdd = runner -> nextAdd;
    (runner->nextAdd)->prevAdd = newNode;
    newNode -> prevAdd = runner;
    runner -> nextAdd = newNode;
    return head;
  }
}

For complete code on doubly linked list you can click here

#KeepLearningKeepGrowing