Section 11.2
Linking Objects
EVERY USEFUL OBJECT contains instance variables. When the type of an instance variable is given by a class or interface name, the variable can hold a reference to another object. Such a reference is also called a pointer, and we say that the variable points to the object. (Of course, any variable that can contain a reference to an object can also contain the special value null, which points to nowhere.) When one object contains an instance variable that points to another object, we think of the objects as being "linked" by the pointer. Data structures of great complexity can be constructed by linking objects together.
Something interesting happens when an object contains an instance variable that can refer to another object of the same type. In that case, the definition of the object's class is recursive. Such recursion arises naturally in many cases. For example, consider a class designed to represent employees at a company. Suppose that every employee except the boss has a supervisor, who is another employee of the company. Then the Employee class would naturally contain an instance variable of type Employee that points to the employee's supervisor:
class Employee {
// An object of type Employee holds data about
// one employee.
String name; // Name of the employee.
Employee supervisor; // The employee's supervisor.
.
. // (Other instance variables and methods.)
.
} // end class Employee
If emp is a variable of type Employee, then emp.supervisor is another variable of type Employee. If emp refers to the boss, then the value of emp.supervisor should be null to indicate the fact that the boss has no supervisor. If we wanted to print out the name of the employee's supervisor, for example, we could use the following Java statement:
if ( emp.supervisor == null) {
System.out.println( emp.name " is the boss!" );
}
else {
System.out.print( "The supervisor of " + emp.name + " is " );
System.out.println( emp.supervisor.name );
}
Now, suppose that we want to know how many levels of supervisors there are between a given employee and the boss. We just have to follow the chain of command through a series of supervisor links, and count how many steps it takes to get to the boss:
if ( emp.supervisor == null ) {
System.out.println( emp.name " is the boss!" );
}
else {
Employee runner; // For "running" up the chain of command.
runner = emp.supervisor;
if ( runner.supervisor == null) {
System.out.println( emp.name
+ " reports directly to the boss." );
}
else {
int count = 0;
while ( runner.supervisor != null ) {
count++; // Count
runner = runner.supervisor;
}
System.out.println( "There are " + count
+ " supervisors between " + emp.name
+ " and the boss." );
}
}
As the while loop is executed, runner points in turn to the original employee, emp, then to emp's supervisor, then to the supervisor of emp's supervisor, and so on. The count variable is incremented each time runner "visits" a new employee. The loop ends when runner.supervisor is null, which indicates that runner has reached the boss. At that point, count has counted the number of steps between emp and the boss.
In this example, the supervisor variable is quite natural and useful. In fact, data structures that are built by linking objects together are so useful that they are a major topic of study in computer science. We'll be looking at a few typical examples. In this section and the next, we'll be looking at linked lists. A linked list consists of a chain of objects of the same type, linked together by pointers from one object to the next. This is much like the chain of supervisors between emp and the boss in the above example. It's possible to have more complex situations, in which one object can contain links to several other objects. We'll look at an example of this in Section 4.
For the rest of this section, linked lists will be constructed out of objects belonging to the class Node which is defined as follows:
class Node {
String item;
Node next;
}
The term node is often used to refer to one of the objects in a linked data structure. Objects of type Node can be chained together as shown in the top part of the above picture. The last node in such a list can always be identified by the fact that the instance variable next in the last node holds the value null instead of a pointer to another node.
Although the Nodes in this example are very simple, we can use them to illustrate the common operations on linked lists. Typical operations include deleting nodes from the list, inserting new nodes into the list, and searching for a specified String among the items in the list. We will look at subroutines to perform all of these operations. The subroutines are used in the following applet, which demonstrates the three types of operation. In this applet, you start with an empty list, so you have to add some strings to it before you can do anything else. The "find" operation just tells you whether a specified string is in the list.
The applet uses a class, named StringList, to do the list operations. An object of type StringList represents a linked list of Nodes. We'll be looking at a few aspects of this class in detail. The complete source code can be found in the file StringList.java. (A standalone program that does the same thing as the applet can be found in the file ListDemo.java. This program is pretty straightforward, so I won't consider it further.)
For a linked list to be used in a program, that program needs a variable that refers to the first node in the list. It only needs a pointer to the first node since all the other nodes in the list can be accessed by starting at the first node and following links along the list from one node to the next. In the sample program, an object of type StringList has an instance variable named head that serves this purpose. The variable head is of type Node, and it points to the first node in a linked list. If the list is empty, the value of head is null.
Suppose we want to know whether a specified string, searchItem, occurs somewhere in the list. We have to compare searchItem to each item in the list. To do this, we use a variable of type Node to "run" along the list and look at each node. Our only access to the list is through the variable head, so we start by getting a copy of the value in head:
Node runner = head; // Start at the first node.
We need a copy 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. To move from one node to the next, it is only necessary to say runner = runner.next. We'll know that we've reached the end of the list when runner becomes equal to null. All this is done in the instance method find() from the StringList class:
public boolean find(String searchItem) {
// Returns true if the specified item is in the list, and
// false if it is not in the list.
Node runner; // A pointer for traversing the list.
runner = head; // Start by looking at the head of the list.
// (head is an instance variable.)
while ( runner != null ) {
// Go through the list looking at the string in each
// node. If the string is the one we are looking for,
// return true, since the string has been found.
if ( runner.item.equals(searchItem) )
return true;
runner = runner.next; // Move on to the next node.
}
// At this point, we have looked at all the items in the list
// without finding searchItem. Return false to indicate that
// the item does not exist in the list.
return false;
} // end find()
The pattern that is used in this routine occurs over and over: If head is a variable that refers to a linked list, then to process all the nodes in the list, do
runner = head;
while ( runner != null ) {
.
. // Process the node that runner points to.
.
runner = runner.next;
}
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. This is exactly what we want when the list is empty.
The problem of inserting a new item into the list is more difficult. (In fact, it's probably the most difficult operation on linked data structures that you'll encounter in this chapter.) In the StringList class, the items in the nodes of the linked list are kept in increasing order. When a new item is inserted into the list, it must be inserted at the correct position according to this ordering. This means that, usually, we will have to insert the new item somewhere in the middle of the list, between two existing nodes. To do this, it's convenient to have two variables of type Node, which refer to the existing nodes that will lie on either side of the new node. In the following illustration, these variables are previous and runner. Another variable, newNode, refers to the new node. In order to do the insertion, the link from previous to runner must be "broken," and new links from previous to newNode and from newNode to runner must be added:
The command "previous.next = newNode;" can be used to make previous.next point to the new node, instead of to the node indicated by runner. And the command "newNode.next = runner" will set newNode.next to point to the correct place. However, before we can use these commands, we need to set up runner and previous as shown in the illustration. The idea is to start at the first node of the list, and then move along the list past all the items that are less than the new item. While doing this, we have to be aware of the danger of "falling off the end of the list." That is, we can't continue if runner reaches the end of the list and becomes null. If insertItem is the item that is to be inserted, and if we assume that it does, in fact, belong somewhere in the middle of the list, then the following code would correctly position previous and runner:
Node runner, previous;
previous = head; // Start at the beginning of the list.
runner = head.next;
while ( runner != null && runner.item.compareTo(insertItem) < 0 ) {
previous = runner; // "previous = previous.next" would also work
runner = runner.next;
}
(This uses the compareTo() instance method from the String class to test whether the item in the node is less than the item that is being inserted. See Section 2.3.)
This is fine, except that the assumption that the new node is inserted into the middle of the list is not always valid. It might be that insertItem is less than the first item of the list. In that case, the new node must be inserted at the head of the list. This can be done with the instructions
newNode.next = head; // Make newNode.next point to the old head.
head = newNode; // Make newNode the new head of the list.
It is also possible that the list is empty. In that case, newNode will become the first and only node in the list. This can be accomplished simply by setting head = newNode. The following insert() method from the StringList class covers all of these possibilities:
public void insert(String insertItem) {
// Add insertItem to the list. It is allowed to add
// multiple copies of the same item.
Node newNode; // A Node to contain the new item.
newNode = new Node();
newNode.item = insertItem; // (N.B. newNode.next is null.)
if ( head == null ) {
// The new item is the first (and only) one in the list.
// Set head to point to it.
head = newNode;
}
else if ( head.item.compareTo(insertItem) >= 0 ) {
// The new item is less than the first item in the list,
// so it has to be inserted at the head of the list.
newNode.next = head;
head = newNode;
}
else {
// The new item belongs somewhere after the first item
// in the list. Search for its proper position and insert it.
Node runner; // A node for traversing the list.
Node previous; // Always points to the node preceding runner.
runner = head.next; // Start by looking at the SECOND position.
previous = head;
while (runner != null && runner.item.compareTo(insertItem) < 0) {
// Move previous and runner along the list until runner
// falls off the end or hits a list element that is
// greater than or equal to insertItem. When this
// loop ends, runner indicates the position where
// insertItem must be inserted.
previous = runner;
runner = runner.next;
}
newNode.next = runner; // Insert newNode after previous.
previous.next = newNode;
}
} // end insert()
If you were paying close attention to the above discussion, you might have noticed that there is one special case which is not mentioned. What happens if the new node has to be inserted at the end of the list? This will happen if all the items in the list are less than the new item. In fact, this case is already handled correctly by the subroutine, in the last part of the if statement. If insertItem is less than all the items in the list, then the while loop will end when runner has traversed the entire list and become null. However, when that happens, previous will be left pointing to the last node in the list. Setting previous.next = newNode adds newNode onto the end of the list. Since runner is null, the command newNode.next = runner sets newNode.next to null. This is the correct value that is needed to mark the end of the list.
The delete operation is similar to insert, although a little simpler. There are still special cases to consider. When the first node in the list is to be deleted, then the value of head has to be changed to point to what was previously the second node in the list. Since head.next refers to the second node in the list, this can be done by setting head = head.next. (Once again, you should check that this works when head.next is null, that is, when there is no second node in the list. In that case, the list becomes empty.)
If the node that is being deleted is in the middle of the list, then we can set up previous and runner with runner pointing to the node that is to be deleted and with previous pointing to the node that precedes that node in the list. Once that is done, the command "previous.next = runner.next;" will delete the node. The deleted node will be garbage collected.
Here is the complete code for the delete() method:
public boolean delete(String deleteItem) {
// If the specified string occurs in the list, delete it.
// Return true if the string was found and deleted. If the
// string was not found in the list, return false. (If the
// item exists multiple times in the list, this method
// just deletes the first one.)
if ( head == null ) {
// The list is empty, so it certainly
// doesn't contain deleteItem.
return false;
}
else if ( head.item.equals(deleteItem) ) {
// The string is the first item of the list. Remove it.
head = head.next;
return true;
}
else {
// The string, if it occurs at all, is somewhere beyond the
// first element of the list. Search the list.
Node runner; // A node for traversing the list.
Node previous; // Always points to the node preceding runner.
runner = head.next; // Start by looking at the SECOND list node.
previous = head;
while (runner != null && runner.item.compareTo(deleteItem) < 0) {
// Move previous and runner along the list until runner
// falls off the end or hits a list element that is
// greater than or equal to deleteItem. When this
// loop ends, runner indicates the position where
// deleteItem must be, if it is in the list.
previous = runner;
runner = runner.next;
}
if ( runner != null && runner.item.equals(deleteItem) ) {
// Runner points to the node that is to be deleted.
// Remove it by changing the pointer in the previous node.
previous.next = runner.next;
return true;
}
else {
// The item does not exist in the list.
return false;
}
}
} // end delete()