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.