Question

In C++, write a member method delete() that deletes a node from a linked list at a random position. (It should first randomly generate that position. and then delete that node).

Answer 1

The required method is highlighted as bold in the below source code:

#include <iostream>

using namespace std;

//structure declaration
struct node
{
int data;
struct node *next;
};

struct node *head = NULL;

//function to count the size of the linked list
int size()
{
//declare a structure type variable and initialize with head
struct node *ptr = head;
int count = 0;
while(ptr != NULL)
{
count++;
ptr = ptr->next;
}
return count;
}

//function to check if list is empty or not
bool isEmpty()
{
//declare a structure type variable and initialize with head
struct node *ptr = head;
int count = 0;
while(ptr != NULL)
{
count++;
ptr = ptr->next;
}
if(count==0)
return true;
return false;
}

//function to print the node value with address
void printList()
{
//declare a structure type variable and initialize with head
struct node *ptr = head;

while(ptr != NULL)
{
//display the node address, value stored in node and the address of the next node
cout<<ptr->data<<" ";
  
//assign the pointer to the next node
ptr = ptr->next;
}
}

//function to add a new node at the end of the linked list
void addLast(int data)
{
//declare a structure type variable and initialize with head
struct node *ptr = head;
struct node *link = (struct node*) malloc(sizeof(struct node));
  
while(ptr != NULL)
{
//assign the pointer to the next node
ptr = ptr->next;
}
  
//assign the new node data field with the paramener value
link->data = data;
//assigne the new node address field with the head pointer
link->next = NULL;
  
//assign the head node to the new node
ptr->next = link;
}

//function to add a new node at the beginning of the linked list
void addFirst(int data)
{
struct node *link = (struct node*) malloc(sizeof(struct node));
  
//assign the new node data field with the paramener value
link->data = data;
//assigne the new node address field with the head pointer
link->next = head;
  
//assign the head node to the new node
head = link;
}

//function to delete a node
void delete(int pos)
{
struct node *headNode = head;
if (headNode == NULL)
return;
struct node* temp = headNode;
  
if (pos == 0)
{
headNode = temp->next;   
free(temp);
return;
}
  
for (int i=0; temp!=NULL && i<pos-1; i++)
temp = temp->next;
if (temp == NULL || temp->next == NULL)
return;
  
struct node *next = temp->next->next;

free(temp->next);
  
temp->next = next;
}

int main()
{
//insert value
addFirst(15);
addFirst(10);
addFirst(20);
addFirst(30);
  
int sz = size();
  
int loc = rand() % sz;
  
delete(loc);
  
//display the linked list by calling printList() function
cout<<"The linked list is: "<<endl;
printList();

return 0;

}

OUTPUT:

The linked list is:
30 20 10