How to Delete Node in a Linked List

A linked list is a data structure in programming where elements, called nodes, are linked together using pointers. Unlike arrays, linked lists allow dynamic memory allocation, making them flexible for tasks like inserting or deleting elements without shifting data. But how do you delete a node in a linked list when you only have a reference to that node? This is a common coding challenge that tests your understanding of linked list operations and efficient memory management. In this blog, you’ll learn what a linked list is, why it’s useful, and step-by-step instructions to delete a node effectively using Python.

Steps to Solve How to Delete a Node in a Linked List

• Understand the Linked List Structure:
  • A linked list consists of nodes where each node contains:
    • A value (data).
    • A pointer to the next node in the sequence.
• Identify the Problem:
  • You are given a reference to the node that needs to be deleted.
  • You don’t have access to the head of the linked list.
• Copy the Value of the Next Node:
  • Instead of directly deleting the node, copy the value of the next node into the current node.
• Update the Pointer:
  • Change the pointer of the current node to skip the next node by pointing it to the node after the next.
  • This effectively removes the next node from the linked list.
• Handle Edge Cases:
  • If the node to delete is the last node (tail), this method won’t work because there’s no next node to copy. Additional logic may be required if the problem constraints allow deletion of the tail.
• Test the Solution:
  • Example:
    • Input: Linked list: 4 -> 5 -> 1 -> 9, node to delete: 5
    • Process:
      • Copy 1 (value of the next node) into the node with 5.
      • Update the pointer to skip the node with 1.
    • Output: 4 -> 1 -> 9
• Validate the Result:
  • Ensure the modified linked list is correctly updated by traversing it and checking the values and pointers.

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

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!