8.4. The List Interface (ADT)

A common ADT is the List interface. When thinking of a List as an abstract type, you can think of a List as an ordered collection of objects (no need to think specifically about the underlying data structure when discussing the ADT). There are several important operations (abstract methods) needed for a List. Some common list operations include, but are not limited to:

8.4.1. Common List Operations

Here is a list of common operations for a list:

• Create a new list.

• Retrieve an object in the list at a particular index.

• Add an object to the list at a particular index.

• Remove an object from the list at a particular index.

• Clear the list.

• Count the elements in the list.

• Produce a string representation of the list's contents.

In this chapter, we use a custom List interface for strings, distinct from java.util.List. The UML diagram below summarizes its six public abstract methods; the table describes their behavior.

Fig. 8.4 The six public abstract methods of this chapter's List interface. [svg] [png]

Return Type	Method / Operation Name and Parameters	Description
String	get(int index)	Returns with the reference value stored at the specified index. Throws IndexOutOfBoundsException if index < 0 or index >= size().
boolean	add(int index, String s)	Inserts the reference value stored in s at the specified index. Shifts the reference values at that index and later indices one position to the right.
String	remove(int index)	Removes the reference value at the specified index and returns with that value. Shifts subsequent reference values one position to the left.
void	clear()	Removes all elements from the list. On normal completion, the method returns without a value and the list is empty.
int	size()	Returns with the number of elements in the list.
String	makeString(String sep)	Returns with a reference to a String object representing the list, with the specified separator between element representations.

Creating a list is the responsibility of an implementing class, such as ArrayBasedList or LinkedBasedList. Their no-argument constructors create empty lists. The List interface itself does not declare a constructor.

8.4.2. What does the ADT not describe?

It doesn't describe how the operations work internally (the code in the methods). One list implementation might use an array to store the items in the list, while another list implementation might use a linked list to do the same. That is, different implementing classes are responsible for the inner workings of their implementations so long as the list operations work as previously described. The complete ADT will also describe what should happen under exceptional circumstances.

Test Yourself

In the example below, we provide a few List ADT method calls. It is worth highlighting again that we can understand this code without knowing any details of the underlying implementation. Using the table above where needed, trace through the code below and write the output you would expect to see after the last three println statements execute.

We recommend writing the list out as you would a regular shopping list. You don't need to draw it as an array or a linked list. Just keep up with the items in the list and make sure they are in the right index (line).

Listing 8.3 Create an array-based or linked-based list and add four items to it.

List myList = new ArrayBasedList(); // or LinkedBasedList()
myList.add(0, "Bread");
myList.add(0, "Cheese");
myList.add(1, "Milk");
myList.add(3, "Ice Cream");
System.out.println("Removed: " + myList.remove(0));
System.out.println("List Size: " + myList.size());
System.out.println("List Contents: " + myList.makeString(","));

Test Yourself Solution (Open after attempting the question above)

Program Output:

Removed: Cheese
List Size: 3
List Contents: Milk, Bread, Ice Cream

Rapid Fire Review

1. What is a key feature of the List interface (ADT)?

   1. It defines the internal storage method for a list.

   2. It describes operations for an ordered collection of objects.

   3. It defines how exceptions should be handled internally.

   4. It guarantees that lists use arrays for storage.

2. Which of the following methods retrieves an object from a list at a specific index?

   1. get(int index)

   2. add(int index, String s)

   3. remove(int index)

   4. makeString(String sep)

3. What happens when the add(int index, String s) method is called on a List?

   1. The specified object is inserted at the end of the list regardless of the index.

   2. The object at the specified index is replaced by the new object.

   3. The object is inserted at the specified index, and subsequent objects are shifted to the right.

   4. The list is cleared, and the specified object is added at the specified index.

4. What is the output of the code below:

   List myList = new LinkedBasedList();
   myList.add(0, "Bread");
   myList.add(0, "Cheese");
   myList.add(2, "Candy");
   myList.add(2, "Milk");
   myList.remove(2);
   System.out.println("The item at index 2 is: " + myList.get(2));
   System.out.print(" List Size: " + myList.size());
   System.out.print(" List Contents: " + myList.makeString(", "));
   

   1. The item at index 2 is: Candy List Size: 3 List Contents: Cheese, Bread, Candy

   2. The item at index 2 is: Milk List Size: 3 List Contents: Cheese, Bread, Milk

   3. The item at index 2 is: Candy List Size: 2 List Contents: Bread, Cheese

   4. The item at index 2 is: Cheese List Size: 2 List Contents: Cheese, Bread

5. What is the difference between the List interface and its implementing classes?

   1. The List interface defines how the data is stored, while implementing classes provide methods for list operations.

   2. The List interface describes the methods for list operations, while implementing classes define the internal structure of how the data is stored.

   3. The List interface requires the use of arrays, while implementing classes can use different data structures.

   4. There is no difference between the List interface and its implementing classes.