Contents  Introduction  Getting Started  The Linked List  Node Design  Node Allocation  Node Insertion  - Unsorted  Linked List  Traversal  Searching  Node Deletion  End of File  Source code  Printable version  Adobe PDF version     The Series  Linked Lists

Node Deletion

We're getting close to the end now, as it's time to talk about node deletion. Node deletion is a little bit different compared to the other linked list functions in that you must think of all the special cases that may come up. If you don't think of every special case, you might end up with severe memory leaks, crashes, or in the not-so-bad case, just a program that refuses to delete the desired node.

For all of the dynamic data structures we discuss in this series, we will need to go through and determine all the cases that will come up when deleting nodes for the data structure we discuss. So let's begin by determining the cases involved in deleting nodes from a linked list.

To start off, let's discuss the simplest case: deletion of a node in the middle of the list. Let's say we already know what data we want to delete, and we put it in a key node. The first thing we need to do is find the pointer to that node. To accomplish that, we use the Find function that we just created and call the found node current. The next thing we need to do is find the node that links to the node that was just found, which we will call previous. From here, we can now bypass the link to the current node by changing the previous node's link to point to the current node's link. This will "skip" the current node in the linked list chain, but we have not lost this memory since we still have the current pointer. Now that the linked list is intact, we can free the memory used by the current pointer. Take a look at Figure 1.6 to see how this is done.

Now we need to think about another potentially hazardous case of node deletion: the desired node is the first node in the list, but not the only node. In a case like this, all we need to do is set current to the head node, and then move the head pointer to the next node in the list. From there, we just free the current node pointer. Take a look at Figure 1.7 for a better idea.

That's it. There are no more cases for deletion in a singly linked list. You do, however, need to put a verification that the desired node was in fact found, or you could run into some access violation problems.

Here is our delete function:

void DeleteNode(node_t **head, node_t keyRecord)
{
  node_t *delNode;// node to delete
  node_t *previous;// node before the deleted node

  // find our node to delete
  delNode = Find(*head, keyRecord);

  // if desired record is not in the list, exit the function
  if (delNode == NULL)
  {
    printf("Record not found.\n");
    return;
  }

  if (delNode == *head)
  {
    // first node in the list, but not the only node
    // move the head to the second node in the list
    *head = delNode->next;
    free((void*)delNode);
  }
  else
  {
    // any other case
    previous = *head;

    // search through the list for the node before our deleted node
    while (previous->next != delNode)
    {
      previous = previous->next;
    }

    // link the previous node to the node after our deleted node
    previous->next = delNode->next;

    if (delNode != NULL)
    {
      free((void*)delNode);// free the memory
      delNode = NULL;
    }
  }
}

Next : End of File