Question

Linked Lists:

Suppose you have a doubly linked list with both head and tail pointers, that stores integers. Implement a non-recursive function that takes a linked list, searches for an integer, and removes the node with the first occurrence of that integer and also removes the node directly after it regardless of value . This function will return to address of the resulting list. You ca n assume that there will be at least three nodes, and if there is a node to be remove it will be, at the latest, the third to last node.

Node*deleteTwo(Node*list, int valal ){

/*example usage might be:

int main() {
    Node* head;
    Node* tail;
    //Some code to create a list with head 3, 2, 1 tail
    head = deleteTwo(head,3);
    //The list is now head 1 tail

}*/

Answer 1

Code:-

void deleteTwo(Node *list, int val)

{

    // if te list is empty

    if( list == NULL )

        return;

   

    // if the node to be deleted is the first node in the list

    if( list->data == val )

    {

        // remove the node

        list = list->next;

       

        // delete the previous head node

        delete list->prev;

       

        list->prev = NULL;

       

        // if there is a node after the previous head of the list

        if( list != NULL )

        {

            // remove the node

            list = list->next;

           

            // delete the previous head node

            delete list->prev;

           

            list->prev = NULL;

        }

    }

    else

    {

        // point trav to the first node of the list

        Node *trav = list;

       

        // traverse the list untill the list ends or trav points to

        // the node with value val

        while( trav != NULL && trav->data != val )

            // go to next node

            trav = trav->next;

           

        // if the list doesn't contain val

        if( trav == NULL )

            return;

       

        // remove the node

        trav->prev->next = trav->next;

       

        // make trav point to the next node of th etraget node

        trav = trav->next;

       

        // make the target node point by temp

        Node *temp = trav->prev;;

       

        // adjust the prev pointer

        trav->pre = trav->pre->pre;

       

        // delete the previous head node

        delete temp;

       

       // if there is a node after the previous target node

        if( list != NULL )

        {

            // remove the node

            trav->prev->next = trav->next;

           

            // make trav point to the next node of th etraget node

           trav = trav->next;

           

            // make the target node point by temp

            Node *temp = trav->prev;;

           

            // adjust the prev pointer

            trav->pre = trav->pre->pre;

           

            // delete the previous head node

            delete temp;

        }

    }

}