Type Substitution

ArrayList<T> and LinkedList<T> both declare implements List<T>, where List<T> is an interface with add, remove, set, get, contains, indexOf, and size. The method selectionSort(List<T> list) sorts a list using only size, get, and set.

Solution

Both classes implement List, so each is a subtype of List, and a subtype can be used anywhere its supertype is expected. This is type substitution.

Solution

Java looks at the instantiated type of the object at the moment of the call and runs that class’s get. This is dynamic dispatch.