Linking Data Out

Overview

Just as there were three ways to add data to a list, there are three operational ways to remove data from a linked list. However, two of the ways can be taken care of in one operation for removal. Once again, working with linked lists is not terribly difficult but you will make mistakes if you don't draw your pictures before trying to write the code.

And with pencil in hand, let's take a look at removing nodes.

Removing A Node At The Head

Two conditions for removing data from the head of a linked list use the same process. First, consider the scenario where you are removing the first node in a linked list that has other nodes.

Linked list with multiple nodes.

To remove the first node, you simply assign the head reference to its next reference, as shown here.

Ah, but what if the list only has one node left, you ask? It's the same thing. Here is the node to be removed.

You assign the head reference to it's next reference, and here is the result.

When the process is done, the head reference is pointing to the next thing in the linked list which happens to be the NULL reference that was at the end of the node. The head reference is set to NULL, which by the way, is important for future operations, and it's done. Again, that's about all there is to it.

Removing A Node From Within A Linked List

If you checked for removal from the head reference, you can use one other strategy to remove from the rest of the list, including the last node. The key for removal is the same as the key for inserting. You have to conduct the operation from the node prior to the node you are removing so you can maintain the link from the prior node to the rest of the list. For that reason, you can search the list exactly the same way you searched it for inserting. Consider the following. The goal is to remove the node with the letter 'P' so the searching process must watch for two things: 1) Is the working reference not NULL (i.e., make sure you did not go off the end of the list), and 2) is the data at the next reference not equal to the desired letter?

With the specified tests in mind, the working reference will iterate up to the 'M' node when it sees that the 'M' node's next reference is equal to 'P' as shown here. Remember again, that you cannot conduct this searching operation until you have verified that the list is not empty and that the first item is not the desired value. For those actions, you will conduct the remove at head operation provided earlier on this page.

From there, it is just a matter of linking around the 'P' node as shown below. The 'M' node's next reference is assigned to the 'P' node's next reference, and the node is unlinked.

Of course there are a lot of ways to conduct this operation, as there is with inserting, appending, and so on, but this is the fundamental action that needs to be taken.

Advice From Mom

One of the things your Mom told you more times than you can remember is that you always put away your toys and things when you are done with them. This is also a requirement for linked list nodes. Each node has acquired memory from the OS and that memory must be put away when it is no longer used.

This is easy to do. Remember that the working pointer is pointed at the 'M' node, and the one to be removed is the 'P' node. A different (temporary) pointer would be assigned to the one to be deleted, as shown:

    // set the temporary pointer to the 'P' node
    tempPtr = wkgPtr->nextPtr;

    // make the link from 'M' node to 'R' node
    wkgPtr->nextPtr = tempPtr->nextPtr;

    // return the allocated memory to the operating system (free)
    free( tempPtr );

And it is almost exactly the same in C++:

    // set the temporary pointer to the 'P' node
    tempPtr = wkgPtr->nextPtr;

    // make the link from 'M' node to 'R' node
    wkgPtr->nextPtr = tempPtr->nextPtr;

    // return the allocated memory to the operating system (free)
    delete tempPtr;

One way or the other the memory return operation must happen, but it isn't terribly difficult.

Node Removal From A Linked List

As has been mentioned previously, and as you can see here, there really isn't anything difficult about linked lists, as long as you draw pictures. Some actions with linked lists are just plain too difficult if you haven't pulled out your paper and pencil and figured out your desired action. The next topic will briefly discuss a couple of other kinds of linked lists that can be used in certain circumstances. Enjoy!