Question

Write an algorithm in pseudo code to find one element and delete it in a doubly linked list. Your algorithm will print the original list, request the user to put in an element to be deleted, then print the final list after the deletion is done. If the element doesn’t exist in the list, print "XXX is not in the list" where "XXX" should be the one you received from the user.

Use the following as your test cases to evaluate whether your algorithm works correctly:

if you have a linked list: 3<->2<->0,

with user input 5, your algorithm should print "5 is not in the list".

with user input 2, your algorithm should print  "3<->0".

if your linked list is empty, with user input 5, your algorithm should print "5 is not in the list".

Answer 1

Algorithm:
   Let structure of DLL node be:
   struct node{
       int data;
       struct node *left,*right;
   }

   Search linearly for the element in the doubly linked list whenever we found it assign prev = node -> left and next = node -> right and perform following operations.
   prev -> right = next
   next -> left = prev
   then free the node.

Pseduocode:
   removeElement(int value){
       curr = head
       //Traverse through DLL
       while(curr){
           if(curr -> data == value){
               break
           }
           curr = curr -> right
       }

       if(curr -> right is NULL){
           //We haven't found the element
           print("%d value is not in the list",value);
           return
       }
       //We have found the node with value
       prev = curr -> left
       next = curr -> right
       //Handle edge cases that is node at end or start
       if(prev is NULL){
           head = head -> right;
       }
       if(next is NULL){
           curr -> next = NULL;
       }
       //Both exist
       if(prev and next){
           prev -> right = next
           next -> left = prev
           free(curr)
       }
       //Printing the DLL
       curr = head
       while(curr){
           print(curr -> data,"<->")
           curr = curr -> right
       }
   }
Sample Input:
   DLL = 3<->2<->0
   removeElement(5) -> "5 is not in the list"
   removeElement(2) -> 3<->0