Combining Single Linked List Operations (Object Orientated Implementation)

Note - The code examples used in this post are located at my GitHub account - OO Single Linked List

Over the past few posts, we've described and shown the implementation of the three basic linked list operations. Each post covered an operation (searching, insertion and deletion) with code individually detailing how it was performed without interference from the others.

Now that we know about all three operations and how they work, the last thing to do is to combine them all so we can make a properly functioning single linked list. 

If you were following through the code examples, you would have noticed that the language chosen for the implementation was Java, so it'd be fitting that we also utilise some OO (Object Orientated) concepts when we combine the operations together.

Deleting from a Single Linked List

Note - The code examples used in this post are located at my GitHub account - Single Linked Lists

In the past couple of posts we've covered the process of searching and inserting items into a single linked list. Now we're onto the last of the three basic operations of a single linked list, deletion.

Because we cannot directly access items in a single linked list like we can with an array, deleting an item from a single linked list involves the following steps - 

1. Finding the node in the list containing the item we want to remove. (If it exists)
2. Find the predecessor of the node we want to remove such that it can be re-coupled to the successor of the node. 
3. Linking the predecessor node with the successor node of the node we wish to remove.

Step 2 is particularly important as without performing the step, we will end up with two lists. 

If we think of our linked list as a line of coupled train carriages, if we remove one, we'll need to re-couple the carriages on either side of the one we removed to connect the train together again, otherwise we'll have unconnected carriages that will go nowhere when the train departs.

An illustration of what we want to try to achieve with deletion is shown below - 

Figure 1 - Deleting the node "Dave" from our linked list. 

Note - The dotted lines represent the operation that we want to achieve, which in this instance is to connect nodes "Jerry" and "Stuart" together since we want to remove "Dave". 

From Figure 1, the general idea is to link the incoming (predecessor) arrow with the outgoing (successor) arrow for the node that we want to remove.