Chapter 9.2.3 – Basic Linked List Processing | Introduction to Programming Using Java

Chapter 9.2.3 – Basic Linked List Processing | Introduction to Programming Using Java

 

9.2.3 Basic Linked List Processing

 

It is very common to want to process all the items in a linked list in some way. The common pattern is to start at the head of the list, then move from each node to the next by by following the pointer in the node, stopping when the null that marks the end of the list is reached. If head is a variable of type Node that points to the first node in the list, then the general form of the code is:

 

Chapter 9.2.3 - Basic Linked List Processing | Introduction to Programming Using Java

 

Our only access to the list is through the variable head, so we start by getting a copy of the value in head with the assignment statement runner = head. We need a copy of head because we are going to change the value of runner.

We can’t change the value of head, or we would lose our only access to the list! The variable runner will point to each node of the list in turn. When runner points to one of the nodes in the list, runner.next is a pointer to the next node in the list, so the assignment statement runner = runner.next moves the pointer along the list from each node to the next.

We know that we’ve reached the end of the list when runner becomes equal to null. Note that our list-processing code works even for an empty list, since for an empty list the value of head is null and the body of the while loop is not executed at all. As an example, we can print all the strings in a list of Strings by saying:

 

Chapter 9.2.3 - Basic Linked List Processing | Introduction to Programming Using Java

 

The while loop can, by the way, be rewritten as a for loop. Remember that even though the loop control variable in a for loop is often numerical, that is not a requirement. Here is a for loop that is equivalent to the above while loop:

 

Chapter 9.2.3 Basic Linked List Processing | Introduction to Programming Using Java

 

Similarly, we can traverse a list of integers to add up all the numbers in the list. A linked list of integers can be constructed using the class

 

Chapter 9.2.3 Basic Linked List Processing | Introduction to Programming Using Java

 

If head is a variable of type IntNode that points to a linked list of integers, we can find the sum of the integers in the list using:

 

Chapter 9.2.3 Basic Linked List Processing | Introduction to Programming Using Java

 

It is also possible to use recursion to process a linked list. Recursion is rarely the natural way to process a list, since it’s so easy to use a loop to traverse the list. However, understanding how to apply recursion to lists can help with understanding the recursive processing of more complex data structures.

A non-empty linked list can be thought of as consisting of two parts: the head of the list, which is just the first node in the list, and the tail of the list, which consists of the remainder of the list after the head. Note that the tail is itself a linked list and that it is shorter than the original list (by one node).

This is a natural setup for recursion, where the problem of processing a list can be divided into processing the head and recursively processing the tail. The base case occurs in the case of an empty list (or sometimes in the case of a list of length one). For example, here is a recursive algorithm for adding up the numbers in a linked list of integers:

 

Chapter 9.2.3 Basic Linked List Processing | Introduction to Programming Using Java

 

One remaining question is, how do we get the tail of a non-empty linked list? If head is a variable that points to the head node of the list, then head.next is a variable that points to the second node of the list—and that node is in fact the first node of the tail.

So, we can view head.next as a pointer to the tail of the list. One special case is when the original list consists of a single node. In that case, the tail of the list is empty, and head.next is null. Since an empty list is represented by a null pointer, head.next represents the tail of the list even in this special case. This allows us to write a recursive list-summing function in Java as

 

Chapter 9.2.3 - Basic Linked List Processing | Introduction to Programming Using Java

 

I will finish by presenting a list-processing problem that is easy to solve with recursion, but quite tricky to solve without it. The problem is to print out all the strings in a linked list of strings in the reverse of the order in which they occur in the list.

Note that when we do this, the item in the head of a list is printed out after all the items in the tail of the list. This leads to the following recursive routine. You should convince yourself that it works, and you should think about trying to do the same thing without using recursion:

 

Chapter 9.2.3 - Basic Linked List Processing | Introduction to Programming Using Java

 

In the rest of this section, we’ll look at a few more advanced operations on a linked list of strings. The subroutines that we consider are instance methods in a class, StringList. An object of type StringList represents a linked list of nodes.

The class has a private instance variable named head of type Node that points to the first node in the list, or is null if the list is empty. Instance methods in class StringList access head as a global variable. The source code for StringList is in the file StringList.java, and it is used in the sample program ListDemo.java.

Suppose we want to know whether a specified string, search item, occurs somewhere in a list of strings. We have to compare search item to each item in the list. This is an example of basic list traversal and processing. However, in this case, we can stop processing if we find the item that we are looking for.

 

Chapter 9.2.3 - Basic Linked List Processing | Introduction to Programming Using Java

 

It is possible that the list is empty, that is, that the value of head is null. We should be careful that this case is handled properly. In the above code, if head is null, then the body of the while loop is never executed at all, so no nodes are processed and the return value is false. This is exactly what we want when the list is empty, since the searchItem can’t occur in an empty list.

 

 

 

SEE MORE:

 

 

1 thought on “Chapter 9.2.3 – Basic Linked List Processing | Introduction to Programming Using Java”

Leave a Comment