Collections - The Java Programming Language - page 911

Where AbstractList implements its iterators via the random access
method get , AbstractSequentialList implements the random access
methods via an iterator you provide by implementing the listIterator
method. You must also implement size . Your class will be modifiable in
whatever ways your list iterator's methods allow. For example, if your
iterator allows set but not add or remove , you will have a modifiable but
non-resizable list.
To use the AbstractMap class you must implement the entrySet method
to return an unmodifiable set of entries that contains the mappings of
the map. This will implement an unmodifiable map. To make a modifi-
able map, you must override put , and the iterator your entrySet object
returns must allow remove .
The abstract implementations provided in these classes are designed to
be easy to extend, but efficiency is not always a consequence. You can
often make your subclass of an abstract collection type much faster by
judicious overriding of other methods, as shown for the ArrayBunchList
iterator. As another example, the implementation of get in AbstractMap ,
having only a set of entries, must search through that set one at a time
until it finds an appropriate entry. This is an O(n) implementation. To
get its O(1) performance, HashMap overrides get and all other key-based
methods to use its own hash buckets. However, HashMap does not over-
ride the implementation of equals because that requires iteration any-
way and the implementation in AbstractMap is reasonably efficient.
Exercise 21.5 : Implement a more efficient ListIterator for Ar-
rayBunchList . Be careful of the specific contracts of ListIterator methods,
such as set not being valid until either next or previous is invoked.