Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

linked list
c++
head
node
data structures

How to delete the head node of a linked list in C++

Anusheh Zohair Mustafeez

In this shot, we will create a function to delete the head node of a singly linked list in C++.

svg viewer
Deleted the head node of a Linked List

Implementation

Below is the standard implementation of a singly linked list in C++. We will pass the object of the LinkedList class to our delete_head function, which will return a linked list with the original head node deleted.

#include <iostream>
using namespace std;

// Making a node struct containing a data int and a pointer
// to another node
struct Node { 
  int data; 
  Node *next; 
};

class LinkedList
{
  public:
    // Head pointer
    Node* head;

    // default constructor. Initializing head pointer
    LinkedList()
    {
      head = NULL;
    }

    // inserting elements (At start of the list)
    void insert(int val)
    {
      // make a new node
      Node* new_node = new Node;
      new_node->data = val;
      new_node->next = NULL;

      // If list is empty, make the new node, the head
      if (head == NULL)
        head = new_node;
      // else, make the new_node the head and its next, the previous
      // head
      else
      {
        new_node->next = head;
        head = new_node;
      }
    }

    // loop over the list. return true if element found
    bool search(int val)
    {
      Node* temp = head;
      while(temp != NULL)
      {
        if (temp->data == val)
          return true;
        temp = temp->next;
      }
      return false;
    }

    
    void remove(int val)
    {
      // If the value to be deleted is at head
      if (head->data == val)
      {
        delete head;
        head = head->next;
        return;
      }

      // If there is only one element in the list
      if (head->next == NULL)
      {
        // If the head is to be deleted. Assign null to the head
        if (head->data == val)
        {
          delete head;
          head = NULL;
          return;
        }
        // else print, value not found
        cout << "Value not found!" << endl;
        return;
      }

      // Else loop over the list and search for the node to delete
      Node* temp = head;
      while(temp->next!= NULL)
      {
        // When node is found, delete the node and modify the pointers
        if (temp->next->data == val)
        {
          Node* temp_ptr = temp->next->next;
          delete temp->next;
          temp->next = temp_ptr;
          return;
        }
        temp = temp->next;
      }

      // Else, the value was neve in the list
      cout << "Value not found" << endl;
    }

    void display()
    {
      Node* temp = head;
      while(temp != NULL)
      {
        cout << temp->data << " ";
        temp = temp->next;
      }
      cout << endl;
    }
};


// This is the function we are interested in. It takes in a LinkedList object and
// returns a Node pointer to the head of a linked list with the original head deleted
Node* delete_head(LinkedList lst)
{
  if (lst.head != NULL)
  {
    // Move the head pointer to the next node 
    Node* temp = lst.head;

    // Move head one node ahead
    lst.head = lst.head->next;

    // Delete previous head
    delete temp;

    // Return new head
    return lst.head;
  }
}

int main() {
  LinkedList l;
  // inserting elements into linked list l
  l.insert(6);
  l.insert(9);
  l.insert(1);
  l.insert(3);
  l.insert(7);

  // Displaying current linked list
  cout << "Current Linked List: "<<endl;
  l.display();

  // Deleting head of linked list
  l.head = delete_head(l);

  // Displaying linked list after deleting head node
  cout << "Linked list after deleting head node:"<<endl;
  l.display();
}

RELATED TAGS

linked list
c++
head
node
data structures

CONTRIBUTOR

Anusheh Zohair Mustafeez
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring