Skip to main content

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
    LinkNode next

struct SingleLL:
    LinkNode head
    LinkNode tail

SingleLL newLinkedList():
    sll = allocate memory for SingleLL
    sll.head = NULL
    sll.tail = NULL
    return sll

void appendNode(sll, node):
    if sll.head is NULL:
        sll.head = node
    else:
        sll.tail.next = node
    sll.tail = node

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

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

LinkNode deleteElement(node):
    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):
    if sll.head is not NULL:
        sll.tail = NULL
        sll.head = deleteElement(sll.head)

main():
    sll = newLinkedList()
    addNode(sll, 1)
    // Add other nodes...
    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>

// Linked List LinkNode
struct LinkNode
{
	int data;
	struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
	struct LinkNode *head;
	struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
	// 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->head = NULL;
		sll->tail = NULL;
	}
	return sll;
}
// Add new Node at end of linked list 
void appendNode(struct SingleLL *sll, struct LinkNode *node)
{
	if (sll->head == NULL)
	{
		sll->head = node;
	}
	else
	{
		// Append the node at last position
		sll->tail->next = node;
	}
	sll->tail = node;
}
// Handles the request of adding new node in linked list
void addNode(struct SingleLL *sll, int data)
{
	// Create dynamic node
	struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
	if (node == NULL)
	{
		printf("Memory overflow to Create LinkNode\n");
		return;
	}
	else
	{
		// Set initial node value
		node->data = data;
		node->next = NULL;
	}
	appendNode(sll, node);
}
// Display linked list element
void display(struct SingleLL *sll)
{
	if (sll->head == NULL)
	{
		printf("\n Empty linked list\n");
		return;
	}
	struct LinkNode *temp = sll->head;
	// iterating linked list elements
	while (temp != NULL)
	{
		printf(" %d →", temp->data);
		// Visit to next node
		temp = temp->next;
	}
	printf(" NULL\n");
}
// Recursively, delete nodes in given linked list 
struct LinkNode *deleteElement(struct LinkNode *node)
{
	if (node != NULL)
	{
		struct LinkNode *temp = node->next;
		if (temp != NULL)
		{
			// Unlink next node
			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)
{
	if (sll->head != NULL)
	{
		// new tail node is null
		sll->tail = NULL;
		// new head is null
		sll->head = deleteElement(sll->head);
	}
}
int main(int argc, char const *argv[])
{
	struct SingleLL *sll = newLinkedList();
	// Linked list
	//  1 → 2 → 3 → 4 → 5 → NULL
	addNode(sll, 1);
	addNode(sll, 2);
	addNode(sll, 3);
	addNode(sll, 4);
	addNode(sll, 5);
	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
 Empty linked list
/*
  Java Program for
  Delete a linked list using recursion
*/
// Linked list node
class LinkNode
{
	public int data;
	public LinkNode next;
	public LinkNode(int data)
	{
		this.data = data;
		this.next = null;
	}
}
public class SingleLL
{
	public LinkNode head;
	public LinkNode tail;
	public SingleLL()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	public void addNode(int data)
	{
		LinkNode node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	public void display()
	{
		if (this.head == null)
		{
			System.out.println("\n Empty linked list");
			return;
		}
		LinkNode temp = this.head;
		//iterating linked list elements
		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 
	public LinkNode deleteElement(LinkNode node)
	{
		if (node != null)
		{
			LinkNode temp = node.next;
			if (temp != null)
			{
				// Unlink next node
				node.next = deleteElement(temp);
			}
		}
		return null;
	}
	// This is handle the request of remove linked list elements
	public void deleteList()
	{
		if (this.head != null)
		{
			// new tail node is null
			this.tail = null;
			// new head is null
			this.head = deleteElement(this.head);
		}
	}
	public static void main(String[] args)
	{
		SingleLL sll = new SingleLL();
		// Linked list
		//  1 → 2 → 3 → 4 → 5 → NULL
		sll.addNode(1);
		sll.addNode(2);
		sll.addNode(3);
		sll.addNode(4);
		sll.addNode(5);
		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
 Empty linked list
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program for
  Delete a linked list using recursion
*/
// Linked list node
class LinkNode
{
	public: int data;
	LinkNode *next;
	LinkNode(int data)
	{
		this->data = data;
		this->next = NULL;
	}
};
class SingleLL
{
	public: LinkNode *head;
	LinkNode *tail;
	SingleLL()
	{
		this->head = NULL;
		this->tail = NULL;
	}
	// Add new Node at end of linked list 
	void addNode(int data)
	{
		LinkNode *node = new LinkNode(data);
		if (this->head == NULL)
		{
			this->head = node;
		}
		else
		{
			// Append the node at last position
			this->tail->next = node;
		}
		this->tail = node;
	}
	// Display linked list element
	void display()
	{
		if (this->head == NULL)
		{
			cout << "\n Empty linked list" << endl;
			return;
		}
		LinkNode *temp = this->head;
		//iterating linked list elements
		while (temp != NULL)
		{
			cout << " " << temp->data << " →";
			// Visit to next node
			temp = temp->next;
		}
		cout << " NULL" << endl;
	}
	// Recursively, delete nodes in given linked list 
	LinkNode *deleteElement(LinkNode *node)
	{
		if (node != NULL)
		{
			LinkNode *temp = node->next;
			if (temp != NULL)
			{
				// Unlink next node
				node->next = this->deleteElement(temp);
			}
          	// remove node
          	delete node;
		}
		return NULL;
	}
	// This is handle the request of remove linked list elements
	void deleteList()
	{
		if (this->head != NULL)
		{
			// new tail node is null
			this->tail = NULL;
			// new head is null
			this->head = this->deleteElement(this->head);
		}
	}
};
int main()
{
	SingleLL *sll = new SingleLL();
	// Linked list
	//  1 → 2 → 3 → 4 → 5 → NULL
	sll->addNode(1);
	sll->addNode(2);
	sll->addNode(3);
	sll->addNode(4);
	sll->addNode(5);
	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
 Empty linked list
// Include namespace system
using System;
/*
  Csharp Program for
  Delete a linked list using recursion
*/
// Linked list node
public class LinkNode
{
	public int data;
	public LinkNode next;
	public LinkNode(int data)
	{
		this.data = data;
		this.next = null;
	}
}
public class SingleLL
{
	public LinkNode head;
	public LinkNode tail;
	public SingleLL()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	public void addNode(int data)
	{
		LinkNode node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	public void display()
	{
		if (this.head == null)
		{
			Console.WriteLine("\n Empty linked list");
			return;
		}
		LinkNode temp = this.head;
		//iterating linked list elements
		while (temp != null)
		{
			Console.Write(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		Console.WriteLine(" NULL");
	}
	// Recursively, delete nodes in given linked list 
	public LinkNode deleteElement(LinkNode node)
	{
		if (node != null)
		{
			LinkNode temp = node.next;
			if (temp != null)
			{
				// Unlink next node
				node.next = this.deleteElement(temp);
			}
		}
		return null;
	}
	// This is handle the request of remove linked list elements
	public void deleteList()
	{
		if (this.head != null)
		{
			// new tail node is null
			this.tail = null;
			// new head is null
			this.head = this.deleteElement(this.head);
		}
	}
	public static void Main(String[] args)
	{
		SingleLL sll = new SingleLL();
		// Linked list
		//  1 → 2 → 3 → 4 → 5 → NULL
		sll.addNode(1);
		sll.addNode(2);
		sll.addNode(3);
		sll.addNode(4);
		sll.addNode(5);
		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
 Empty linked list
<?php
/*
  Php Program for
  Delete a linked list using recursion
*/
// Linked list node
class LinkNode
{
	public $data;
	public $next;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->next = NULL;
	}
}
class SingleLL
{
	public $head;
	public $tail;
	public	function __construct()
	{
		$this->head = NULL;
		$this->tail = NULL;
	}
	// Add new Node at end of linked list 
	public	function addNode($data)
	{
		$node = new LinkNode($data);
		if ($this->head == NULL)
		{
			$this->head = $node;
		}
		else
		{
			// Append the node at last position
			$this->tail->next = $node;
		}
		$this->tail = $node;
	}
	// Display linked list element
	public	function display()
	{
		if ($this->head == NULL)
		{
			echo "\n Empty linked list".
			"\n";
			return;
		}
		$temp = $this->head;
		//iterating linked list elements
		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)
			{
				// Unlink next node
				$node->next = $this->deleteElement($temp);
			}
		}
		return NULL;
	}
	// This is handle the request of remove linked list elements
	public	function deleteList()
	{
		if ($this->head != NULL)
		{
			// new tail node is null
			$this->tail = NULL;
			// new head is null
			$this->head = $this->deleteElement($this->head);
		}
	}
}

function main()
{
	$sll = new SingleLL();
	// Linked list
	//  1 → 2 → 3 → 4 → 5 → NULL
	$sll->addNode(1);
	$sll->addNode(2);
	$sll->addNode(3);
	$sll->addNode(4);
	$sll->addNode(5);
	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
 Empty linked list
/*
  Node JS Program for
  Delete a linked list using recursion
*/
// Linked list node
class LinkNode
{
	constructor(data)
	{
		this.data = data;
		this.next = null;
	}
}
class SingleLL
{
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	addNode(data)
	{
		var node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	display()
	{
		if (this.head == null)
		{
			console.log("\n Empty linked list");
			return;
		}
		var temp = this.head;
		//iterating linked list elements
		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)
			{
				// Unlink next node
				node.next = this.deleteElement(temp);
			}
		}
		return null;
	}
	// This is handle the request of remove linked list elements
	deleteList()
	{
		if (this.head != null)
		{
			// new tail node is null
			this.tail = null;
			// new head is null
			this.head = this.deleteElement(this.head);
		}
	}
}

function main()
{
	var sll = new SingleLL();
	// Linked list
	//  1 → 2 → 3 → 4 → 5 → NULL
	sll.addNode(1);
	sll.addNode(2);
	sll.addNode(3);
	sll.addNode(4);
	sll.addNode(5);
	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
 Empty linked list
#  Python 3 Program for
#  Delete a linked list using recursion

#  Linked list node
class LinkNode :
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class SingleLL :
	def __init__(self) :
		self.head = None
		self.tail = None
	
	#  Add new Node at end of linked list 
	def addNode(self, data) :
		node = LinkNode(data)
		if (self.head == None) :
			self.head = node
		else :
			#  Append the node at last position
			self.tail.next = node
		
		self.tail = node
	
	#  Display linked list element
	def display(self) :
		if (self.head == None) :
			print("\n Empty linked list")
			return
		
		temp = self.head
		# iterating linked list elements
		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) :
				#  Unlink next node
				node.next = self.deleteElement(temp)
			
		
		return None
	
	#  This is handle the request of remove linked list elements
	def deleteList(self) :
		if (self.head != None) :
			#  new tail node is null
			self.tail = None
			#  new head is null
			self.head = self.deleteElement(self.head)
		
	

def main() :
	sll = SingleLL()
	#  Linked list
	#   1 → 2 → 3 → 4 → 5 → NULL
	sll.addNode(1)
	sll.addNode(2)
	sll.addNode(3)
	sll.addNode(4)
	sll.addNode(5)
	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
 Empty linked list
#  Ruby Program for
#  Delete a linked list using recursion

#  Linked list node
class LinkNode 
	# Define the accessor and reader of class LinkNode
	attr_reader :data, :next
	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
	attr_reader :head, :tail
	attr_accessor :head, :tail
	def initialize() 
		self.head = nil
		self.tail = nil
	end

	#  Add new Node at end of linked list 
	def addNode(data) 
		node = LinkNode.new(data)
		if (self.head == nil) 
			self.head = node
		else 
			#  Append the node at last position
			self.tail.next = node
		end

		self.tail = node
	end

	#  Display linked list element
	def display() 
		if (self.head == nil) 
			print("\n Empty linked list", "\n")
			return
		end

		temp = self.head
		# iterating linked list elements
		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) 
				#  Unlink next node
				node.next = self.deleteElement(temp)
			end

		end

		return nil
	end

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

	end

end

def main() 
	sll = SingleLL.new()
	#  Linked list
	#   1 → 2 → 3 → 4 → 5 → NULL
	sll.addNode(1)
	sll.addNode(2)
	sll.addNode(3)
	sll.addNode(4)
	sll.addNode(5)
	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 
 Empty linked list

/*
  Scala Program for
  Delete a linked list using recursion
*/
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
	def this(data: Int)
	{
		this(data,null);
	}
}
class SingleLL(var head: LinkNode , var tail: LinkNode)
{
	def this()
	{
		this(null,null);
	}
	// Add new Node at end of linked list 
	def addNode(data: Int): Unit = {
		var node: LinkNode = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	def display(): Unit = {
		if (this.head == null)
		{
			println("\n Empty linked list");
			return;
		}
		var temp: LinkNode = this.head;
		//iterating linked list elements
		while (temp != null)
		{
			print(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		println(" NULL");
	}
	// Recursively, delete nodes in given linked list 
	def deleteElement(node: LinkNode): LinkNode = {
		if (node != null)
		{
			var temp: LinkNode = node.next;
			if (temp != null)
			{
				// Unlink next node
				node.next = deleteElement(temp);
			}
		}
		return null;
	}
	// This is handle the request of remove linked list elements
	def deleteList(): Unit = {
		if (this.head != null)
		{
			// new tail node is null
			this.tail = null;
			// new head is null
			this.head = deleteElement(this.head);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var sll: SingleLL = new SingleLL();
		// Linked list
		//  1 → 2 → 3 → 4 → 5 → NULL
		sll.addNode(1);
		sll.addNode(2);
		sll.addNode(3);
		sll.addNode(4);
		sll.addNode(5);
		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
 Empty linked list
/*
  Swift 4 Program for
  Delete a linked list using recursion
*/
// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.next = nil;
	}
}
class SingleLL
{
	var head: LinkNode? ;
	var tail: LinkNode? ;
	init()
	{
		self.head = nil;
		self.tail = nil;
	}
	// Add new Node at end of linked list 
	func addNode(_ data: Int)
	{
		let node: LinkNode = LinkNode(data);
		if (self.head == nil)
		{
			self.head = node;
		}
		else
		{
			// Append the node at last position
			self.tail!.next = node;
		}
		self.tail = node;
	}
	// Display linked list element
	func display()
	{
		if (self.head == nil)
		{
			print("\n Empty linked list");
			return;
		}
		var temp: LinkNode? = self.head;
		//iterating linked list elements
		while (temp  != nil)
		{
			print("", temp!.data ,"→", terminator: "");
			// Visit to next node
			temp = temp!.next;
		}
		print(" NULL");
	}
	// Recursively, delete nodes in given linked list 
	func deleteElement(_ node: LinkNode? )->LinkNode?
	{
		if (node  != nil)
		{
			let temp: LinkNode? = node!.next;
			if (temp  != nil)
			{
				// Unlink next node
				node!.next = self.deleteElement(temp);
			}
		}
		return nil;
	}
	// This is handle the request of remove linked list elements
	func deleteList()
	{
		if (self.head  != nil)
		{
			// new tail node is null
			self.tail = nil;
			// new head is null
			self.head = self.deleteElement(self.head);
		}
	}
}
func main()
{
	let sll: SingleLL = SingleLL();
	// Linked list
	//  1 → 2 → 3 → 4 → 5 → NULL
	sll.addNode(1);
	sll.addNode(2);
	sll.addNode(3);
	sll.addNode(4);
	sll.addNode(5);
	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
 Empty linked list
/*
  Kotlin Program for
  Delete a linked list using recursion
*/
// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.next = null;
	}
}
class SingleLL
{
	var head: LinkNode ? ;
	var tail: LinkNode ? ;
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	fun addNode(data: Int): Unit
	{
		val node: LinkNode = LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail?.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	fun display(): Unit
	{
		if (this.head == null)
		{
			println("\n Empty linked list");
			return;
		}
		var temp: LinkNode ? = this.head;
		while (temp != null)
		{
			print(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		println(" NULL");
	}
	// Recursively, delete nodes in given linked list 
	fun deleteElement(node: LinkNode ? ): LinkNode ?
	{
		if (node != null)
		{
			val temp: LinkNode? = node.next;
			if (temp != null)
			{
				// Unlink next node
				node.next = this.deleteElement(temp);
			}
		}
		return null;
	}
	// This is handle the request of remove linked list elements
	fun deleteList(): Unit
	{
		if (this.head != null)
		{
			// new tail node is null
			this.tail = null;
			// new head is null
			this.head = this.deleteElement(this.head);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val sll: SingleLL = SingleLL();
	// Linked list
	//  1 → 2 → 3 → 4 → 5 → NULL
	sll.addNode(1);
	sll.addNode(2);
	sll.addNode(3);
	sll.addNode(4);
	sll.addNode(5);
	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
 Empty linked list

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.

Last updated on by Kalkicode




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.

New Comment