How to Delete a Node in a Linked List in C++
This article will discuss the method of how to implement a function that deletes a given node in a linked list C++.
Implement a Function to Delete a Given Node in a Linked List
In this article, we implement a singly linked list from scratch without utilizing the containers from STL. Thus, we need to define some necessary functions to manage nodes in a linked list.
The insertNode element is the core function that needs to be invoked to create a new linked list. Since we need to store the head of the list, the insertNode returns the pointer to the node of type ListNode. The latter is the minimal representation of the linked list node. It only contains a pointer to the next node and the string data object.
During the testing and demonstration of the program, it’s important to have some utility functions to display some messages to the user console. In this case, the printNodes element is utilized to print all the nodes in the given list structure. Additionally, we need to deallocate every existing node in the list on program exit using the freeNodes function when allocating new nodes on the dynamic memory.
Once we constructed a list with the arbitrary data as shown in the main function of the following code snippet, we are ready to invoked deleteNode, which implements the node removal operation. The removal of a node requires several corner cases to be handled in it. Namely, the scenario when the given node is the same as the head of the list and the other one when the given node is the only node in the list.
In the latter scenario, we can just call the delete operator on the node pointer and return from the function. Although it’s important to assign nullptr to the address because this will help us add new elements to the same head variable in the main function.
On the other hand, removing the head node when there are other nodes in the list is relatively tricky. We have to copy the contents of the second node to the head node and delete the former one. Notice that each case returns the EXIT_SUCCESS value to indicate a successful function call.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, head);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Output:
node 0 - data: Xenial
node 1 - data: Artful
-----------------------------------
node 0 - data: Artful
The remaining function code implements the regular case, where the given node is unhooked from the list chain and then deallocated using the delete operator. Note, though, this operation requires the previous node to be found, which is the linear time operation for every node except from the head of the list. Usually, one should store the end of the list in the linked list structure in order to guarantee the constant time removal for the end of the list.
The following code snippet demonstrates a different main function scenario, where a node is removed from the middle of the list.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next{};
string data;
};
struct ListNode *insertNode(struct ListNode *root, string data) {
auto new_node = new ListNode;
if (root) {
while (root->next) root = root->next;
new_node->next = nullptr;
new_node->data = std::move(data);
root->next = new_node;
return root->next;
}
new_node->next = nullptr;
new_node->data = std::move(data);
return new_node;
}
int deleteNode(struct ListNode *root, struct ListNode *node) {
if (node == nullptr || root == nullptr) return EXIT_FAILURE;
if (root == node) {
if (root->next == nullptr) {
delete node;
root = nullptr;
return EXIT_SUCCESS;
}
node = root->next;
root->data = root->next->data;
root->next = root->next->next;
delete node;
return EXIT_SUCCESS;
}
auto prev = root;
while (prev->next != node && prev->next != nullptr) {
prev = prev->next;
}
prev->next = node->next;
delete node;
return EXIT_SUCCESS;
}
void freeNodes(struct ListNode *root) {
struct ListNode *tmp = nullptr;
while (root) {
tmp = root;
root = root->next;
delete tmp;
}
}
void printNodes(struct ListNode *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct ListNode *head = nullptr;
head = insertNode(head, "Xenial");
auto iter = insertNode(head, "Bionic");
insertNode(head, "Artful");
printNodes(head);
cout << " ----------------------------------- " << endl;
deleteNode(head, iter);
printNodes(head);
freeNodes(head);
return EXIT_SUCCESS;
}
Output:
node 0 - data: Xenial
node 1 - data: Bionic
node 2 - data: Artful
-----------------------------------
node 0 - data: Xenial
node 1 - data: Artful
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook