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()
