Deleting a Node in a Linked List in C++

Deleting a Node in a Linked List in C++
Deleting a Node in a Linked List in C++

Each element in the linked list is known as a node.

A node consists of two parts INFO and POINTER. The work of the INFO part is to store data, whereas the POINTER stores Address of the next node and its work is to point to the next element.

A linked list is a linear collection of data elements, called nodes pointing to the next nodes by means of pointers. Have you ever thought about why we call it a linked list? The answer is simple because it stores
data in sequence i.e in linked allocation, where the address of the next node is stored in the
previous pointer.

Let us understand the LL more clearly with the help of a story. In a class there were 40 students, their class teacher wanted to take them to watch a movie. She booked 40 tickets by calling the manager of the cinema hall. The manager booked one entire row having 40 seats in it. The teacher took their students in the hall and the movie started but because of some urgent work, the class teacher had to leave the hall, so she noted down the seat number and row number of the first student so that she can easily find her students.

After the two-hour movie gets over and the class teacher comes and goes that noted seat number and counts 40 students from there and takes them with herself. Again a year later they make a plan to watch a movie this time an entire row is not empty so they got seats scattered in the hall, this time also teacher has some work but this time there is a challenge in front of the teacher to note the seat number and row number of every student so that she can find them easily.

But the teacher is very smart, she takes out some slips and distributes them to all students, she noted down the seat number of the first student and told the student to store the seat number of the next student. In this way, each student noted the seat number of the next student. And when the teacher came by with the help of each student she gathered all the students and took them back.

The conclusion of the story is when the students were seated in a row it was similar to an array. In the array, all the elements are stored in the contiguous location. When the students were seated here and there having a slip containing the sitting number of the next student it was similar to the linked list. In the linked list each element stores the address of the next element.

Why a linked list?

When we are not sure about the size beforehand, we need a data structure that stores the memory at runtime, the linked list does so. So we use a linked list when exact numbers of elements are not known to us.

As we have already discussed that there are two types of linked list namely

  • Singly-linked list
  • Doubly linked list
    In a singly linked list, the node contains only one pointer (next) but in doubly linked list node contains
    two pointers ( prev and next).

There are many operations which can be performed in linked lists like Insertion, Deletion, Traversal among them let us talk about Deletion.

Deletion in a linked list
In a linked list, there is three possibilities for the deletion of a node :

blog banner 1
  • If the node to be deleted happens to be the first node.
  • If the node happens to be in the middle of the list.
  • If the node is at the end of the list.
    Let us discuss deletion in linked list briefly:
    For the deletion of a node from the list, it involves two major steps
    • Step1: Search for the availability of the node in the list.
    • Step2: If available, make its previous node pointing to its next node.
Linked List
Linked List

Deleting node from the beginning of the list

The function for the deletion of the node is DeleteNodeBeg(). Let’s go through its code.

//deleting node from the beginning of the list.
Void DeleteNodeBeg()
{
if(start==null)
cout<<”Underflow”<<”\n”;
else
{
ptr = start; //statement-1
start=start -> next; //statement-2
delete ptr ; //statement-3
}
}

Let us understand the code, in our code DeleteNodeBeg() is the function which we had created to delete the first node. In this start is the pointer which is checking whether the list contains any element or it is empty. As it found that any element is stored in the list, it goes to the else part of the program.

Here the address stored in the start pointer is assigned to the ptr pointer, now the start pointer is empty as the address stored in it is assigned to ptr pointer, now in the second statement of else block, the address of the next node is assigned to the start pointer, in third the statement, we deleted the ptr pointer as it stores the address of the first node which we want to delete.

Deleting node from the middle of the list

If the length of the linked list is odd then delete (( n+1)/2)th term of the linked list and if the list is
of even length then delete the (n/2+1)th term of the linked list.
To delete a the middle note we have to follow some points:

  • Let two pointers namely ptr1 and ptr2.
  • Each time increment ptr1 by 1 and ptr2 by 2.
  • Repeat step 2 until ptr2 goes to the end of the linked list.
  • When ptr2 is at the end of the list, at the same time ptr1 will be at the middle of the list.
  • Then delete the middle node,i.e. ptr1.
//deleting node from the middle of the list
Void DeleteNodeMid()
{
if(start==null)
cout<<”Underflow”<<”\n”;
else
{
ptr2=head->next;
ptr1=head;
while(ptr2 && ptr2 -> next && ptr2 -> next -> next)
ptr1=ptr1 -> next;
ptr2=ptr2 -> next -> next;
}
Ptr1 -> next= ptr1 -> next -> next;
}

Deleting a node from the end of the list

As we know that in a it, the last node of the linked list contains data in its info part and NULL in its pointer part. To delete the last node we should find the second last node of the list and make its pointer part carry NULL.

Algorithm:
1. If the first node is null or there is only one node, then return null.
2. Find Second last node.

  • Delete last node.
  • Change next of second last in NULL.
/* Function to remove the last node
of the linked list */
Void DeleteLastNode()
{
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;
}

To explore more articles about Data Structures, check out our blog’s section.

By Deepak Jain