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...
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 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”
in C programming language Write a function removeDups that removes all duplicates in a given array...
in C programming language Write a function removeDups that removes all duplicates in a given array of type int. Sample Test Case: input -> {1,2,2,2,3,3,4,2,4,5,6,6} output -> {1,2,3,4,5,6,0,0,0,0,0,0} More specifically, the algorithm should only keep the first occurance of each element in the array, in the order they appear. In order to keep the array at the same length, we will replace the removed elements with zeros, and move them to the end of the array.
THE FOLLOWING IS CODED IN C Write a function that sets each element in an array...
THE FOLLOWING IS CODED IN C Write a function that sets each element in an array to the sum of the corresponding elements in two other arrays. That is, if array 1 has the values 2,4, 5, and 8 and array 2 has the values 1, 0, 4, and 6, the function assigns array 3 the values 3, 4, 9, and 14. The function should take three array names and an array size as arguments. Test the function in a...
C++ 9.12: Element Shifter Write a function that accepts an int array and the array’s size...
C++ 9.12: Element Shifter Write a function that accepts an int array and the array’s size as arguments. The function should create a new array that is one element larger than the argument array. The first element of the new array should be set to 0. Element 0 of the argument array should be copied to element 1 of the new array, element 1 of the argument array should be copied to element 2 of the new array, and so...
C Write a function that appends the second character array to the first, replaces the first...
C Write a function that appends the second character array to the first, replaces the first array with the result and replaces the second character array with the original first array. For example, if the first character array is "hello" and the second is "world" at the end of the function the new value of the first character array should be"helloworld" and the second array should be "hello". If the input is invalid the function should return 1. Otherwise, the...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT