Introduction
A linked list is a sequential data structure that contains nodes and their addresses linked to the previous node. The first node in a linked list is the "head" node, and the address field of the last node is pointed to null. There are three types of linked lists. They are
- Single linked list
- Doubly Linked List
- Circular linked list
In this article, let’s learn how to delete a linked list node at a given position.
Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.
Linked List Implementation
We have a recursive method where we delete the node by passing the node as a reference to the function. We find the node which is to be deleted and deallocate the memory of the node to delete it and later change the previous node pointer to the next node. The complexity of this method is O(n). But recursion might be complex and the auxiliary space can be O(n). So we prefer an iterative method that has an auxiliary space of O(1). Let’s discuss the iterative method with an example.
We can delete the node from anywhere in the linked list. It can be from; the beginning of the list, the middle of the list, or the end of the list. If the node is at the beginning or end of the list, we can remove it. But if the node is in the middle of the list, we use the traversal technique to advance to the following nodes through the links and find the element with the given index to be deleted. We must delete it using the index and update the current pointer to its successive node. Suppose we have a linked list with the elements 8, 52, 43, and 16.
We can delete node 8 from the beginning of the list with index 0 quickly. Similarly, we can delete node 16 at last with the index as the total length of the linked list - 1. But if we want to delete any element from the middle, we need to traverse over the list until we arrive at the required index and delete the node along with its address link.
Let’s learn how to delete a node from a linked list through the following example.
- C
C
#include<stdio.h>
#include<stdlib.h>
void push(int);
void display_List();
void delete(int);
struct node {
int data;
struct node *next;
}*head=NULL,*tail=NULL;
void delete(int pos) {
struct node *temp = head;
int i;
if(pos==0) {
head=head->next; // incrementing the head pointer
temp->next=NULL;
free(temp); // Node is deleted
} else {
for(i=0;i<pos-1;i++) {
temp=temp->next;
}
struct node *del =temp->next;
temp->next=temp->next->next;
del->next=NULL;
free(del); // Node is deleted
}
printf("\nUpdated Linked List is : \n");
display_List();
return ;
}
void push(int value) {
struct node *newnode; // Creating a new node
newnode = (struct node *)malloc(sizeof(struct node));
newnode->data = value; // Assigning value to newnode
newnode->next = NULL;
if(head==NULL) {
head = newnode;
tail = newnode;
} else {
tail->next=newnode;
tail=newnode;
}
return ;
}
void display_List() {
struct node *temp;
temp=head;
while(temp!=NULL) {
if(temp->next==NULL) {
printf(" %d->NULL",temp->data);
} else {
printf(" %d->",temp->data);
}
temp=temp->next;
}
printf("\n");
return ;
}
int main() {
int n;
push(8);
push(52);
push(43);
push(16);
printf("The linked list is: ");
display_List();
printf("Enter position to delete: ");
scanf("%d", &n);
delete(n);
return 0;
}
Output
The linked list is: 8-> 52-> 43-> 16->NULL
Enter position to delete: 2
Updated Linked List is :
8-> 52-> 16->NULL
In the above code, we created a linked list with the elements 8, 52, 43, and 16. The user will enter a number as an index to delete the node in the given index from the linked list. The element will be deleted from the linked list, the next node in the list will be pointed to its previous node, and its address will be updated. The time complexity of deleting a node from a linked list is 0(n).
Complexities
Time Complexity
The time complexity of the given solution is O(N), where N is the number of elements in the given array.
Reason: We are traversing the entire array to find the number we have to delete, hence the complexity is O(N).
Auxiliary space complexity
The Auxiliary space complexity of the given solution is O(1).
Reason: We need a temporary variable to store the node we need to delete, hence the space complexity is O(1).
Also read - Merge sort in linked list
8+ registered 