Linked List Part 6 | Deletion | Reverse Traversal | Doubly Linked List

In the previous post we had created a doubly linked list , did traversal and insertion in it. Click here for the previous post

Now, we are going to delete a node by it's index and then implement traversal in reverse order from last node to head.

Deletion in doubly linked list:

1. Define runner and start runner pointer from head to (index - 1)^th node.

2. Declare and Initialze runner2 and initialize runner2 = runner->nextAdd;

(So our runner2 will be present at the node to be deleted) 

3. As we want to omit the node to be deleted, let's call the deleted node to be A.

Therefore the next node to A will have , prevAdd as previous to node A.

So we will declare

(runner2->nextAdd)->prevAdd = runner

4. Now we will just free up memory occupied by runner2 

free(runner2) 

Now our node is deleted.

Here is the function for it.

struct NodeDll *deleteAtIndex(struct NodeDll *head, int index ){
  
  struct NodeDll* runner;
  if(index == 0){
    head = head -> nextAdd;
    head -> prevAdd = NULL;
    (head->nextAdd)->prevAdd = head;
    return head;
  }

Next we will make a function for traversing through this linked list in reverse order. For reverse traversal we will have to make use of prevAdd as, every time we print data in a node pointer has to be moved  a step behind to print data in it's previous node.

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

Here we have the complete code for creation, insertion, deletion and reverse traversal of a Doubly Linked List:

#include <stdio.h>
#include <stdlib.h>

//Compiler version gcc  6.3.0

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              
  
  */
    

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

// printing in reverse order
void reverseTraverse(struct NodeDll *runner){
  printf("[ NULL ] <=> ");
  while(runner != NULL){
    printf("[ %d ] <=> ",runner -> data);
    runner = runner -> prevAdd;
  }
  printf("[ NULL ]");
}
  

// insersal by index func
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;
  }
}


// deletion by index func
struct NodeDll *deleteAtIndex(struct NodeDll *head, int index ){
  
  struct NodeDll* runner;
  if(index == 0){
    head = head -> nextAdd;
    head -> prevAdd = NULL;
    (head->nextAdd)->prevAdd = head;
    return head;
  }
  
  else{
    runner = head;
    int runnerIndex = 0;
    while(runnerIndex != index - 1){
      
      runner = runner -> nextAdd;
      runnerIndex++;
    }
    struct NodeDll *runner2 = runner -> nextAdd;
    runner -> nextAdd = runner2 -> nextAdd;
    (runner2->nextAdd)->prevAdd = runner;
    free(runner2);

    return head;
  }
}

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;
  
  
  printf("1st traversal:\n");
  traverse(head);
  
  printf("\ninserting 15 at index 3:\n");
  head = insertAtIndex(head,15, 3);
  traverse(head);
  
  printf("\ndeletion of node at index 2 :\n");
  head = deleteAtIndex(head,2);
  traverse(head);
  
  printf("\nReverse\n");
  reverseTraverse(four);
  return 0;
}