The List ADT

This chapter names the List abstract data type: the operations DynamicArray and LinkedList already share. We use an interface to bring those two otherwise unrelated classes under one contract. Then we repeat the same pattern with a second ADT, SortedList, which we implement as a sentinel-based SortedLinkedList.

After reading this chapter, you should be able to:

• Explain why duplicated selectionSort methods for DynamicArray and LinkedList are a type-design problem, and how type substitution fixes it
• Define a List<T> interface for the operations DynamicArray and LinkedList share, implement it with implements and @Override, and sort either kind of list with one method
• Explain how an interface hides the cost of its implementation, such as get making selectionSort run in $O(n^2)$ on an array-backed list and $O(n^3)$ on a linked list
• Define an abstract data type, and distinguish the List ADT from its implementations
• Document an ADT contract with Javadoc, including the IndexOutOfBoundsException behavior for an invalid index
• Name implementations after the structures that back them (ArrayList, LinkedList), and program to the interface rather than to a specific implementation
• Explain why a sorted structure cannot implement List, and define a SortedList ADT without set that requires comparable, non-null elements
• Build a sentinel-based SortedLinkedList with add, get, indexOf, contains, and remove, and explain why binary search does not give logarithmic running time on a linked list

You can download the accompanying code for this chapter: starter and solution.

Sections

1. Run Selection Sort on LinkedList
2. The List Interface
3. Implementing a List Interface
4. Operation Costs Behind the Interface
5. Abstract Data Types
6. Documenting the Contract
7. Naming the Implementations
8. Program to the Interface
9. A Second ADT: SortedList
10. A Class to Hold a Sorted List
11. Adding in Order
12. Access and Search
13. Removing a Value