Algorithm For C/C++: Iterate through the linked list and delete all the nodes one by one. The main point here is not to access the next of the current pointer if the current pointer is deleted.
In Java, Python, and JavaScript automatic garbage collection happens, so deleting a linked list is easy. Just need to change head to null.
You can delete the link list by following 3 methods:
- Delete from beginning
- Delete from the end
- Delete from middle
Delete from the beginning :
ALGORITHM:
- Store the address of the first node in a pointer.
- move the head node to the next node
- dispose or free memory of the pointer node
C
X=head;
head= head->next;
free(x);
|
C++
ListNode* X = head;
head = head->next;
delete X;
|
Java
ListNode X = head;
head = head.next;
X = null;
|
Python3
X = head
head = head.next
X = None
|
Javascript
<script>
ListNode X = head;
head = head.next;
X = null;
</script>
|
C#
ListNode X = head;
head = head.next;
X = null;
|
Delete the last node:
ALGORITHM:
- Traverse link list to second last element
- Change its next pointer to null
- Free the memory of the last node.
C
Struct node* temp=head ;
While(temp->next->next!=NULL)
{
Temp= temp->next ;
}
Temp->next= NULL;
|
C++
node* temp = head;
while (temp->next->next != NULL) {
temp = temp->next;
}
temp->next = nullptr;
|
Python3
temp = head
while (temp.next and temp.next.next != None):
temp = temp.next
temp.next = None
|
Java
ListNode temp = head;
while (temp.next.next != null) {
temp = temp.next;
}
temp.next = null;
|
C#
ListNode temp = head;
while (temp.next.next != null) {
temp = temp.next;
}
temp.next = null;
|
Javascript
<script>
node temp = head;
while (temp.next.next != null) {
temp = temp->next;
}
temp.next = nullptr;
</script>
|
Delete from the middle:
ALGORITHM:
- Store the address of the deleted node as a key node.
- Store the address of the preceding node in a pointer. Eg . P
- Store the address of a key node in the pointer variable . eg . X
- Make the successor of the key node as the successor of the node pointed by p.
- Free node X.
C
for (int i = 2; i < position; i++) {
If(temp->next != NULL) { Temp = temp->next; }
}
Temp->next = temp->next->next;
|
C++
for (int i = 2; i < position; i++) {
if(temp->next != NULL) { temp = temp->next; }
}
temp->next = temp->next->next;
|
Java
for (int i = 2; i < position; i++) {
if (temp.next != null) {
temp = temp.next;
}
}
temp.next = temp.next.next;
|
Python3
for i in range(2,position):
if temp.next != None:
temp = temp.next;
temp.next = temp.next.next;
|
C#
int i = 2;
while (i < position) {
if (temp.Next != null) {
temp = temp.Next;
}
i++;
}
temp.Next = temp.Next.Next;
|
Javascript
for(let i = 2; i<position; i++){
if(temp.next != null)
temp = temp.next;
}
temp.next = temp.next.next;
|
Implementation:
C
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
struct Node
{
int data;
struct Node* next;
};
void deleteList(struct Node** head_ref)
{
struct Node* current = *head_ref;
struct Node* next;
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
*head_ref = NULL;
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main()
{
struct Node* head = NULL;
push(&head, 1);
push(&head, 4);
push(&head, 1);
push(&head, 12);
push(&head, 1);
printf("\n Deleting linked list");
deleteList(&head);
printf("\n Linked list deleted");
}
|
C++
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
};
void deleteList(Node** head_ref)
{
Node* current = *head_ref;
Node* next = NULL;
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
*head_ref = NULL;
}
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main()
{
Node* head = NULL;
push(&head, 1);
push(&head, 4);
push(&head, 1);
push(&head, 12);
push(&head, 1);
cout << "Deleting linked list";
deleteList(&head);
cout << "\nLinked list deleted";
}
|
Java
import java.io.*;
class LinkedList {
Node head;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void deleteList() { head = null; }
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(1);
llist.push(4);
llist.push(1);
llist.push(12);
llist.push(1);
System.out.println("Deleting the list");
llist.deleteList();
System.out.println("Linked list deleted");
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def deleteList(self):
current = self.head
while current:
next_to_current = current.next
del current.data
current = next_to_current
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
if __name__ == '__main__':
llist = LinkedList()
llist.push(1)
llist.push(4)
llist.push(1)
llist.push(12)
llist.push(1)
print("Deleting linked list")
llist.deleteList()
print("Linked list deleted")
|
C#
using System;
public class LinkedList
{
Node head;
class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d; next = null;
}
}
void deleteList()
{
head = null;
}
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
public static void Main(String [] args)
{
LinkedList llist = new LinkedList();
llist.push(1);
llist.push(4);
llist.push(1);
llist.push(12);
llist.push(1);
Console.WriteLine("Deleting the list");
llist.deleteList();
Console.WriteLine("Linked list deleted");
}
}
|
Javascript
<script>
var head;
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
function deleteList() {
head = null;
}
function push(new_data) {
var new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
push(1);
push(4);
push(1);
push(12);
push(1);
document.write("Deleting the list<br/>");
deleteList();
document.write("Linked list deleted");
</script>
|
Output
Deleting linked list
Linked list deleted
Time Complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
