8.3. 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:

Common List Operations

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

• Print the contents of the list.

In this chapter, we will use the following Java method definitions. Note that each method corresponds to one of the operations above.

Return Type	Method / Operation Name and Parameters	Description
N/A	List()	Creates a new List object with an initial list size of zero.
String	get(int index)	Retrieves the object (String in this case) at the specified index. This method throws an IndexOutOfBoundsException if the index is out of range index < 0 || index > size
boolean	add(int index, String s)	Inserts the specified object (String in this case) at the specified index. The method shifts the object currently at that position (if any) and any subsequent objects to the right (i.e. it adds one to their indices).
String	remove(int index)	Removes and returns the string at the specified position in the list. Shifts any subsequent elements to the left (i.e. subtracts one from their indices).
void	clear()	Removes all of the objects from the list. The list will be empty after this call returns.
String	makeString (String sep)	Returns a string representation of this list with every string in the sequence separated by the specified separator string (sep).

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

Create a new list - can be either array-based or linked-based and add three 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.