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.

In Figure 1, the single linked list proceeds from left to right, from the head to the node with the name "Dave". The directional arrow from each node indicates where the pointer is pointing to, where in this case only points to the next node in the list. 

In other words, this means that "John" knows about "Sue", "Sue" knows nothing about "John" but knows about "Dave" and "Dave" knows nothing of either "John" or "Sue". 

Data Structure Representation 

The data structure representation of a single linked list is identical to the generalised node structure that we described in the Linked Structures and Pointers introduction, so we won't describe it again.

Single Linked List Operations - 

As mentioned in the previous post, all linked structures have three basic operations, searching, inserting and deleting, which we'll dive into further detail here specifically for single linked lists. 

Over the next few posts, we'll slowly add the linked list operations so that we'll end up with functioning code that will allow us to search, insert and delete from a single linked list. 

To begin our adventure, we'll start with the search operation. 

Searching a Single Linked List - 

Searching a single linked list is the process of searching from the head of the list to the tail and determining at each step whether we've found the item that we are searching for.

The reason that we're required to start the search from the head of the list is because unlike an array, we do not have direct access to each node in a single linked list. Each node only knows about the next one, and nothing of the one that came before it.

The search operation can be implemented both iteratively and recursively.

Figure 2 - Searching a Single Linked List involves jumping from one node to the next till we've found our target or we've reached the end.

Iteratively Searching a Single Linked List - 

If we search a single linked list iteratively, all we do is create a loop that starts from the head of the list and loops through the list until we have met either of the following conditions

1. We have found the item
2. We have reached the end of the list

If we satisfy condition #1 we can break the loop at the matching node and return true indicating that the item we want to find is in the list, otherwise we will satisfy condition #2 and reach the end of our list, where the end is identified with a null next node pointer. 

Using Figure 2 as an example, if we're to search for the name "Sue", we would start the loop at the head of the list and determine if the first node we encounter satisfies either of the two conditions that we've outlined. The first node we encounter would be "John", which is neither the name we are looking for nor is it the end of the list, therefore we move to the next node and repeat the process again.

In this case we're looking for a node that contains "Sue", which is the node after "John", so once we've reached the found node, we can simply break out of the loop and return true indicating that we've found it. But what would happen if we were looking for a node named "Gary"? 

Using our basic linked list from Figure 2, if we continue looping from the start we would eventually get to the node "Dave" and notice that there is no pointer to a next node and it simply contains null. This means that we've reached the end of our list and met condition #2. In this situation the loop will terminate and because we haven't found "Gary" in our list, we'll need to return false.

The code required to implement the loop with our two conditions for searching is shown below:

/**
* Searching a Single Linked List through iteration.
* 
* @param head - the head or start of our linked list.
* @param item - the item which we are to search for.
* @return true if we find the name in our list, 
* false otherwise.
*/
public static boolean iterativeSearchList(Node head, String name) {

 // flag to indicate if we have found our name or not.
 boolean isFound = false;

 // reference to the current node we are looking at. 
 Node currentNode = head; 
  
 // Iterate through the list until we have no more nodes 
 // to look look at (Condition #2)
 while (currentNode != null) {
    // If the current node contains the name we are looking for
    // then we have found the name in our list and can return true
    // to indicate that we have found it. Because we have found it
    // we can also break out of this loop. (Condition #1)
    if (currentNode.getName().equals(name)) {
     isFound = true;
     break;
    }
    // If we have not found it we need to continue searching in the
    // next node.
    currentNode = currentNode.getNext();
 }
 return isFound;
 }
}

Figure 3 - Searching a Single Linked List through iteration. 

NOTE - The methods getName() and getNext() are convenience methods to retrieve data from the Node.

Recursively Searching a Single Linked List - 

If we search a linked list recursively, what we're aiming to do at each step of the recursion is to reduce the size of the list until we either find the item or we've reached the end. The terminating conditions for our recursive loop are the same as the one for the iterative loop mentioned above.

The way that it works recursively is that each time the conditions are not met, we call the search method again but we pass in the next node as the parameter as that will become the head of the smaller list. This stops the current execution of the search method on the current node and starts again on the next node. This continues until either of the terminating conditions are met, in which case it stops, and passes the answer back up through the previous method calls. 

Another way to think about the recursion is that each time the method calls itself, it puts the current execution onto a pile and continues on the new method. When the current instance (version) of the method finishes, it removes itself from the pile and passes control back to the one underneath and continues until there are no more methods left on the pile.

The code below outlines the method to search a single linked list recursively.

/**
 * Searching through a Single Linked List recursively. The
 * idea with recursion is that we reduce the size of the input
 * each time it calls itself.
 * 
 * @param head - the head or start of our linked list.
 * @param name - the name that we are searching for.
 * @return true if the name is in 
 */
public static boolean recursiveSearchSingleLinkedList(Node head, String name) {

 // If the current head is null, it means we've
 // reached the end of our list. (Condition #2)
 if (head == null) {
    return false;
 }

 // If the current node contains the name we're
 // looking for, we can return true (Condition #1)
 if (head.getName().equals(name)) {
     return true;
 }
 else {
    // If we've not satisfied either condition, we must call the
    // method again but with the next node, reducing the list size.
    return recursiveSearchSingleLinkedList(head.getNext(), name);
 }


}

Figure 4 - Searching a Single Linked List through recursion. 

(Notice the similarities in terminating conditions)

Searching a single linked list both recursively and iteratively require satisfying the same general condition. The only difference in each case is how we go proceed through each node in the list.

Complexity - 

The worst case time complexity to search a single linked list is O(n) where n is the number of nodes in our list. The reason for this is because we do not know where the item is within our list and also the nature of how we traverse a single linked list.

Because there is only a single access point into the list, our item could be anywhere, and in the worst case it might not exist in the list at all. However to prove that, we must at the very least step through n nodes to find out whether it exists in our list or not.

The best case is if the item was always at the head of the list, however this cannot be guaranteed, and as the general rule of thumb we always take the worst case scenario.

Summary - 

Searching is one of the fundamental operations that can be performed on a linked list. Whether it is done recursively or iteratively, once you know the general method of stepping from one node to the next, the implementation appears quite simple. A few pointers to take away from this post are - 

1. The head of the single linked list is the only entry point to any item in the list.
2. Each node only knows about it's successor (next) and nothing of its predecessor.
3. Searching a linked list involves stepping into each node and checking the data, if its found then we can return, otherwise we proceed to the current nodes successor and continue the search.
4. Whether searching recursively or iteratively, we have the same two base conditions that will be satisfied, thus their individual implementations are very similar.

In the next couple of posts, we'll continue along with how to perform the other operations of a single linked list. 

Exercises - 

1. Using the provided code as a starting point, implement a method that prints the contents of a single linked list both iteratively and recursively.