Principle 16.3.1. EFFECTIVE DESIGN: Generalizing a Type.
An effective strategy for designing a list abstract data type is to start with a specific list and generalize it. The result should be a more abstract version of the original list.
PhoneListexample from the previous section illustrates the basic concepts of the linked list. Keep in mind that there are other implementations that could have been described. For example, some linked lists use a reference to both the first and last elements of the list. Some lists use nodes that have two pointers, one to the next node and one to the previous node. This enables traversals in two directions—front to back and back to front—as well as making it easier to remove nodes from the list. The example we showed was intended mainly to illustrate the basic techniques involved in list processing.
PhoneListexample is limited to a particular type of data—namely, a
PhoneListNode. Let’s develop a more general linked list class and a more general node class that can be used to store and process lists of any kind of data.
intis an ADT. The data are the integers ranging from some
MAXINT. The operations are the various integer operations: addition, subtraction, multiplication, and division. These operations prescribe the ways that
ints can be used. There are no other ways to manipulate integers.
ints, but we have no real idea how they are implemented—that is, what exact algorithm they use.
privateparts of an object—its instance variables and private methods—are hidden from the user while the object’s interface—its
publicmethods—are available. As with the integer operators, the object’s public methods prescribe just how the object can be used.
PhoneListexample. Thus, the
PhoneListNodewill become a generic
Nodethat can store any kind of data (Figure 16.3.2). Some of the changes are merely name changes. Thus, wherever we had
PhoneListNode, we now have just
Node. The link access methods have not changed significantly. What has changed is that instead of instance variables for the name, phone number, and so on, we now have just a single data reference to an
Object. This is as general as you can get, because, as we pointed out earlier,
datacan refer to any object, even to primitive data.
Nodeclass is shown in Listing 16.3.3. Note that the data access methods,
setData(), use references to
Objectfor their parameter and return type. Note also how we’ve defined the
toString()method. It just invokes
toString()is defined in
Object, every type of data will have this method. And because
toString()is frequently overridden in defining new objects, it is useful here.
Listclass (Figure 16.3.4) will still contain a reference to the
headof the list, which will now be a list of
Nodes. It will still define its constructor, its
isEmpty()method, and its
print()method in the same way as in the
Listclass, we want to design some new methods, particularly because we want to use this class as the basis for more specialized lists. The
PhoneList.insert()method was used to insert nodes at the end of a list. In addition to this method, let’s design a method that inserts at the head of the list. Also,
PhoneListhad a method to remove nodes by name. However, now that we have generalized our data, we don’t know if the list’s
Objects have a name field, so we’ll scrap this method in favor of two new methods that remove a node from the beginning or end of the list, respectively.
insertAtRear()method, which otherwise is very similar to the
PhoneList.insert()method. The key change is that now its parameter must be an
Object, because we want to be able to insert any kind of object into our list. At the same time, our list consists of
Nodes, so we have to use the
Objectto create a
Nodein our insert methods:
head = new Node(obj);
Nodeconstructor takes an
Objectargument and simply assigns it to the
datareference. So when we insert an
Objectinto the list, we make a new
Nodeand set its
datavariable to point to that
Object. Note that we check whether the list is empty before traversing to the last node.
insertAtFront()method (Listing 16.3.5) is simple to implement, since no traversal of the list is necessary. You just need to create a new
Objectas its data element and then link the new node into the head of the list:
Node newnode = new Node(obj); newnode.setNext(head); head = newnode;
removeFirst()method is also quite simple to implement. In this case, you want to return a reference to the
Objectthat’s stored in the first node, but you need to adjust
headso that it points to whatever the previous
head.nextwas pointing to before the removal. This requires the use of a temporary variable, as shown in the method.
removeLast()method is a bit more complicated. It handles three cases: (1) The empty list case, (2) the single node list, and (3) all other lists. If the list is empty, it returns
null. Obviously, it shouldn’t even be called in this case. In designing subclasses of
Listwe will first invoke
isEmpty()before attempting to remove a node.
null, thus resulting in an empty list. In the typical case, case 3, we traverse the list to find the last node, again using the strategy of maintaining both a
currentpointer. When we find the last node, we must adjust
previous.nextso that it no longer points to it.
PhoneListexample. However, one of the things we want to test is that we can indeed create lists of heterogeneous types—lists that include
Integers mixed with
Floats, mixed with other types of objects. The
[cross-reference to target(s) "fig-testlistadt" missing or not unique]illustrates this feature.
ListADT is that it lets you avoid having to write the relatively difficult list-processing algorithms each time you need a list structure.
PhoneRecordclass is a scaled-down version of the
PhoneListNodewe used in the previous example (Figure 16.3.8). Its definition is shown in Listing 16.3.9. Note how we use an
Objectreference to remove objects from the list in
main(). We use the
Object.toString()method to display the object that was removed.
ListADT is given here. as well as the implementation of
PhoneRecord. Experiment with it to see how it works. Then add a new node to the list with your name and number. Print the list. Then remove your entry and print again.
Listthat shows that new elements can be inserted into a list after all of its previous nodes have been removed.