Deletion of a linked list

Shreya Deep
Last Updated: May 13, 2022

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.

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;
}

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;
}

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 takes constant space only.

Frequently asked questions

  1. What is a linked list in C++?
    A linked list is a linear data structure which 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.
     
  2. 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)
     
  3. 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 of the previous node.
    3. Free memory for the node to be deleted.

Key Takeaways

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.

To practice more such problems, Codestudio is a one-stop destination. You can also Attempt our Online Mock Test Series. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think