Deleting a Node in a Linked List in C++
Introduction
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 twohour 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
 Singlylinked 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 :

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.
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; //statement1
start = start > next; //statement2
delete ptr; //statement3
}
}
Let us understand the code, in our code DeleteNodeBeg() is the function that we 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 the ptr pointer, now in the second statement of the 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;
}
Let us now look at some faqs based on the discussion above:
Frequently Asked Questions
What is a linked list in C++?
A linked list is a linear data structure that instead of storing data at contiguous memory locations, stores data at random locations, and each node is linked to the other by the use of pointers.
What are the applications of a linked list?
1. A linked list is used to implement Stack and Queues.
2. A linked list is used to implement hashing(open chain hashing).
3. A linked list is used to implement graphs(Adjacency list representation of graphs)
How do you delete a node in a linked list?
To delete a node from a linked list, we need to do the following steps.
 Find the previous node of the node to be deleted.
 Change the next pointer of the previous node.
 Free memory for the node to be deleted.
Conclusion
This article covered Deleting a Node in a LinkedList in C++. A good grasp of Linked Lists can be a huge plus point in a coding interview.
Check out the CodeStudio library for getting a better hold of the data structures and algorithms.
Recommended Reading:
 Advantages and Limitations of Linked List
 Implementing a Linked List in Java using Class
 Insertion Sort for Singly Linked List
 Quicksort on a Singly Linked List
 Unrolled linked list
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on CodeStudio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on CodeStudio.
Happy learning!