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.

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)