Function to delete a Linked list

Last Updated on June 22, 2022 by Ria Pathak

Introduction

The linked list is one of the most important data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given a singly linked list. We have to write a function that takes the head of the list as a parameter and deletes the complete linked list.

Problem Statement Understanding

Suppose the linked list is 1 – > 2 – > 3 – > 4. Now, we have to delete this linked list.

• We have to delete the nodes one by one, so in the first step after deletion of 1, the linked list will be 2 – > 3 – > 4.
• In the second step after deletion of 2, the linked list will be 3 – > 4.
• In the third step after deletion of 3, the linked list will be 4.
• In the final step, 4 will also get deleted, and we will have an empty list.

Input:

Output: NULL (Empty List)

This question is not a very complex one. Firstly, do we have to do the linked list deletion in Java and Python? The answer is No. We have to solve it only for C++, as in Java and Python, an automatic garbage collection process happens, so the deletion of a linked list is easy. In Java and Python, we just have to change the head to NULL.

Let us have a glance at the approach.

Approach

The approach is going to be pretty simple. We are going to create two nodes, current and temp, current will point to the head and temp will be NULL. Now, we will traverse through the list until the current is not NULL. In every iteration, we will make temp point to the next of current. Then, we will free current and lastly, the temp will become the new current.

In the end, we will make the head of the list NULL.

Algorithm

• Create two nodes, current and temp, current will point to the head and temp will be NULL.
• Traverse through the list using current, and for every iteration, do the following.
  1) Store the next of current in temp.
  2) free(current)
  3) Make temp as the new current.
• In the end, make the head of the list NULL.

Dry Run

Code Implementation

#include
#include
#include
 
/* Link list node */
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;
    
    /* Use push() to construct below list
     1->12->1->4->1  */
    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");
}

#include 
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void deleteList(Node** head_ref)
{
 
 
    Node* current = *head_ref;
    Node* temp = NULL;
 
    while (current != NULL)
    {
        temp = current->next;
        free(current);
        current = temp;
    }

    *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, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
 
    cout << "Deleting the linked list";
    deleteList(&head);
 
    cout << "\nLinked list deleted";
}

class LinkedList
{
    Node head; 
    class Node
    {
        int data;
        Node next;
        Node(int d) { data = d; next = null; }
    }

    /* Function deletes the entire linked list */
    void deleteList()
    {
        head = null;
    }

    /* Inserts a new Node at front of the list. */
    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(9);
        llist.push(1);

        System.out.println("Deleting the list");
        llist.deleteList();

        System.out.println("Linked list deleted");
    }
}

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:
            prev = current.next
            del current.data
            current = prev

    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(4)
    llist.push(3)
    llist.push(2)
    llist.push(1)

    print("Deleting linked list")
    llist.deleteList()

    print("Linked list deleted")

Output
Deleting the linked list
Linked list deleted

[forminator_quiz id=”3813″]

Space Complexity: O(1), as only temporary variables are being created.

So, in this article, we have tried to explain the most efficient approach to delete a linked list. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.