The List ADT

ArrayList (backed by an array) and LinkedList (backed by linked nodes) both implement this contract:

public interface List<T> {
  void add(T element);
  boolean remove(T element);
  void set(int index, T element);
  T get(int index);
  boolean contains(T element);
  int indexOf(T element);
  int size();
}

Solution

An abstract data type is a contract: a set of operations and the rules they obey, described without saying how the data is stored. List is the ADT: it says a list can add, get, set, remove, contains, indexOf, and size, and what each should do. ArrayList and LinkedList are two implementations of that ADT: each stores the elements differently, in an array or in linked nodes, and each supplies its own working code for every operation.

Solution

No. The interface guarantees the same behavior, but nothing about cost. ArrayList.get(i) reads the backing array directly, $O (1)$ . LinkedList.get(i) follows links from the head, $O (i)$ , so $O (n)$ in the worst case. With about $n \times n$ get calls, selectionSort is $O (n^{2})$ on ArrayList and $O (n^{3})$ on LinkedList. The cost comes from the implementation, not the interface.

Solution

/**
 * Return the element stored at the given index.
 *
 * @param index the position to read from.
 * @return the element at that position.
 * @throws IndexOutOfBoundsException if index < 0 or index >= size().
 */
T get(int index);

Solution

List<Integer>. The method then depends only on the List contract, so it works with any implementation. It cannot depend on the details of one particular implementation.