Question

C++ How would you delete a node in a linked list? from beginning, end, and a node somewhere in the middle without breaking the links to the next or previous nodes

Answer 1

SOURCE CODE:

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
  
/* structure of a linked list node */
class Node
{
public:
int data;
Node *next;
};

/*function to insert a node at the beginning */
void push(Node **head_ref, int new_data)
{
Node *new_node = new Node();
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}

void deleteNode(Node *head, Node *n)
{
// When node to be deleted is beginning node
if(head == n)
{
if(head->next == NULL)
{
cout << "There is only one node." <<
" The list can't be made empty ";
return;
}
  
/* Copy the data of next node to head */
head->data = head->next->data;
  
// store address of next node
n = head->next;
  
// Remove the link of next node
head->next = head->next->next;
  
// free memory
free(n);
  
return;
}
  
// When node to be deleted is somewhere in the middle
Node *prev = head;
while(prev->next != NULL && prev->next != n)
prev = prev->next;
  
// Check if node really exists in Linked List
if(prev->next == NULL)
{
cout << "\nGiven node is not present in Linked List";
return;
}
  
// Remove node from Linked List
prev->next = prev->next->next;
  
// Free memory
free(n);
  
return;
}

// When node to be deleted is end node
Node* removeLastNode(struct Node* head)
{
if (head == NULL)
return NULL;
  
if (head->next == NULL) {
delete head;
return NULL;
}
  
// Find the second last node
Node* second_last = head;
while (second_last->next->next != NULL)
second_last = second_last->next;
  
// Delete last node
delete (second_last->next);
  
// Change next of second last
second_last->next = NULL;
  
return head;
}

/* function to print a linked list */
void printList(Node *head)
{
while(head!=NULL)
{
cout<<head->data<<" ";
head=head->next;
}
cout<<endl;
}

int main()
{
Node *head = NULL;
  
/* Create following linked list
1->2->3->4->5->6->7->8 */
push(&head,8);
push(&head,7);
push(&head,6);
push(&head,5);
push(&head,4);
push(&head,3);
push(&head,2);
push(&head,1);
  
cout<<"Given Linked List: ";
printList(head);   
  
/* Let us delete the beginning node */
cout<<"\nDeleting the beginning node ";
deleteNode(head, head);
  
cout<<"\nModified Linked List: ";
printList(head);
  
/* Let us delete the node which is somewhere in the middle */
cout<<"\nDeleting node "<< head->next->next->data<<" ";
deleteNode(head, head->next->next);
  
cout<<"\nModified Linked List: ";
printList(head);
  
/* Let us delete the end node */
cout<<"\nDeleting the end node ";
removeLastNode(head);
  
cout<<"\nModified Linked List: ";
printList(head);
  
return 0;
}

SOURCE CODE IMAGES:

OUTPUT IMAGE: