Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 45

Searching and Deleting Nodes in a Singly Linked List

Recommended resources

Introduction

In our last lesson, we built the essential functions for populating a linked list, allowing us to add new items to our game inventory at the beginning, at the end, or in sorted order. With a list full of items, the next logical steps are to find specific items and remove them. This lesson completes the core set of operations on our data structure by focusing on precisely that: searching for and deleting nodes.

You will learn to implement functions to locate a node by its value and then safely remove it from the list, regardless of its position. Mastering this is crucial for managing a dynamic inventory, where items are constantly being acquired, used, or dropped. We'll pay close attention to pointer manipulation and memory management, building directly on the concepts of traversal and double pointers from our previous session.

Searching a Linked List

Before we can delete an item by its value (e.g., removing a "Health Potion"), we must first find it. The process of searching a linked list is a fundamental traversal algorithm. You start at the head and move from node to node until you either find the value you're looking for or reach the end of the list (NULL).

The logic is simple:

  1. Create a temporary pointer, current, and initialize it to the head of the list.
  2. Loop as long as current is not NULL.
  3. Inside the loop, check if the data in the current node matches the key you're searching for.
  4. If it's a match, the search is successful. You can return a pointer to the node or simply a true value.
  5. If it's not a match, advance to the next node: current = current->next.
  6. If the loop completes without finding the key, the search fails, and you can return NULL or false.

The following resource provides a complete, professional C implementation of this logic.

Linked List Operations: Traverse, Insert and Delete

This article from Programiz contains a full C code example for various linked list operations. We will focus on the searchNode function.

Within the C code block, locate the function int searchNode(struct Node** head_ref, int key). Study this function to see the traversal algorithm in action. Note how it returns 1 for success and 0 for failure. This function is a concise implementation of the search logic.

Deleting a Node from a Linked List

Deleting a node is more intricate than insertion because you must correctly "un-wire" the node from the list before freeing its memory. A mistake here can either break the chain or, worse, create a memory leak.

There are three main scenarios to consider when deleting a node, which are expertly outlined in the following video.

How to Delete a Node in a Linked List by Searching for a Value

This video from Gina Sprint provides a fantastic overview of the deletion process, breaking it down into manageable cases.

Please watch the introduction from the beginning to the three cases. This will give you a clear mental map of the problem: handling an empty list, deleting the head, and deleting a node from the middle or end.

Let's examine these cases one by one.

Case 1: Deleting the Head Node

This is a critical special case. If the item to be deleted is the very first one in our inventory, we must update the list's head pointer. As you'll recall from our previous lesson on insertion, any function that might change the head of the list needs access to the original head pointer. This is where using a double pointer (struct Node **head_ref) is essential.

The algorithm is:

  1. Check if the list is non-empty and if the head node contains the value to be deleted.
  2. Create a temporary pointer (temp) to hold the current head node.
  3. Update the list's head to point to the next node (*head_ref = temp->next).
  4. Free the memory of the original head node using the temporary pointer (free(temp)).
This diagram illustrates the steps for deleting the head node. A temporary pointer is used to save the location of the node after the head. The old head is freed, and the list's head pointer is updated to the saved location.

Case 2: Deleting a Node in the Middle or at the End

This is the general case. To remove a node from the middle or end of the list, you need to find it, but you also need to modify the next pointer of the node before it. This requires keeping track of two pointers as you traverse: a current pointer and a previous pointer.

The algorithm is:

  1. Initialize current to the head of the list and previous to NULL.
  2. Traverse the list, advancing both pointers (previous = current; current = current->next;) until you find the node to delete or reach the end.
  3. If the node is found (current != NULL), you "splice" it out by linking the previous node to the current node's successor: previous->next = current->next.
  4. Finally, free(current) to release its memory.

This two-pointer traversal technique is a cornerstone of linked list manipulation. The following video segment provides an excellent trace of this exact process.

How to Delete a Node in a Linked List by Searching for a Value

Let's return to Gina Sprint's video to see a walkthrough of the prev/cur pointer technique for deleting a node from the middle.

Watch the segment from the main algorithm. Pay close attention to how the prev and cur pointers advance and how the link is re-established once the target node is found.

A Complete Implementation

Now, let's combine these cases into a single, robust deleteNode function. The code will first check the head case, and if that doesn't apply, it will proceed with the prev/cur traversal to handle the middle/end case.

The Programiz article you reviewed for searching also provides an excellent C implementation for deletion.

Linked List Operations: Traverse, Insert and Delete

Let's look at the complete deleteNode function from the same Programiz C code block.

Find and study the function void deleteNode(struct Node** head_ref, int key). Trace its logic: The head deletion case, which handles removing the first node. The traversal loop, which uses prev and temp (our current) pointers. The final steps, which handle the case where the key is not found, or perform the splice-and-free operation.

To see this code built from scratch and tested, you can also watch the coding portion of Gina Sprint's video.

How to Delete a Node in a Linked List by Searching for a Value

This part of the video translates the algorithm we've discussed into a complete C function and tests it.

You can watch the section from coding it up to see the if-else structure that handles the head vs. middle cases. The following segment, testing the code, is also valuable as it demonstrates the function's correctness with various scenarios.

An Alternative Approach: The "Look-Ahead"

The prev/cur pointer method is very common, but there is another valid technique that uses only one traversal pointer. This method involves "looking ahead" to the next node's value.

The logic is as follows:

  • Handle the head deletion as a separate special case.
  • For the general case, start a current pointer at the head.
  • Loop while current->next is not NULL.
  • In the loop, check if current->next->data is the value to be deleted.
  • If it is, you've found the node before the one to delete. You can then perform the splice:
    • Save the node to delete: node_to_delete = current->next.
    • Rewire the link: current->next = node_to_delete->next.
    • Free the memory: free(node_to_delete).

This approach is conceptually interesting and is demonstrated well in the following video.

Removing an element from a linked list

This video from CodeVault illustrates the "look-ahead" technique for deletion.

First, watch the visual explanation from the visual concept. Then, see the code implementation in the segment from the code walkthrough. Notice how this implementation must still handle deleting the root as a separate case before the main loop (the root case).

While both the prev/cur and "look-ahead" methods work, many programmers find the prev/cur pattern slightly more straightforward, as the main loop's logic directly operates on the current node rather than its successor.

Conclusion

You have now completed the fundamental set of linked list manipulations: insertion, searching, and deletion. With these tools, your linked list is no longer just a static chain but a fully dynamic data structure capable of managing the contents of a game inventory.

Key Takeaways:

  • Searching is a basic traversal that moves from node to node until a match is found or the list ends.
  • Deletion must handle three distinct cases: an empty list, removing the head node, and removing a node from the middle or end.
  • Deleting the head is a special case that requires updating the list's main head pointer, making a double pointer (**head_ref) the ideal tool.
  • Deleting from the middle/end is typically handled with a previous and current two-pointer traversal to allow for the "splicing" of the node out of the list.
  • Memory management is non-negotiable: you must always call free() on the deleted node's memory to prevent memory leaks.

In our next lesson, we will address the final piece of the puzzle: safely destroying an entire linked list. You will write a function that traverses the whole list and deallocates every single node, ensuring our program is clean and leak-free when an inventory is no longer needed.