Answer to Question #226744 in C for mikel

Question

Implement doubly linked list using dummy node with following operations.

1. ins key_of_y key_of_x (insert command)

/*

Insert node x after node y. First search node y using a key value. If node y is found then insert node x after node y. Otherwise insert node x after dummy node.

*/

2. del key_of_x (remove command)

/*

Search a node x using a key value then delete it from the list if found.

*

3. sch search_key (search command)

/*

Search whole linked list against a key number.

*/

4. shw (showall command)

/*

Traverse whole linked list and print all key values.

*/

5. ext (exit command)

/*

Exit from the program.

Input:

ins 3 1

ins 1 2

ins 1 3

ins 2 4

ins 5 0

ins 0 2

shw

del 2

del 2

del 2

del 0

shw

sch 1

sch 2

ext

Output:

INSERT after dummy node.

INSERT after 1.

INSERT after 1.

INSERT after 2.

INSERT after dummy node.

INSERT after 0.

0 2 1 3 2 4

Node with key value 2 is DELETED.

Node with key value 2 is DELETED.

DELETE not possible.

Node with key value 0 is DELETED.

1 3 4

Node with key value 1 is FOUNDED.

Not FOUND.

Answer 1

#include<stdio.h>
struct Node {
    int key;
    struct Node* nextNode;
    struct Node* prevNode;
};
 


void deleteNode(struct Node** headRef, struct Node* dele)
{
  
    if (*headRef == NULL || dele == NULL)
        return;
 
   
    if (*headRef == dele)
        *headRef = dele->nextNode;
 
    
    if (dele->nextNode != NULL)
        dele->nextNode->prevNode = dele->prevNode;
 
    
    if (dele->prevNode != NULL)
        dele->prevNode->nextNode = dele->nextNode;
 
    
    free(dele);
}
 


void deleteNodeAtGivenPos(struct Node** headRef, int data)
{
    
    if (*headRef == NULL || data <= 0)
        return;
 
    struct Node* currentNode = *headRef;
    int i;
 
    
    for ( i = 1; currentNode != NULL && i < data; i++)
        currentNode = currentNode->nextNode;
 
    
    if (currentNode == NULL)
        return;
 
    
    deleteNode(headRef, currentNode);
}
 


void pushNode(struct Node** headRef, int data)
{
    
    struct Node* newNode =
         (struct Node*)malloc(sizeof(struct Node));
 
    
    newNode->key = data;
 
    
    newNode->prevNode = NULL;
 
 
    newNode->nextNode = (*headRef);
 
    
    if ((*headRef) != NULL)
        (*headRef)->prevNode = newNode;
 
    (*headRef) = newNode;
    free(dele);
}
 


void displayList(struct Node* head1)
{
    while (head1 != NULL) {
    	printf("\n%d\n",head1->key);
        
        head1 = head1->nextNode;
    }
}


void insertAfter(struct Node* node, int data)
{
    
    if (node == NULL) {
        printf("the given previous node cannot be NULL");
        return;
    }
 
   
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
 
    
    newNode->key = data;
 
    
    newNode->nextNode = node->nextNode;
 
    node->nextNode = newNode;
 
   
    newNode->prevNode = node;
 
    
    if (newNode->nextNode != NULL)
        newNode->nextNode->prevNode = newNode;
}


int main()
{
    
    struct Node* head1 = NULL;
 
    
    pushNode(&head1, 5);
    pushNode(&head1, 2);
    pushNode(&head1, 4);
    pushNode(&head1, 8);
    pushNode(&head1, 10);
 
    
    displayList(head1);
 
    int n = 2;
 
   
    deleteNodeAtGivenPos(&head1, n);
 
   
    printList(head1);
   insertAfter(head1->nextNode, 12);
 
    printf("Created DLL is: ");
    printList(head1);
    return 0;
}