Arrays

Arrays5

❯

Stacks

Stacks4

❯

Queues

Queues4

❯

Linked Lists

Linked Lists16

❯

Trees

Trees3

❯

Trie

Trie1

❯

1Trie Introduction

Singly Linked List – Delete Operation

⬅ Previous TopicSingly Linked List – Insert Operation

Next Topic ⮕Singly Linked List – Traversal Operation

Contents

Intro Example Pseudocode Examples Time Space

Delete Operation in Singly Linked List

After deleting node at index/position = 2.

Deleting from a singly linked list means removing a node from a specific position. We adjust the next pointer of the previous node to skip the node being deleted.

This operation can be done at the beginning, in the middle, or at the end of the list depending on the index.

Visual Example

Suppose we have a list:

We want to delete the node at index 2 (value 30), so the final list becomes: 10 → 20 → 40 → null

Step-by-Step Deletion at Index 2

Start with list 10 → 20 → 30 → 40 → null.
Traverse to node at index 1 (value 20).
Set current.next = current.next.next (i.e., 20 skips 30 and points to 40).
The node with value 30 is now disconnected and will be garbage collected.

Complete Pseudocode: Delete Node in Singly Linked List

This pseudocode shows how to delete a node at a specific index in a singly linked list.

function deleteAt(head, index):
    if index == 0:
        return head.next

    curr = head
    for i in range(index - 1):
        curr = curr.next

    if curr.next is not null:
        curr.next = curr.next.next

    return head

Let’s walk through each part of the code to understand what it does.

function deleteAt(head, index):

Explanation: The function is defined to delete a node at the given index from the singly linked list.

    if index == 0:
        return head.next

Explanation: If the index is 0, it means the head node should be deleted. We return head.next, which becomes the new head of the list.

    curr = head
    for i in range(index - 1):
        curr = curr.next

Explanation: For deletion at other positions, we first move curr to the node just before the one we want to delete by looping index - 1 times.

    if curr.next is not null:
        curr.next = curr.next.next

Explanation: This ensures we’re not at the end of the list. If the next node exists, we skip it by pointing curr.next to curr.next.next, effectively deleting the target node.

    return head

Explanation: We return the original head so the caller can continue to use the updated list.

Singly Linked List Delete Operation Examples

The following examples demonstrate how to delete a node from various positions in a singly linked list.

Initial List	Delete Index	Final Linked List	Explanation
[10, 20, 30]	0	20 → 30 → null	Delete at the beginning. Head node is removed. New head is the next node.
[10, 20, 30]	1	10 → 30 → null	Delete from the middle. Node at index 1 (value 20) is skipped by adjusting the next pointer of the previous node.
[10, 20, 30]	2	10 → 20 → null	Delete at the end. Tail node (value 30) is removed. New tail points to `null`.
[10, 20, 30]	5	Error	Invalid index. The index is greater than the list size. Most implementations will throw an error or return failure.

Time Complexity of Singly Linked List Delete Operation

Deletion Case	Time Complexity	Explanation
Delete at Beginning	O(1)	We update the `head` pointer to point to the next node. No traversal is needed.
Delete at Middle	O(n)	We must traverse the list to find the node just before the one to delete. This requires linear time.
Delete at End	O(n)	We must traverse to the second-last node to update its `next` pointer to `null`.
Delete by Value	O(n)	We traverse to find the first node with the target value, which may require scanning the whole list.

Space Complexity of Singly Linked List Delete Operation

Deletion Case	Space Complexity	Explanation
Delete at Beginning	O(1)	No extra memory is used. Only the `head` pointer is updated.
Delete at Middle	O(1)	No extra space is needed; the node is removed by pointer reassignment.
Delete at End	O(1)	Even though traversal takes time, no additional space is required to perform deletion.
Delete by Value	O(1)	Space remains constant regardless of position of value.

Key Concepts

Head deletion: Simply move the head pointer to head.next.
Middle deletion: Traverse to (index - 1), skip the node to be deleted by updating the next pointer.
Tail deletion: Traverse to second-last node and set its next to null.
Delete by value: Search for node with the given value, update previous node’s next.
Always check if the list is empty before deleting and handle edge cases like single-node lists.

⬅ Previous TopicSingly Linked List – Insert Operation

Next Topic ⮕Singly Linked List – Traversal Operation

Comments

Loading comments...

Linked Lists❯