Last Updated on July 27, 2023 by Mayank Dham
In this blog we will see how to delete a node from the singly linked list before the specified position. Given a singly linked list and a specific position, we must delete a node in that position in a singly linked list. Linked lists are fundamental data structures used in computer science to store and manage collections of elements efficiently. They offer dynamic memory allocation and provide flexible means of adding, removing, and traversing elements. Two common variations of linked lists are singly linked lists and doubly linked lists, each with its unique features and use cases.
How to Delete a Node at a Given Position in a Singly Linked List
Let’s start with an example to better understand the problem statement.
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 second position.
Note: We are using 0 based indexing in this problem.
The node in the second position of the given linked list is 2. As a result, we must remove two items 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.
What approach should we take to this problem? What comes to mind first when we consider how to delete a node from a linked list at a given position? Attempt to obtain the position, correct?
Yes, but with a slight modification.
To delete a node, we must also have a pointer to its predecessor. This can be solved by traversing until the (position – 1)th node.
Let’s take a look at the approach.
Approach on How to Delete a Node Before a Given Position in a Singly Linked List
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 next node of the node that we need to delete.
- Say if the node to be deleted is target, its previous node is prev, and its next node is next1. So, to delete the 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 delete a node from linked list at a given position.
Algorithm for How to Delete a Node Before a Given Position in a 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.
Now, as are having the idea for the algorithm to delete a node before specified position in singly linked list in C. Let’s see the dry to understand more in depth to delete a node from linked list at a given position.
Dry Run on How to Delete a Node Before a Given Position in a Singly Linked List
Code Implementation on How to Delete a Node at a Given Position in a Singly Linked List
#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
Created Linked List: 1 5 2 7
Linked List after Deletion at position 2: 1 5 7Time Complexity: O(n), as list traversal is needed.
Conclusion
In conclusion, deleting a node from a linked list at a given position is a crucial operation in linked list manipulation, and understanding the process is essential for efficient data management in computer programming. Throughout this article, we explored the intricacies of linked lists, delving into node structures, pointer manipulations, and traversal techniques to effectively delete a node at a specified position.
We learned that the delete operation involves careful handling of pointers to avoid memory leaks and maintain the integrity of the linked list. By following the step-by-step explanations and examples provided, readers can confidently implement the delete operation in various programming languages.
Frequently Asked Questions (FAQs) To Delete a Node Before Specified Position in Singly Linked List in C
Here are a few FAQs on how to delete a node from linked list at a given position.
1. Is it possible to delete a node from a linked list without traversing the list?
No, deleting a node from a linked list at a given position requires traversing the list to identify the target node and update the pointers.
2. What happens to the memory occupied by the deleted node in the linked list?
The memory occupied by the deleted node is deallocated and becomes available for other memory allocations in the program.
3. How can I delete a node at the beginning (head) of the linked list?
To delete the head node, update the head pointer to point to the next node in the list and free the memory of the original head node.
4. What happens if I try to delete a node from an empty linked list?
Deleting a node from an empty linked list is not possible, and appropriate checks should be implemented to handle such scenarios.
5. Can I delete multiple occurrences of the same value in a linked list?
Yes, you can delete multiple occurrences of the same value by repeating the delete operation until all occurrences are removed.
6. How does the time complexity of the delete operation in a linked list compare to an array?
The time complexity of the delete operation in a linked list is O(n) in the worst case, while for an array, it is O(n) for linear search plus O(n) for element shifting, resulting in an overall complexity of O(n^2) in the worst case.
7. Can I delete a node at a negative position in the linked list?
No, the position must be a positive integer within the valid range of the linked list size.