OBJECT-ORIENTED DESIGN: The List Abstract Data Type (ADT)

Section 16.3 OBJECT-ORIENTED DESIGN: The List Abstract Data Type (ADT)

The PhoneList example 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.

Also, the PhoneList example 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.

Subsection 16.3.1 Abstract Data Type

An Abstract Data Type (ADT) involves two components: the data that are being stored and manipulated and the methods and operations that can be performed on those data. For example, an int is an ADT. The data are the integers ranging from some MININT to 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.

Moreover, in designing an ADT, it’s important to hide the implementation of the operations from the users of the operations. Thus, our programs have used all of these integer operations on ints, but we have no real idea how they are implemented—that is, what exact algorithm they use.

Objects can be designed as ADTs, because we can easily distinguish an object’s use from its implementation. Thus, the private parts of an object—its instance variables and private methods—are hidden from the user while the object’s interface—its public methods—are available. As with the integer operators, the object’s public methods prescribe just how the object can be used.

So let’s design a list ADT. We want it to be able to store any kind of data, and we want to prescribe the operations that can be performed on those data—the insert, delete, and so on. Also, we want to design the ADT so that it can be extended to create more specialized kinds of lists.

Subsection 16.3.2 The `Node` Class

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.

Our approach will be to generalize the classes we created in the PhoneList example. Thus, the PhoneListNode will become a generic Node that 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, data can refer to any object, even to primitive data.

Figure 16.3.2. The `Node` class is a generalization of the `PhoneListNode` class.

The implementation of the Node class is shown in Listing 16.3.3. Note that the data access methods, getData() and setData(), use references to Object for their parameter and return type. Note also how we’ve defined the toString() method. It just invokes data.toString(). Because 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.

public class Node {
   private Object data;        // Stores any kind of data
   private Node next;
   public Node(Object obj) {  // Constructor
      data = obj;
      next = null;
   }                               // Data access methods
   public void setData(Object obj) {
      data = obj;
   }
   public Object getData() {
      return data;
   }
   public String toString() {
      return data.toString();
   }                               // Link access methods
   public void setNext( Node nextPtr ) {
      next = nextPtr;
   }
   public Node getNext() {
      return next;
   }
} // Node

Listing 16.3.3. The Node class is a more abstract version of the PhoneListNode class.

Subsection 16.3.3 The `List`Class

Let’s now generalize the PhoneList class. The List class (Figure 16.3.4) will still contain a reference to the head of 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 PhoneList.

Figure 16.3.4. The `List` class contains a pointer to the head of the list and public methods to insert and remove objects from both the front and rear of the list.

However, in designing a generic List class, 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, PhoneList had 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.

public class List {
  private Node head;

  public List() { head = null; }
  
  public boolean isEmpty() { return head == null; }
  
  public void print() {
    if (isEmpty())
      System.out.println("List is empty");
    Node current = head;
    while (current != null) {
      System.out.println(current.toString());
      current = current.getNext();
    }
  } // print()
  
  public void insertAtFront(Object obj) {
    Node newnode =  new Node(obj);
    newnode.setNext(head);
    head = newnode;
  }
  
  public void insertAtRear(Object obj) {
    if (isEmpty())
      head = new Node(obj);
    else {
      Node current = head;              // Start at head of list
      while (current.getNext() != null) // Find the end of the list
        current = current.getNext();
      current.setNext(new Node(obj));  // Create and insert newNode
      }
  } // insertAtRear()
  
  public Object removeFirst() {
    if (isEmpty())              // Empty List
       return null;
    Node first = head;
    head = head.getNext();
    return first.getData();
  } // removeFirst()
  
  public Object removeLast() {
    if (isEmpty())  // empty list
       return null;
    Node current = head;
    if (current.getNext() == null) {// Singleton list
       head = null;
       return current.getData();
    }
    Node previous = null;           // All other cases
    while (current.getNext() != null) {
      previous = current;
      current = current.getNext();
    }
    previous.setNext(null);
    return current.getData();
  } // removeLast()

} // List

Listing 16.3.5. The List ADT.

We already know the basic strategies for implementing these new methods, which are shown in the definition in Listing 16.3.5. We have renamed the 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 Object to create a Node in our insert methods:

head = new Node(obj);

Recall that the Node constructor takes an Object argument and simply assigns it to the data reference. So when we insert an Object into the list, we make a new Node and set its data variable to point to that Object. Note that we check whether the list is empty before traversing to the last node.

The new 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 Node with the Object as 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;

See Figure 16.2.13a for a graphical representation of this type of insertion.

The new removeFirst() method is also quite simple to implement. In this case, you want to return a reference to the Object that’s stored in the first node, but you need to adjust head so that it points to whatever the previous head.next was pointing to before the removal. This requires the use of a temporary variable, as shown in the method.

The new 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 List we will first invoke isEmpty() before attempting to remove a node.

If the list contains a single node, we treat it as a special case and set head to 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 previous and a current pointer. When we find the last node, we must adjust previous.next so that it no longer points to it.

Subsection 16.3.4 Testing the List ADT

Testing the list ADT follows the same strategy used in the PhoneList example. 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 main() method in [cross-reference to target(s) "fig-testlistadt" missing or not unique] illustrates this feature.

public static void main( String argv[] ) {
         // Create list and insert heterogeneous nodes
  List list = new List();
  list.insertAtFront(new PhoneRecord("Roger M", "997-0020"));
  list.insertAtFront(new Integer(8647));
  list.insertAtFront(new String("Hello, World!"));
  list.insertAtRear(new PhoneRecord("Jane M", "997-2101"));
  list.insertAtRear(new PhoneRecord("Stacy K", "997-2517"));
         // Print the list
  System.out.println("Generic List");
  list.print();
         // Remove objects and print resulting list
  Object o;
  o = list.removeLast();
  System.out.println(" Removed " + o.toString());
  System.out.println("Generic List:");
  list.print();
  o = list.removeLast();
  System.out.println(" Removed " + o.toString());
  System.out.println("Generic List:");
  list.print();
  o = list.removeFirst();
  System.out.println(" Removed " +o.toString());
  System.out.println("Generic List:");
  list.print();
} // main()

Listing 16.3.6. A series of tests for the ListADT.

Principle 16.3.7. EFFECTIVE DESIGN: The `List`ADT.

One advantage of defining a ListADT is that it lets you avoid having to write the relatively difficult list-processing algorithms each time you need a list structure.

The list we create here involves various types of data. The PhoneRecord class is a scaled-down version of the PhoneListNode we used in the previous example (Figure 16.3.8). Its definition is shown in Listing 16.3.9. Note how we use an Object reference to remove objects from the list in main(). We use the Object.toString() method to display the object that was removed.

Figure 16.3.8. The `PhoneRecord` class stores data for a phone directory.

public class PhoneRecord {
     private String name;
     private String phone;
     public PhoneRecord(String s1, String s2) {
         name = s1;
         phone = s2;
     }
     public String toString() {
         return name + " " + phone;
     }
     public String getName( ) {
         return name;
     }
     public String getPhone( ) {
         return phone;
     }
} // PhoneRecord

Listing 16.3.9. A PhoneRecord class.

Exercises Self-Study Exercises

1. PhoneRecord Test.

The complete implementation of the List ADT 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.

public class List {
    private Node head;

public List() {
        head = null;
    }

public boolean isEmpty() {
        return head == null;
    }

public void print() {
        if (isEmpty())
            System.out.println("List is empty");
        Node current = head;
        while (current != null) {
            System.out.println(current.toString());
            current = current.getNext();
        }
    } // print()

public void insertAtFront(Object obj) {
        Node newnode = new Node(obj);
        newnode.setNext(head);
        head = newnode;
    }

public void insertAtRear(Object obj) {
        if (isEmpty())
            head = new Node(obj);
        else {
            Node current = head; // Start at head of list
            while (current.getNext() != null) // Find the end of the list
                current = current.getNext();
            current.setNext(new Node(obj)); // Create and insert newNode
        }
    } // insertAtRear()

public static void main(String argv[]) {
        // Create list and insert heterogeneous nodes
        List list = new List();
        list.insertAtFront(new PhoneRecord("Roger M", "997-0020"));
        list.insertAtFront(Integer.valueOf(8647));
        list.insertAtFront(new String("Hello, World!"));
        list.insertAtRear(new PhoneRecord("Jane M", "997-2101"));
        list.insertAtRear(new PhoneRecord("Stacy K", "997-2517"));
        // Print the list
        System.out.println("Generic List");
        list.print();
        // Remove objects and print resulting list
        Object o;
        o = list.removeLast();
        System.out.println(" Removed " + o.toString());
        System.out.println("Generic List:");
        list.print();
        o = list.removeLast();
        System.out.println(" Removed " + o.toString());
        System.out.println("Generic List:");
        list.print();
        o = list.removeFirst();
        System.out.println(" Removed " + o.toString());
        System.out.println("Generic List:");
        list.print();
    } // main()

public Object removeFirst() {
        if (isEmpty()) // Empty List
            return null;
        Node first = head;
        head = head.getNext();
        return first.getData();
    } // removeFirst()

public Object removeLast() {
        if (isEmpty()) // empty list
            return null;
        Node current = head;
        if (current.getNext() == null) {// Singleton list
            head = null;
            return current.getData();
        }
        Node previous = null; // All other cases
        while (current.getNext() != null) {
            previous = current;
            current = current.getNext();
        }
        previous.setNext(null);
        return current.getData();
    } // removeLast()

} // List

class Node {
    private Object data; // Stores any kind of data
    private Node next;

public Node(Object obj) { // Constructor
        data = obj;
        next = null;
    } // Data access methods

public void setData(Object obj) {
        data = obj;
    }

public Object getData() {
        return data;
    }

public String toString() {
        return data.toString();
    } // Link access methods

public void setNext(Node nextPtr) {
        next = nextPtr;
    }

public Node getNext() {
        return next;
    }
} // Node

class PhoneRecord {
    private String name;
    private String phone;

public PhoneRecord(String s1, String s2) {
        name = s1;
        phone = s2;
    }

public String toString() {
        return name + " " + phone;
    }

public String getName() {
        return name;
    }

public String getPhone() {
        return phone;
    }
} // PhoneRecord

2. PhoneRecord Test, Part 2.

Using the code on the previous exercise, design and implement a test of List that shows that new elements can be inserted into a list after all of its previous nodes have been removed.

You have attempted of activities on this page.

Prev Top Next