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.
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

Shreya Deep
0 upvote

## 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.

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

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
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
}
int main(){
int n; // Number of elements in the linked list
cin>>n;
Node *tail=NULL; // Tail of the linked list
for(int i=0;i<n;i++){
int x;
cin>>x;
Node *newnode=new Node(x);
newnode->next=NULL;
tail=newnode;
}
else{
tail->next=newnode;
tail=newnode;
}
}
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 take constant space only.

### 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.