by Linked List is a data structure used for storing collection of data where successive elements are connected through pointers and the size of linked list can grow or shrink dynamically.
In short, Linked list can be thought as similar to array in which traversal can happen through pointers instead of indexes. Before going ahead have a look into Linked List Basics and Linked List Implementation.
Let’s have a look on basic class definition for Linked List.
class LinkedList
{
public:
int data;
LinkedList* next;
LinkedList (int data);
~LinkedList ();
};
/* Below function will print all nodes in a Linked List */
void print_linked_list (LinkedList* start)
{
if (!start)
{
cout << "Linked list is null, nothing to print" << endl;
return;
}
LinkedList* temp = start;
while (temp)
{
cout << " " << temp -> data;
temp = temp -> next;
}
cout << endl;
}
Delete Operation
Deleting a new node in any Linked List is called Delete Operation. Multiple variations of Linked List Delete operations are possible which are Listed below.
Deleting a node at the beginning
In this case head node needs to be deleted. After this operation next node of the current head node will become the 1st data node of the linked list.
Steps are as follows.
- Start from the head node of the Linked List.
- Store the next pointer of existing head node in a variable.
- Delete the current head node.
- Return the saved next pointer as the new head node.
Let’s look into the sample code.
void delete_start_node (LinkedList** start)
{
if (!start)
{
cout << "Nothing to delete" << endl;
return;
}
LinkedList* temp = *start;
*start = (*start) -> next;
delete temp;
}
Deleting a node in between Linked List
In this case, we need to first traverse through the linked list and searched the node which we need to delete.
Steps are as follows.
- Start from the head node of the Linked List.
- Traverse the linked list to search the node to be deleted.
- Change the next pointer of the previous node of the searched node to the next node of the searched node.
- Delete the searched node.
Let’s look into the sample code.
bool delete_searched_node (LinkedList** start, int searched_data)
{
LinkedList* temp = *start;
LinkedList* parent = *start;
while (temp)
{
if (temp -> data == searched_data)
{
cout << "Node found, going to delete" << endl;
parent -> next = temp -> next;
delete temp;
return true;
}
parent = temp;
temp = temp -> next;
}
cout << "Node not found, ignoring delete" << endl;
return false;
}
Deleting all Nodes from Linked List
In this case, we need to traverse through the linked list and delete every node.
Steps are as follows
- Start from the head node of the Linked List.
- Delete the head node and mark next node as head node.
- Repeat above steps till all the nodes have been deleted.
Let’s look into the sample code.
void delete_all_node (LinkedList** start)
{
LinkedList* temp = *start;
while (temp)
{
LinkedList* next = temp -> next;
delete temp;
temp = next;
}
*start = NULL;
}
Let’s use these functions in an example main functions to explain the usage of these functions. Few of the functions used below are explained in Linked List Insert operation and Linked List Traverse and Search article. Refer those before moving ahead.
int main()
{
LinkedList* start = NULL;
print_linked_list (start);
insert_at_begining (&start, 3);
insert_after_certain_element (start, 5, 6);
insert_after_certain_element (start, 7, 5);
insert_after_certain_element (start, 9, 8);
insert_after_certain_element (start, 11, 10);
insert_after_certain_element (start, 16, 11);
insert_after_certain_element (start, 2, 9);
insert_after_certain_element (start, 3, 2);
int searched_data = 5;
cout << "Searching element in linked list: " << searched_data << endl;
search_element (start, searched_data);
print_linked_list (start);
cout << "Deleting Head Node " << endl;
delete_start_node (&start);
print_linked_list (start);
cout << "Deleting Node 11" << endl;
delete_searched_node (&start, 11);
print_linked_list (start);
cout << "Deleting all Nodes" << endl;
delete_all_node (&start);
print_linked_list (start);
cout << "End check_delete_items_log" << endl;
}
Let’s analyze the output of this main function.
Linked list is null, nothing to print
Inserting node 5
Searched data not found, hence putting new node at the end
Inserting node 7
Inserting node 9
Searched data not found, hence putting new node at the end
Inserting node 11
Searched data not found, hence putting new node at the end
Inserting node 16
Inserting node 2
Inserting node 3
Searching element in linked list: 5
Found the searched data: 5
3 5 7 9 2 3 11 16
Deleting Head Node
5 7 9 2 3 11 16
Deleting Node 11
Node found, going to delete
5 7 9 2 3 16
Deleting all Nodes
Linked list is null, nothing to print
