# Delete a linked list using recursion

In this problem, we are tasked with deleting a linked list using recursion. A linked list is a data structure composed of nodes, where each node contains data and a reference to the next node. The goal is to deallocate memory occupied by each node while traversing the list recursively, ultimately leading to an empty list.

## Problem Statement

Given a singly linked list, our objective is to delete all its nodes using a recursive approach.

## Example Scenario

Consider a linked list: 1 → 2 → 3 → 4 → 5 → NULL. After applying the recursive deletion, the list becomes empty: Empty linked list.

## Idea to Solve the Problem

To delete a linked list using recursion, we can create a recursive function that deletes the current node and then makes a recursive call to delete the next node. This process continues until the end of the list is reached, at which point all nodes are deallocated and the linked list becomes empty.

## Pseudocode

``````struct LinkNode:
int data

struct SingleLL:

sll = allocate memory for SingleLL
sll.tail = NULL
return sll

void appendNode(sll, node):
else:
sll.tail.next = node
sll.tail = node

node = allocate memory for LinkNode
node.data = data
node.next = NULL
appendNode(sll, node)

void display(sll):
while temp is not NULL:
print temp.data
temp = temp.next

if node is not NULL:
temp = node.next
if temp is not NULL:
node.next = deleteElement(temp)
free memory for node
return NULL

void deleteList(sll):
sll.tail = NULL

main():
print "Before Delete:"
display(sll)
deleteList(sll)
print "After Delete:"
display(sll)``````

## Algorithm Explanation

1. Create a recursive function `deleteElement` that takes a pointer to a `LinkNode` as an argument.
2. Inside the function, if the given `node` is not NULL, get a reference to the next node using `node.next`.
3. Make a recursive call to `deleteElement` with the next node.
4. After the recursion unwinds, deallocate memory for the current node using the `free` function.
5. Set the next pointer of the previous node to NULL (this effectively removes the node from the list).
6. In the `deleteList` function, handle cases where the linked list is not empty.
7. Call the `deleteElement` function with the head of the linked list, and reset the head and tail pointers to NULL.

## Program Solution

``````// C program for
// Delete a linked list using recursion
#include <stdio.h>

#include <stdlib.h>

{
int data;
};
struct SingleLL
{
};
// Returns the new linked list
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *) malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
sll->tail = NULL;
}
return sll;
}
void appendNode(struct SingleLL *sll, struct LinkNode *node)
{
{
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
void addNode(struct SingleLL *sll, int data)
{
// Create dynamic node
if (node == NULL)
{
return;
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
appendNode(sll, node);
}
void display(struct SingleLL *sll)
{
{
return;
}
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Recursively, delete nodes in given linked list
{
if (node != NULL)
{
if (temp != NULL)
{
node->next = deleteElement(temp);
}
// Free node
free(node);
}
return NULL;
}
// This is handle the request of remove linked list elements
void deleteList(struct SingleLL *sll)
{
{
// new tail node is null
sll->tail = NULL;
}
}
int main(int argc, char const *argv[])
{
//  1 → 2 → 3 → 4 → 5 → NULL
printf(" Before Delete \n");
display(sll);
// Remove all nodes
deleteList(sll);
printf("\n After Delete ");
display(sll);
return 0;
}``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete
``````/*
Java Program for
Delete a linked list using recursion
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.println(" NULL");
}
// Recursively, delete nodes in given linked list
{
if (node != null)
{
if (temp != null)
{
node.next = deleteElement(temp);
}
}
return null;
}
// This is handle the request of remove linked list elements
public void deleteList()
{
{
// new tail node is null
this.tail = null;
}
}
public static void main(String[] args)
{
SingleLL sll = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → NULL
System.out.print(" Before Delete \n");
sll.display();
// Remove all nodes
sll.deleteList();
System.out.print("\n After Delete ");
sll.display();
}
}``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program for
Delete a linked list using recursion
*/
{
public: int data;
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
SingleLL()
{
this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
void display()
{
{
cout << "\n Empty linked list" << endl;
return;
}
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL" << endl;
}
// Recursively, delete nodes in given linked list
{
if (node != NULL)
{
if (temp != NULL)
{
node->next = this->deleteElement(temp);
}
// remove node
delete node;
}
return NULL;
}
// This is handle the request of remove linked list elements
void deleteList()
{
{
// new tail node is null
this->tail = NULL;
}
}
};
int main()
{
SingleLL *sll = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → NULL
cout << " Before Delete \n";
sll->display();
// Remove all nodes
sll->deleteList();
cout << "\n After Delete ";
sll->display();
return 0;
}``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete
``````// Include namespace system
using System;
/*
Csharp Program for
Delete a linked list using recursion
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.WriteLine(" NULL");
}
// Recursively, delete nodes in given linked list
{
if (node != null)
{
if (temp != null)
{
node.next = this.deleteElement(temp);
}
}
return null;
}
// This is handle the request of remove linked list elements
public void deleteList()
{
{
// new tail node is null
this.tail = null;
}
}
public static void Main(String[] args)
{
SingleLL sll = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → NULL
Console.Write(" Before Delete \n");
sll.display();
// Remove all nodes
sll.deleteList();
Console.Write("\n After Delete ");
sll.display();
}
}``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete
``````<?php
/*
Php Program for
Delete a linked list using recursion
*/
{
public \$data;
public \$next;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
class SingleLL
{
public \$tail;
public	function __construct()
{
\$this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
\$this->tail->next = \$node;
}
\$this->tail = \$node;
}
public	function display()
{
{
"\n";
return;
}
while (\$temp != NULL)
{
echo " ".\$temp->data." →";
// Visit to next node
\$temp = \$temp->next;
}
echo " NULL\n";
}
// Recursively, delete nodes in given linked list
public	function deleteElement(\$node)
{
if (\$node != NULL)
{
\$temp = \$node->next;
if (\$temp != NULL)
{
\$node->next = \$this->deleteElement(\$temp);
}
}
return NULL;
}
// This is handle the request of remove linked list elements
public	function deleteList()
{
{
// new tail node is null
\$this->tail = NULL;
}
}
}

function main()
{
\$sll = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → NULL
echo " Before Delete \n";
\$sll->display();
// Remove all nodes
\$sll->deleteList();
echo "\n After Delete ";
\$sll->display();
}
main();``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete
``````/*
Node JS Program for
Delete a linked list using recursion
*/
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
display()
{
{
return;
}
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
console.log(" NULL");
}
// Recursively, delete nodes in given linked list
deleteElement(node)
{
if (node != null)
{
var temp = node.next;
if (temp != null)
{
node.next = this.deleteElement(temp);
}
}
return null;
}
// This is handle the request of remove linked list elements
deleteList()
{
{
// new tail node is null
this.tail = null;
}
}
}

function main()
{
var sll = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → NULL
process.stdout.write(" Before Delete \n");
sll.display();
// Remove all nodes
sll.deleteList();
process.stdout.write("\n After Delete ");
sll.display();
}
main();``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete
``````#  Python 3 Program for
#  Delete a linked list using recursion

def __init__(self, data) :
self.data = data
self.next = None

class SingleLL :
def __init__(self) :
self.tail = None

else :
#  Append the node at last position
self.tail.next = node

self.tail = node

def display(self) :
return

while (temp != None) :
print("", temp.data ,"→", end = "")
#  Visit to next node
temp = temp.next

print(" NULL")

#  Recursively, delete nodes in given linked list
def deleteElement(self, node) :
if (node != None) :
temp = node.next
if (temp != None) :
node.next = self.deleteElement(temp)

return None

#  This is handle the request of remove linked list elements
def deleteList(self) :
#  new tail node is null
self.tail = None

def main() :
sll = SingleLL()
#   1 → 2 → 3 → 4 → 5 → NULL
print(" Before Delete ")
sll.display()
#  Remove all nodes
sll.deleteList()
print("\n After Delete ", end = "")
sll.display()

if __name__ == "__main__": main()``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete
``````#  Ruby Program for
#  Delete a linked list using recursion

attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end

class SingleLL
# Define the accessor and reader of class SingleLL
def initialize()
self.tail = nil
end

else
#  Append the node at last position
self.tail.next = node
end

self.tail = node
end

def display()
return
end

while (temp != nil)
print(" ", temp.data ," →")
#  Visit to next node
temp = temp.next
end

print(" NULL", "\n")
end

#  Recursively, delete nodes in given linked list
def deleteElement(node)
if (node != nil)
temp = node.next
if (temp != nil)
node.next = self.deleteElement(temp)
end

end

return nil
end

#  This is handle the request of remove linked list elements
def deleteList()
#  new tail node is null
self.tail = nil
end

end

end

def main()
sll = SingleLL.new()
#   1 → 2 → 3 → 4 → 5 → NULL
print(" Before Delete \n")
sll.display()
#  Remove all nodes
sll.deleteList()
print("\n After Delete ")
sll.display()
end

main()``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete
``````
``````/*
Scala Program for
Delete a linked list using recursion
*/
{
def this(data: Int)
{
this(data,null);
}
}
{
def this()
{
this(null,null);
}
def addNode(data: Int): Unit = {
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
def display(): Unit = {
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
println(" NULL");
}
// Recursively, delete nodes in given linked list
if (node != null)
{
if (temp != null)
{
node.next = deleteElement(temp);
}
}
return null;
}
// This is handle the request of remove linked list elements
def deleteList(): Unit = {
{
// new tail node is null
this.tail = null;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var sll: SingleLL = new SingleLL();
//  1 → 2 → 3 → 4 → 5 → NULL
print(" Before Delete \n");
sll.display();
// Remove all nodes
sll.deleteList();
print("\n After Delete ");
sll.display();
}
}``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete
``````/*
Swift 4 Program for
Delete a linked list using recursion
*/
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
init()
{
self.tail = nil;
}
{
{
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
func display()
{
{
return;
}
while (temp  != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Recursively, delete nodes in given linked list
{
if (node  != nil)
{
if (temp  != nil)
{
node!.next = self.deleteElement(temp);
}
}
return nil;
}
// This is handle the request of remove linked list elements
func deleteList()
{
{
// new tail node is null
self.tail = nil;
}
}
}
func main()
{
let sll: SingleLL = SingleLL();
//  1 → 2 → 3 → 4 → 5 → NULL
print(" Before Delete ");
sll.display();
// Remove all nodes
sll.deleteList();
print("\n After Delete ", terminator: "");
sll.display();
}
main();``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete
``````/*
Kotlin Program for
Delete a linked list using recursion
*/
{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
fun display(): Unit
{
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
println(" NULL");
}
// Recursively, delete nodes in given linked list
{
if (node != null)
{
if (temp != null)
{
node.next = this.deleteElement(temp);
}
}
return null;
}
// This is handle the request of remove linked list elements
fun deleteList(): Unit
{
{
// new tail node is null
this.tail = null;
}
}
}
fun main(args: Array < String > ): Unit
{
val sll: SingleLL = SingleLL();
//  1 → 2 → 3 → 4 → 5 → NULL
print(" Before Delete \n");
sll.display();
// Remove all nodes
sll.deleteList();
print("\n After Delete ");
sll.display();
}``````

#### input

`````` Before Delete
1 → 2 → 3 → 4 → 5 → NULL

After Delete

## Output Explanation

The code demonstrates the deletion of linked list nodes using recursion. Initially, the linked list contains elements 1 → 2 → 3 → 4 → 5 → NULL. After applying the recursive deletion, the list becomes an empty linked list.

## Time Complexity

The time complexity of deleting a linked list using recursion is O(n), where n is the number of nodes in the linked list. This is because each node is visited and freed once during the recursive deletion process.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.