Guide to Delete Node in a Linked List

And now we come to the curious case of node deletion. But how did we delete them? In fact, taking a node out of a linked list is one of the hardest things to accomplish when first introduced. Just think of yourself inside a to-do list. You are there in the middle, and you would like to take one particular task out without disturbing the other tasks.

Introduction: Why delete a node?

This is very similar to the scenario of deleting a node in a linked list, but we will sort it down to a small extent to relate more. Have you ever pulled a card out from a deck without disturbing the order of the rest of the remaining cards? Well, deleting a node from a linked list is more or less something similar to that. Be it preparing for coding interviews, preparing for companies, or working on some real-world projects; this technique should make it to your toolkit. So come on, let's jump into the world of linked lists and learn the art of node deletion.

Understanding a linked list

Before heading on to the process of deletion, let's understand briefly what a linked list structurally is. The linked list, or simply a list, is a type of data structure that consists of a sequence of elements, in this case, nodes, and the links that structure it. Each node stores data and contains a reference or link to the next element in the sequence. Such a setup makes insertion and deletion very efficient.

There can be different types of linked lists. Here, we discuss the singly linked list available in the program. In a singly linked list, the elements are linked, and every link contains a connection to the next link in the chain.

Algorithm to delete a node from a linked list

Tap through the abstract steps that describe the algorithm of deleting a certain node from a linked list. I'll walk you through it with an example in plain terms.

Step 1: Search for the node to be removed

First, you have to find the node to be deleted. So, let's say we have a linked list whose items are 1 -> 2 -> 3 -> 4 -> 5. Now, we want to delete the node containing the number 3 from the linked list.

Step 2: Traverse the list

Head from the element before the element you want to delete. For example, in this case, to delete '3' in the above example, you must skip '3' and head from 1 to 2, since 2 points to 3.

Step 3: Change the pointers

Change the current node's pointer. So now, replace its pointer to avoid the node to be deleted. For example, change the pointer at 2 to be directed towards 4, bypassing 3.

Step 4: Delete the node

Finally, delete the node by freeing its memory. In most languages, including Python, memory management is automatic. However, in C or C++, one would need to call the free() function to deallocate the memory that the deleted node was using.

Example in Python

Below is the example to show the above process:

1class Node:
2    def __init__(self, data):
3        self.data = data
4        self.next = None
5
6class LinkedList:
7    def __init__(self):
8        self.head = None
9
10    def append(self, data):
11        new_node = Node(data)
12        if not self.head:
13            self.head = new_node
14            return
15        last_node = self.head
16        while last_node.next:
17            last_node = last_node.next
18        last_node.next = new_node
19
20    def delete_node(self, key):
21        temp = self.head
22
23        if temp is not None:
24            if temp.data == key:
25                self.head = temp.next
26                temp = None
27                return
28
29        while temp is not None:
30            if temp.data == key:
31                break
32            prev = temp
33            temp = temp.next
34
35        if temp == None:
36            return
37
38        prev.next = temp.next
39        temp = None
40
41# Example usage:
42llist = LinkedList()
43llist.append(1)
44llist.append(2)
45llist.append(3)
46llist.append(4)
47llist.append(5)
48
49print("Original List: ")
50current = llist.head
51while current:
52    print(current.data, end=" -> ")
53    current = current.next
54
55llist.delete_node(3)
56
57print("\nList after deleting node with value 3: ")
58current = llist.head
59while current:
60    print(current.data, end=" -> ")
61    current = current.next

Key takeaways

• Update the pointers properly: Always make sure that the pointers are updated properly so that the list does not break.
• Handle edge cases: Be it the deletion of the head node or a node that doesn't exist in the list, you should handle the edge cases with care.
• Practice: Implement it in different languages to master the concept.

Conclusion

It might seem slightly confusing at first to delete a node in a linked list, but it actually becomes simple once the concept is clear and with a little practice. The key is to update the pointers in the right way and handle some edge cases. Happy coding!