1.
Introduction
2.
2.1.
C
2.2.
Complexities
2.2.1.
Time Complexity
2.2.2.
Auxiliary space complexity
3.
Problem Statement
3.1.
Example: Delete a Linked List Node at a Given Position
4.
Approach: Iterative
4.1.
Algorithm
4.2.
Example
4.3.
C++
4.4.
Java
4.5.
Python
5.
5.1.
5.2.
What are the types of linked lists?
5.3.
How do you delete one node in a linked list?
5.4.
What happens when you remove a node from a linked list?
5.5.
What is the time complexity for deleting a node from a linked list?
6.
Conclusion
Last Updated: Apr 20, 2024
Easy

# Delete Node in a Linked List

## 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

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.

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

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).

## Problem Statement

Deleting a node from a linked list at a given position involves removing a specific node from the list while maintaining the integrity of the list structure.

### Example: Delete a Linked List Node at a Given Position

Suppose we have the following linked list:

``````1 -> 2 -> 3 -> 4 -> 5
``````

If we want to delete the node at position 3 (counting from 1), the resulting linked list should be:

``1 -> 2 -> 4 -> 5``

## Approach: Iterative

In the iterative approach, we traverse the linked list until we reach the node just before the node to be deleted. Then, we update the pointers to bypass the node to be deleted.

### Algorithm

1. If the position to delete is 1, set the head pointer to the next node and delete the current head node.
2. Traverse the linked list until reaching the (position - 1)th node.
3. Update the pointers of the (position - 1)th node to bypass the node to be deleted.
4. Delete the node at the given position.

• C++
• Java
• Python

### C++

``#include <iostream>struct ListNode {    int val;    ListNode* next;    ListNode(int x) : val(x), next(nullptr) {}};void deleteNode(ListNode*& head, int position) {    if (head == nullptr)        return;    if (position == 1) {        ListNode* temp = head;        head = head->next;        delete temp;        return;    }    ListNode* prev = nullptr;    ListNode* current = head;    int count = 1;    while (current != nullptr && count < position) {        prev = current;        current = current->next;        count++;    }    if (current == nullptr)        return;    prev->next = current->next;    delete current;}void printList(ListNode* head) {    ListNode* current = head;    while (current != nullptr) {        std::cout << current->val << " -> ";        current = current->next;    }    std::cout << "nullptr" << std::endl;}int main() {    ListNode* head = new ListNode(1);    head->next = new ListNode(2);    head->next->next = new ListNode(3);    head->next->next->next = new ListNode(4);    head->next->next->next->next = new ListNode(5);    std::cout << "Original List: ";    printList(head);    int position = 3;    deleteNode(head, position);    std::cout << "List after deleting node at position " << position << ": ";    printList(head);    return 0;}``

### Java

``class ListNode {    int val;    ListNode next;    ListNode(int x) {        val = x;        next = null;    }}public class Main {    public static void deleteNode(ListNode head, int position) {        if (head == null)            return;        if (position == 1) {            ListNode temp = head;            head = head.next;            temp = null;            return;        }        ListNode prev = null;        ListNode current = head;        int count = 1;        while (current != null && count < position) {            prev = current;            current = current.next;            count++;        }        if (current == null)            return;        prev.next = current.next;        current = null;    }    public static void printList(ListNode head) {        ListNode current = head;        while (current != null) {            System.out.print(current.val + " -> ");            current = current.next;        }        System.out.println("null");    }    public static void main(String[] args) {        ListNode head = new ListNode(1);        head.next = new ListNode(2);        head.next.next = new ListNode(3);        head.next.next.next = new ListNode(4);        head.next.next.next.next = new ListNode(5);        System.out.print("Original List: ");        printList(head);        int position = 3;        deleteNode(head, position);        System.out.print("List after deleting node at position " + position + ": ");        printList(head);    }}``

### Python

``class ListNode:    def __init__(self, x):        self.val = x        self.next = Nonedef deleteNode(head, position):    if head is None:        return    if position == 1:        temp = head        head = head.next        temp = None        return    prev = None    current = head    count = 1    while current is not None and count < position:        prev = current        current = current.next        count += 1    if current is None:        return    prev.next = current.next    current = Nonedef printList(head):    current = head    while current is not None:        print(current.val, "->", end=" ")        current = current.next    print("None")if __name__ == "__main__":    head = ListNode(1)    head.next = ListNode(2)    head.next.next = ListNode(3)    head.next.next.next = ListNode(4)    head.next.next.next.next = ListNode(5)    print("Original List:", end=" ")    printList(head)    position = 3    deleteNode(head, position)    print("List after deleting node at position", position, ":", end=" ")    printList(head)``

Output

``````Original List: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
List after deleting node at position 3: 1 -> 2 -> 4 -> 5 -> nullptr``````

### What is a linked list?

A linked list is a sequential data structure that contains nodes and their addresses linked to the previous node. The first node in the linked list is called the head node, and the address field of the last node is pointed to null.

### How do you delete one node in a linked list?

We delete a node considering the position of the node. If the node is at the beginning or end of the list, we can just remove it. But if the node is in the middle of the list, we must delete it using the index and update the current pointer to its successive node.

### What happens when you remove a node from a linked list?

When we remove a node from the linked list, the address linked to the node should be deleted too, and the previous node is updated with the address of its successive node.

### What is the time complexity for deleting a node from a linked list?

The time complexity of deleting a node from the linked list is 0(1). Because we already know the index of the node so we can reach the node and delete it from the linked list.

## Conclusion

We have discussed the concept of the linked list and how to delete a node from a linked list in this article. You can find the coding problems related to the deletion and insertion of nodes in DSA here