Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
C++ implementation
3.2.
Complexities
3.2.1.
Time complexity
3.2.2.
Space complexity
4.
Frequently Asked Questions
4.1.
What is a linked list in C++?
4.2.
What are the applications of a linked list?
4.3.
How do you delete a node in a linked list?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Deletion of a Linked List

Author Shreya Deep
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Linked List

Introduction

A linked list is a type of linear data structure that uses nodes to store the data. Each node in a linked list is a structure-defined data type that consists of data and a pointer referencing the address of the next node.

illustrative_diagram

It does the insertion and deletion operations faster.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.

Problem Statement

Given a linked list, delete it, i.e., delete all its nodes.

For example,

INPUT : 2->1->3->4->5

OUTPUT:  NULL

After deleting the whole linked list, nothing will remain, thus NULL.

INPUT : 2->4

OUTPUT:  NULL

After deleting the whole linked list, nothing will remain, thus NULL.

Solution Approach

Iterate through the linked list nodes and keep deleting each node one by one. The thing to be careful about here is that when you delete a node, you loose its next node address also. Therefore, here, we’ll store the address of the next node of the current node prior to deleting the current node. And then, for moving to the next node, we’ll use that stored address. 

Steps are:

  • Create a linked list. For creating the linked list and inserting the elements into it, we’ll follow the steps as in this article. 
  • Call the delete_linked_list function by passing the reference to the pointer of the head. In this function:
  • Create two nodes, current, and temp. Initialize current to head.
  • Start traversing the linked list. While current is not equal to NULL, 
    • Store the next of the current node in temp. temp=current->next.
    • Free current node. This will delete the current node from the assigned memory.
    • Move to the next of the current node by doing current = temp.

C++ implementation

Below is the C++ implementation of the delete_linked_list function:

// Function to delete the linked list
void delete_linked_list(Node **head){
   Node* current = *head; // Initialize the current node to head
   Node* temp = NULL; //// Initialize the temp node to NULL

   while (current != NULL) // Traverse the whole list and keep deleting the elements one by one
   {
       temp = current->next; // Store the next of the current node somewhere in 
       // a temporary node, so that we don't its address.
       free(current);
       current = temp;
   } 
   // Lastly update head to null
   *head = NULL;
}
You can also try this code with Online C++ Compiler
Run Code

C++ implementation by creating the list and then deleting it: 

#include<iostream>
using namespace std;
class Node{
   public:
   int data; 
   Node *next;
   Node(int x){
       this->data=(x);
       next==NULL;
   }
};
// Function to delete the linked list
void delete_linked_list(Node **head){
   Node* current = *head; // Initialize the current node to head
   Node* temp = NULL; //// Initialize the temp node to NULL

   while (current != NULL) // Traverse the whole list and keep deleting the elements one by one
   {
       temp = current->next; // Store the next of the current node somewhere in 
       // a temporary node, so that we don't its address.
       free(current);
       current = temp;
   } 
   // Lastly update head to null
   *head = NULL;
}
int main(){
   int n; // Number of elements in the linked list 
   cin>>n;
   Node *head=NULL; // Head of the linked list 
   Node *tail=NULL; // Tail of the linked list 
   // Creating the linked list 
   for(int i=0;i<n;i++){
       int x;
       cin>>x;
       Node *newnode=new Node(x);
       newnode->next=NULL;
       if(head==NULL) {               
           head=newnode;  
           tail=newnode; 
       }
       else{
           tail->next=newnode;
           tail=newnode;
       }
   }
   // deleting the linked list
   delete_linked_list(&head);
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Complexities

Time complexity

O(n), where n is the number of elements in the linked list.

Reason: We’re traversing the linked list once to delete each element one by one. Thus, the time complexity is O(n).

Space complexity

O(1)

Reason: No extra space has been allocated here other than a few variables which take constant space only.

Also read - Merge sort in linked list

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.

  1. Find the previous node of the node to be deleted.
  2. Change the next pointer of the previous node.
  3. Free memory for the node to be deleted.

Conclusion

In this article, we learned about how to delete a linked list. You can observe that the time complexity to delete the whole linked list is O(n) which is quite efficient. If you don’t know how to delete a single node in a linked list, you can go on to read this article. Furthermore, there are many other operations that we can do on a linked list. You can read about them here.

Recommended Reading:

Problems on doubly 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 Coding Ninjas Studio.

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 Coding Ninjas Studio.

Happy Coding!

Live masterclass