Deletion in Linked List

Deleting elements from different positions in a linked list, including from the beginning, end, and specific positions

Deletion At Beginning

1

Check for Empty List

  • If the list is empty (head == NULL), return immediately.
2

Save the Current Head

  • Store the current head node in a temporary pointer (del).
3

Move Head to Next Node

  • Update head to point to the next node (head = head->next).
4

Delete the Old Head

  • Free the memory of the old head using delete.
//deletionatbeginning.cpp
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data)
{
    this->data = data;
    this->next = NULL;
}
};
void insertAtTail(Node *&head, int data)
{
if (head == NULL)
{
    head = new Node(data);
    return;
}
Node *temp = new Node(data);
Node *curr = head;
while (curr->next)
{
    curr = curr->next;
}
curr->next = temp;
}
void deleteAtBeginning(Node *&head)
{
if (head == NULL)
    return;
Node *del = head;
head = head->next;
delete del;
}
void display(Node *head)
{
while (head != NULL)
{
    cout << head->data << " ";
    head = head->next;
}
}
int main()
{
Node *head = NULL;
insertAtTail(head, 1);
insertAtTail(head, 2);
insertAtTail(head, 3);
insertAtTail(head, 4);
display(head);
// 1->2->3->4
deleteAtBeginning(head);
cout<<endl;
display(head);
// 2->3->4
}

Deletion At Position

1

If deleting the head node `(pos == 0)`:**

  • Delete the head node.
  • Update head to the next node or set it to NULL if the list is now empty.
2

If `pos` is valid and not the head

Traverse to the node just before the position (pos - 1):

  • Start at the head and move to the (pos - 1)th node using a loop.

  • Save the reference to the node at pos in a temporary pointer.

  • Update the previous node's next pointer to skip the node at pos.

  • Delete the node at pos to free memory.

//deletionatposition
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data)
{
    this->data = data;
    this->next = NULL;
}
};
void insertAtTail(Node* &head,int data){
if(head==NULL){
    head= new Node(data);
    return;
}
Node *temp=new Node(data);
Node *curr=head;
while(curr->next){
    curr=curr->next;
}
curr->next=temp;
}
void deletionAtPosition(Node* &head,int pos){
if(pos==0){
    delete head;
    head=NULL;
    return;
}
int curr=0;
Node*currNode=head;
while(curr!=pos-1){
    currNode=currNode->next;
    curr++;
}
Node* del=currNode->next;
currNode->next=currNode->next->next;
delete del;
}
void display(Node* head){
while(head!=NULL){
    cout<<head->data<<" ";
    head=head->next;
}

}
int main(){
 Node *head = NULL;
insertAtTail(head, 1);
insertAtTail(head, 2);
insertAtTail(head, 3);
insertAtTail(head, 4);
display(head);
// 1->2->3->4
cout<<endl;
deletionAtPosition(head,2);
display(head);
//1->2->4
}

Deletion At Tail

1

Check if the list is empty

  • If head == NULL, the list is empty, so return (nothing to delete).
2

Check if the list has only one node

If head->next == NULL, delete the only node and set head = NULL (the list becomes empty).

3

If the list has more than one node

  • Traverse the list to find the second-last node (i.e., where secondlast->next->next == NULL).
  • Set secondlast->next = NULL (remove the last node).
  • Delete the last node.
// deletionatend.cpp
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data)
{
    this->data = data;
    this->next = NULL;
}
};
void insertAtTail(Node *&head, int data)
{
if (head == NULL)
{
    head = new Node(data);
    return;
}
Node *temp = new Node(data);
Node *curr = head;
while (curr->next)
{
    curr = curr->next;
}
curr->next = temp;
}
void deleteAtEnd(Node *&head)
{
if (head == NULL)
    return;
if (head->next == NULL)
{
    delete head;
    head=NULL;
    return;
}
Node *secondlast = head;
while (secondlast->next->next != NULL)
{
    secondlast = secondlast->next;
}
Node *del = secondlast->next;
secondlast->next = NULL;
delete del;
}
void display(Node *head)
{
 if (head == NULL) {
    cout << "List is empty!" << endl;
    return;
}
while (head != NULL)
{
    cout << head->data << " ";
    head = head->next;
}
}
int main()
{
Node *head = NULL;
insertAtTail(head, 1);
insertAtTail(head, 2);
insertAtTail(head, 3);
insertAtTail(head, 4);
display(head);
// 1->2->3->4
deleteAtEnd(head);
cout<<endl;
display(head);
// 1->2->3
}