Delete a Node at a Given Position in Singly Linked List

In the below article we are seeing how to delete a node before the specified position in the singly linked list. Given a singly linked list and a specified position, where we have to delete a node in that specified position.

Understanding how to delete a node from the linked list at a given position.

Let’s first understand the problem statement with the help of an example.

Suppose the linked list is 1 → 5 → 2 → 7 and the position given is 2. So, we have to delete the node present at the 2nd position.

Note : We are using 0 based indexing in this problem.

Here, in the given linked list, the node present at the 2nd position is 2. So, we have to delete 2 from the given list. The Final linked list after deleting 2 will be: 1 → 5 → 7

Input :

Output :

Explanation : The node at the 2nd position has been deleted.

How should we approach this problem? What is the first thing that comes to mind when we think about how to delete a node from the linked list at a given position? Try to reach the position, right?

Yes, But with a little change.

To delete a node, we should also have the pointer to its previous node. We can tackle this by traversing till the (position – 1)th node.

Let us have a glance at the approach.

Approach on how to delete a node from the linked list at a given position

First, let’s think in terms of how to delete a node from the linked list at a given position.

Let the linked list be:

1 → 5 → 2 → 7.

So, here, if we delete the node (2), we get :

1 → 5 → 7.

So, by deleting the node(2) we are making a connection between node(1) and node(5). That means the next of node(1) point to node(5).

Observation

  • If we take some more examples, we will notice that we need to access the previous and the next node of the node that we need to delete.

Say, if the node to be deleted is target, and its previous node is prev and its next node is next1. So, to do the deletion of target node from the linked list, we need to perform the following operations:

1) prev → next = next1.

2) And finally free the target node.

By doing this, we are removing the target node at the given position and changing the necessary links.

There are a few corner cases. Try to think them out by taking a few examples. Everything is discussed in detail in the algorithm section.

Algorithm for how to delete a node before specified position in singly linked list

  • If the head is NULL, return.
  • Create a node temp and make it point to the head.
  • If the position is 0, it means that we have to delete the head of the list. We can easily do that by head = temp → next and free(temp). As temp was pointing to the head, we have incremented the head and freed temp.
  • If the position is not 0, we will proceed. Now, we will write a loop with i = 0 to i < (position -1). As we have discussed, to delete a node, we need a pointer to its previous node. So while traversing the loop, we will increment temp.
  • Now, after the loop ends, if the temp is NULL or temp → next is NULL, we will simply return as the position is more than the number of nodes in the linked list.
  • If the above condition fails, we will have temp pointing to the (position – 1)th node. Now, we simply have to change the required pointers.
  • We will save the temp → next → next in a new node next1. Now, we will free temp → next, as it is the node at the given position. In the end, temp → next = next1. – In this way, there is no unnecessary memory leak and the node at the given position is getting deleted successfully.

Dry Run on how to delete a node before specified position in singly linked list

Code Implementation on how to delete a node from linked list at a given position.

#include<stdio.h>
#include<stdlib.h>
 
void insert(int );
void display_List();
void delete(int );
 
struct node             // Structure declaration
{
    int data;
    struct node *next;  // Self referral pointer
}*head=NULL,*tail=NULL; // Initial value of Head and Tail pointer is NULL
 
 
void delete(int pos)
{
    struct node *temp = head;       // Creating a temporary variable pointing to head
    int i;                    
    if(pos==0)
    {
        printf("\nElement deleted is : %d\n",temp->data);
        head=head->next;        // Advancing the head pointer
        temp->next=NULL;
        free(temp);             // Node is deleted
    }
    else
    {
        for(i=0;i<pos-1;i++) {="" temp="temp-">next;
        }
        // Now temp pointer points to the previous node of the node to be deleted
        struct node *del =temp->next;       // del pointer points to the node to be deleted
        temp->next=temp->next->next;
        printf("\nElement deleted is : %d\n",del->data);      
        del->next=NULL;
        free(del);                          // Node is deleted
    }
    printf("\nUpdated Linked List is : \n");
    display_List();
    return ;
}
 
 
 
void insert(int value)
{
    struct node *newnode;  // Creating a new node
    newnode = (struct node *)malloc(sizeof(struct node)); // Allocating dynamic memory
 
    newnode->data = value;      // Assigning value to newnode
    newnode->next = NULL;    
 
    if(head==NULL)      // Checking if List is empty
    {
        head = newnode;
        tail = newnode;
    }
    else                // If not empty then...
    {
        tail->next=newnode;    
        tail=newnode;       // Updating the tail node with each insertion
    }
    return ;
}
 
void display_List()
{
    struct node *temp;    // Creating a temporary pointer to the structure
    temp=head;          // temp points to head;
    while(temp!=NULL)
    {
        if(temp->next==NULL)
        {
            printf(" %d->NULL",temp->data);
        }
        else
        {
            printf(" %d->",temp->data);
        }
        temp=temp->next;            // Traversing the List till end
    }
    printf("\n");
    return ;
}
// --Driver Code--
int main()
{
    insert(1);
    insert(2);
    insert(3);
    insert(4);
    insert(5);
    insert(6);
    printf("\n--Created Linked List--\n");
    display_List();
    printf("\nLinked List after deletion");
    delete(2);                                   // List indexing starts from 0
    return 0;
}

#include <iostream>
using namespace std;

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

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

void deleteNode(Node **head_ref, int position)
{

    if (*head_ref == NULL)
        return;

    Node* temp = *head_ref;

    if (position == 0)
    {

        *head_ref = temp->next;

        free(temp);            
        return;
    }
 
    for(int i = 0; temp != NULL && i < position - 1; i++)
        temp = temp->next;

    if (temp == NULL || temp->next == NULL)
        return;

     Node *next1 = temp->next->next;
 
    
    free(temp->next); 

    temp->next = next1;
}

void printList( Node *node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}
int main()
{

    Node* head = NULL;
 
    push(&head, 7);
    push(&head, 2);
    push(&head, 5);
    push(&head, 1);
 
    cout << "Created Linked List: ";
    printList(head);
    deleteNode(&head, 2);
    cout << "\nLinked List after Deletion at position 2: ";
    printList(head);
    return 0;
}
public class LinkedList
{
    Node head; 
    class Node
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    public void push(int new_data)
    {

        Node new_node = new Node(new_data);

        new_node.next = head;

        head = new_node;
    }

    void deleteNode(int position)
    {

        if (head == null)
            return;

        Node temp = head;

        if (position == 0)
        {
            head = temp.next;  
            return;
        }

        for (int i=0; temp!=null && i<position-1; i++)
            temp = temp.next;

        if (temp == null || temp.next == null)
            return;

        Node next1 = temp.next.next;
 
        temp.next = next1;  
    }

    public void printList()
    {
        Node tnode = head;
        while (tnode != null)
        {
            System.out.print(tnode.data+" ");
            tnode = tnode.next;
        }
    }

    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
 
        llist.push(7);
        llist.push(2);
        llist.push(5);
        llist.push(1);
 
        System.out.println("\nCreated Linked list is: ");
        llist.printList();
 
        llist.deleteNode(2);  
 
        System.out.println("\nLinked List after Deletion at position 2: ");
        llist.printList();
    }
}


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


class LinkedList:

    def __init__(self):
        self.head = None

    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    def deleteNode(self, position):
        if self.head is None:
            return
        if position == 0:
            self.head = self.head.next
            return self.head
        index = 0
        current = self.head
        prev = self.head
        temp = self.head
        while current is not None:
            if index == position:
                temp = current.next
                break
            prev = current
            current = current.next
            index += 1
        prev.next = temp
        return prev

    def printList(self):
        temp = self.head
        while(temp):
            print (" %d " % (temp.data),end=" ")
            temp = temp.next

llist = LinkedList()
llist.push(7)
llist.push(2)
llist.push(5)
llist.push(1)

print ("Created Linked List: ")
llist.printList()
llist.deleteNode(2)
print ("\nLinked List after Deletion at position 4: ")
llist.printList()

Output on how to delete a node before specified position in singly linked list

Created Linked List: 1 5 2 7

Linked List after Deletion at position 2: 1 5 7

Time Complexity: O(n), as list traversal is needed.

Conclusion

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

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Student management system using linked list
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. What is a Pointer?
    A pointer is a variable which stores the memory address of another variable.

  2. What happens with memory allocated when some node is deleted?
    When you delete an object in the heap, the memory is not cleaned up actually. A call to new or malloc can overwrite the memory as it marks the memory as free.

  3. What is the time complexity for running the program to delete a node from the linked list at a given position?
    The time complexity for the program on how to delete a node from the linked list at a given position will be O(1) if we know the Position reference to that node.

  4. What is underflow in linked list?
    When we try to delete a node from a linked list which is empty then it is called underflow as START == NULL.

Leave a Reply

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