> ### 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.

> Sorry, but your browser
> doesn't support Java.

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

[ Next Section | Previous Section | Chapter Index | Main Index ]