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.

Linked Structures and Pointers

Linked structures and pointers are essentially containers that give us a way to store items in memory. Whilst linked structures provide the same functionality as an array (search, insertion and deletion), they are quite different in terms of its data structure, how the items are connected together and how the various operations (search, insertion and deletion) are performed.

To generalise, a linked structure contains the following -

1. Item - The item that is to be stored in this structure.
2. Pointer - A pointer to the next structure.

Algorithm Analysis (Big Oh)

The theoretical analysis of algorithms is one of the trickier topics to get the hang of when it comes to learning the fundamentals of computer science, however once you understand the basic concepts, with practice it begins to get easier.

The Basics:

The RAM model (Random Access Machine) is a form of algorithm analysis where we simplify how many steps it takes to perform particular computational tasks. For example, 

• Conditional statements (if, switch/case) and method calls are counted as 1 step.
• Loops (for, while) are counted by the maximum number of times they can loop.
• Memory access is counted as 1 step.

The idea is to use a simple computation model that does not consider other factors such as language used, processor speed, memory access speed or memory space. By using this simple model, we can focus solely on the algorithm itself by calculating it’s speed by counting the number of steps it takes to step through. 

Best, Worst and Average Case Complexity:

Complexity analysis is used to understand how good or bad an algorithm is over all instances (combinations) of data that the algorithm can accept. 

Mathematical Induction

What is mathematical induction:

Mathematical induction is a method of proving that a statement is true for all natural numbers. In the context of computer science, it can be used to prove that a recursive or incremental insertion algorithm is correct. 

Recursive or incremental algorithms can fall into two types of mathematical formulae:

• Arithmetic Progression - Difference between the sequence of numbers is constant. For example the sequence 2,4,6,8,10 (The difference between each number in the sequence is 2).

• Geometric Series - The ratio between the terms is constant or that each term is found by multiplying the previous by some constant.. For example the following sequence 2,4,8,16,32 (The sequence has a factor of 2 between each number)

Arrays

Code examples for this entry are located here - Arrays

Arrays are probably one of the most important yet basic data structures that we use. By definition, an array is a data structure that is used to represent a group of items that can be accessed by an index. In other words, we can imagine an array as the mailboxes along a street, where the number at the front of the mailbox represents the index and the street represents the size of the array.

Figure 1. An array represented as a group of mailboxes with index starting at 0

When we create an array, we usually give it a predefined size, which determines the maximum number of items we can store within it.

In programming languages such as Java and C, array indices always start from 0 rather than 1, which might cause some confusion initially. All this means is that to access the nth item in the array, we look for it in position n - 1.

Using our mailbox example and referring to Figure 1, the number of mailboxes is the size of our array, which in the above example is 4. The numbers on the mailbox themselves represent the array indices, which in this instance begins at 0 and goes to 3. This means that to get to the 2nd mailbox, we look for it at the n - 1 position, where n = 2. Subsequently to get to the 3rd mailbox, it is at position 2 and so forth.  

Continuing with our mailbox example, if we want to add or remove items from any mailbox, we access it by the same way in which we look for it. Once we have found it, we can easily add and remove items from our mailbox.