Question

In: Computer Science

write a c++ member function that removes the FIRST OCCURENCE of a SPECIFIC ELEMENT in a...

write a c++ member function that removes the FIRST OCCURENCE of a SPECIFIC ELEMENT in a linked list. After attemtped removal return the SIZE of the linked lost whether or not the removal was successful.

Solutions

Expert Solution

The following is a code to delete the first occurence of the key in a singly linked list. The language is c++.  

#include <iostream>

using namespace std;

#include <bits/stdc++.h> 

// A linked list node 
class Node{ 
public: 
        int data; 
        Node* next; 
}; 

// push a new node to the linked list
void push(Node** head, int new_data) 
{ 
        Node* new_node = new Node(); 
        new_node->data = new_data; 
        new_node->next = (*head); 
        (*head) = new_node; 
} 

//function to delete the first occurence of the linked list
void deleteNode(Node** head, int key) 
{ 
        
        // Store head node 
        Node* temp = *head; 
        Node* prev = NULL; 
        
        // If head node itself is the key
        if (temp != NULL && temp->data == key) 
        { 
                *head = temp->next; // Changed head 
                delete temp;             // free old head 
                return; 
        } 

        // Else Search for the key to be deleted, 
        while (temp != NULL && temp->data != key) 
        { 
                prev = temp; 
                temp = temp->next; 
        } 

        // If key was not present in linked list 
        if (temp == NULL) 
                return; 

        // Unlink the node from linked list 
        prev->next = temp->next; 

        delete temp; 
} 


void printList(Node* node) 
{ 
        while (node != NULL) 
        { 
                cout << node->data << " "; 
                node = node->next; 
        } 
} 

int size(Node* head)  
{  
    int size = 0; // Initialize size  
    Node* current = head; // Initialize current  
    while (current != NULL)  
    {  
        size++;  
        current = current->next;  
    }  
    return size;  
} 

// Driver code 
int main() 
{ 
        
        // Start with the empty list 
        Node* head = NULL; 

        //push the elements to the linked list 
        push(&head, 4); 
        push(&head, 2); 
        push(&head, 3); 
        push(&head, 8);
        push(&head, 3);

        puts("The linked list "); 
        printList(head); 

        deleteNode(&head, 3); 
        puts("\nLinked List after Deletion: "); //after deletion of first occurence of number 3
        
        printList(head); 
        
        
 cout<<"\nsize of the list is "<< size(head); //print the size of the linked list
        
        return 0; 
} 

Output :

* Doubly Linked List:

  • In doubly Linkedlist we have next pointer as well as previous pointer. The previous pointer points to the previous node. Advantage over singly linkedlist is that we can traverse doubly linkedlist in backward as well as forward direction.
  • The deletion in doubly linkedlist is easier than singly linkedlist. In the above exapmle of singly linkedlist we do not have the previous pointer. So to get the previous pointer we have to traverse the entire linkedlist,
  • In doubly linkedlist we have the previous pointer, so deletion is easier.
  • Consider we want to delete a node 2 from the above image.
  • Then we just have to change the pointers as 1)Node 1's next should point to 3. And 3's previous should point to 1.

Code :

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int data;
    struct Node* next;
};
/* Function to push a node at beginning */
void push(struct Node** head, int data)
{
    struct Node* curr = new Node;
    curr->data = data;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //If this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        
}
 
//display linked list
void print(struct Node**head)
{
    struct Node *temp= *head;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            {
                cout<<temp->data<<"->";
            }
            else
            {
                cout<<temp->data;
            }
            temp=temp->next; //move to next node
        }
       
    cout<<endl;
}
 
void deleteFirstOccurence(struct Node** head, int key)
{
    // Initialize previous of Node to be deleted
    struct Node* x = NULL;
    struct Node* temp = *head;
    
    
    while(temp!=NULL && temp->data != key)
    {
            x = temp;
        
        temp = temp->next;
    }
    //key occurs atleast once except head node
    if(x)
    {
        //delete x by copying of next to it.
        //delete next
        temp = x->next;
        x->next = x->next->next;
        delete temp;
    }
    //key occurs at head
    else
    {
        if (*head && (*head)->data == key )
        {
             struct Node * temp = *head;
            *head =  (*head)->next;
            delete temp;
        }
    }
}

//Main function
int main()
{
   
    struct Node* head = NULL;//Initial empty List
    push(&head, 14);
    push(&head, 11);
    push(&head, 3);
    push(&head, 10);
    push(&head, 4);
    push(&head, 1);
    push(&head, 3);
    push(&head, 2);
    push(&head, 7);           
   
    cout<<"Doubly linked list ";
    print(&head);
    
   deleteFirstOccurence(&head, 3);
    cout<<"\nAfter deleting first occurence of 3 \n";   
    print(&head);
    return 0;
}

Output:


Related Solutions

write a c++ member function that removes the first instance of a specific element in a...
write a c++ member function that removes the first instance of a specific element in a linked list and then return the size of the list after the removal whether it was successful or not.
Write a c++ member function that sequentially searches for a specific element in a doubly linked...
Write a c++ member function that sequentially searches for a specific element in a doubly linked list. return the position if found or -1 is the element cannot be found.
Write a c++ member function that attempts to insert a NON DUPLICATE element to a doubly...
Write a c++ member function that attempts to insert a NON DUPLICATE element to a doubly linked list, After the attempted insertion return the SIZE of the doubly linked list whether or not the insertion was successful.
3.) The function remove of the class arrayListType removes only the first occurrence of an element....
3.) The function remove of the class arrayListType removes only the first occurrence of an element. Add the function removeAll as an abstract function to the class arrayListType, which would remove all occurrences of a given element. Also, write the definition of the function removeAll in the class unorderedArrayListType and write a program to test this function. 4.) Add the function min as an abstract function to the class arrayListType to return the smallest element of the list. Also, write...
C++ 1. The function removeAt of the class arrayListType removes an element from the list by...
C++ 1. The function removeAt of the class arrayListType removes an element from the list by shifting the elements ofthe list. However, if the element to be removed is at the beginning ofthe list and the list is fairly large, it could take a lot ofcomputer time. Because the list elements are in no particular order, you could simply remove the element by swapping the last element ofthe list with the item to be removed and reducing the length of...
Program in C Write a function that takes a string as an argument and removes the...
Program in C Write a function that takes a string as an argument and removes the spaces from the string.
** * Write a recursive function that removes the first k even numbers * from the...
** * Write a recursive function that removes the first k even numbers * from the stack. If there are less than k even elements in the stack, * just remove all even elements. Do not use any loops or data structures * other than the stack passed in as a parameter. * @param stack * @param k * @return Returns the number of elements removed from the stack. */ public static int removeEvenNumbers(Stack<Integer> stack, int k) { return 0;...
Write a C program for the recursive algorithm that removes all occurrences of a specific character...
Write a C program for the recursive algorithm that removes all occurrences of a specific character from a string. (please comment the code)
haskell : write a function that reverse the first three element of a list, but not...
haskell : write a function that reverse the first three element of a list, but not the rest. example [1,2,3,4,5,6] == [3,2,1,4,5,6]
[ Write in C, not C++] Define a function char* deleteSymbol(char *s, char x) that removes...
[ Write in C, not C++] Define a function char* deleteSymbol(char *s, char x) that removes the character x from string s. For s[] = “America”, a call to deleteSymbol(s, ‘a’) converts s[] = “Ame”
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT