Deleting from a Doubly Linked List

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

In the past couple of posts we've covered the process of searching and inserting items into a doubly linked list. This post will cover the last of the three basic operations on doubly linked lists, deletion.

Since there is no way to directly access items in a doubly linked list like we can with an array, deleting an item involves the following steps. 

1. Search through the list to find the node we want to remove (if it exists). 
2. Connect the predecessor of the found node to the next of found node. 

Step 2 is important as if we do not complete this step then we would have two separate lists since we would have removed the connecting node.

Inserting into a Doubly Linked List

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

Previously we covered the algorithm for recursively searching through a doubly linked list. It provided a detailed insight into how to traverse through a linked structure and to find and return items within it. 

Searching is an important functionality of a doubly linked list, however without any content to search for, it doesn't really do much. In this post, we'll cover the insertion algorithm so that we can start putting items into our doubly linked list and search for them. 

Doubly Linked Lists (Searching)

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

A doubly linked list is another example of a linked structure. As with single linked lists, it also comprises of a group of nodes connected together in a chain to form the list. 

The nodes in a doubly linked list contain the following properties -

1. The data field(s) - each node can contain any number of data fields.
2. Pointer to next - each node contains a pointer to the successor node in the list.
3. Pointer to previous - each node contains a pointer to its predecessor node in the list. 

The doubly linked list gets its name from the number of pointers that each node has. With the two pointers, each node knows about both its successor and predecessor.

Figure 1 - Doubly Linked List Structure.

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. 

Inserting into a Single Linked List

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

We have previously covered the process of performing a search on a single linked list. In that post, we used a pre-constructed list to provide the basis of our search operation.  Whilst that demonstrated how to go about searching through a single linked list, it didn't shed much light on how we could build our own lists from scratch. In this post, we'll cover the second of the three basic operations of a single linked list, insertion. 

Single Linked Lists (Searching)

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

A single linked list is the simplest of the linked structures. It comprises of a group of nodes that are connected together in a directional chain that form the list. 

Each node can contain any number number of data fields, but only contains one pointer that always points to the next node in the list. This means that each node in a single linked list only knows about its successor and nothing of its predecessor. 

Figure 1 - Single Linked List Structure.