Function to delete a Linked list

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

Function to delete a Linked list


#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";
}

Output
Deleting the linked list
Linked list deleted

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.

Previous post Check whether the length of given linked list is Even or Odd
Next post Union and Intersection of two Linked Lists

Leave a Reply

Your email address will not be published. Required fields are marked *