.png)
Delete Entire Linked List in Data Structures
Problem Statement
Given the head pointer of a singly linked list, delete the entire linked list and free all allocated memory.
After deletion, the head pointer should become NULL.
You must ensure that:
- Every node is properly deallocated.
- No memory leak occurs.
- The list becomes completely empty.
What Does “Delete Entire Linked List” Actually Mean?
Deleting a linked list does not mean:
- Just setting head = NULL
- Or ignoring the list
If we only set head to NULL without freeing nodes, memory remains allocated. This causes memory leaks in languages like C and C++.
Deleting a linked list means:
- Visiting every node
- Freeing or deleting that node
- Finally setting head to NULL
In garbage-collected languages like Java and Python:
- The garbage collector reclaims memory automatically.
- But we must remove references properly.
Observational Thinking Before Implementation
To delete the entire list:
- We must traverse from head to NULL.
- Store next node before deleting current node.
- Delete current node.
- Move forward.
- Repeat until list ends.
Important Concept:
Once a node is deleted, its memory cannot be accessed.
So we must store the next pointer before deletion.
Edge Cases to Handle
- If head is already NULL → nothing to delete.
- Single node list.
- Large list.
- Preventing dangling pointers.
Approach: Iterative Deletion
This is the most practical and recommended method.
Algorithm
If head is NULL → return NULL.
Initialize current = head.
While current is not NULL:
- Store nextNode = current->next
- Free/Delete current
- Move current = nextNode
Finally set head = NULL.
Return head.
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1)
C Implementation – Delete Entire Linked List
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
struct Node* deleteEntireList(struct Node* head) {
struct Node* current = head;
struct Node* nextNode;
while (current != NULL) {
nextNode = current->next;
free(current);
current = nextNode;
}
return NULL;
}
void printList(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return;
}
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
printf("Before deletion: ");
printList(head);
head = deleteEntireList(head);
printf("After deletion: ");
printList(head);
return 0;
}Output:
Before deletion: 10 20 30
After deletion: List is empty
C++ Implementation – Delete Entire Linked List
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
Node* deleteEntireList(Node* head) {
Node* current = head;
Node* nextNode;
while (current != NULL) {
nextNode = current->next;
delete current;
current = nextNode;
}
return NULL;
}
void printList(Node* head) {
if (head == NULL) {
cout << "List is empty" << endl;
return;
}
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
cout << "Before deletion: ";
printList(head);
head = deleteEntireList(head);
cout << "After deletion: ";
printList(head);
return 0;
}
Output:
Before deletion: 10 20 30
After deletion: List is empty
Java Implementation – Delete Entire Linked List
In Java, explicit memory deallocation is not required. The garbage collector reclaims memory automatically.
However, to logically delete the list:
- Break references.
- Set head to null.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static Node deleteEntireList(Node head) {
head = null;
return head;
}
public static void printList(Node head) {
if (head == null) {
System.out.println("List is empty");
return;
}
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
System.out.print("Before deletion: ");
printList(head);
head = deleteEntireList(head);
System.out.print("After deletion: ");
printList(head);
}
}
Output:
Before deletion: 10 20 30
After deletion: List is empty
Python Implementation – Delete Entire Linked List
Python uses automatic garbage collection.
To delete the entire list:
- Remove references.
- Set head = None.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def delete_entire_list(head):
head = None
return head
def print_list(head):
if head is None:
print("List is empty")
return
while head:
print(head.data, end=" ")
head = head.next
print()
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
print("Before deletion:", end=" ")
print_list(head)
head = delete_entire_list(head)
print("After deletion:", end=" ")
print_list(head)
Output:
Before deletion: 10 20 30
After deletion: List is empty
Important Memory Management Insight
In C and C++:
If you only set head = NULL without deleting nodes, memory remains allocated.
In Java and Python:
Memory is managed automatically, but references must be removed.
This difference is extremely important in interviews and system-level programming.
Next problem in the series:
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
