each element to get to the next. A linked list is a sequential access data store. By contrast, an array can be
randomly accessed directly. This is why ArrayList extends AbstractList, while LinkedList
extends AbstractSequentialList.
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
modifiable 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 override the implementation of equals because that requires iteration anyway and the
implementation in AbstractMap is reasonably efficient.
Exercise 21.5: Implement a more efficient ListIterator for ArrayBunchList. Be careful of the
specific contracts of ListIterator methods, such as set not being valid until either next or previous
is invoked.
21.15. The Legacy Collection Types
The collection frameworkthe interfaces and classes described in this chapter, and shown in Figure 21-1 on
page 568has not always been a part of the package java.util, but that package has always contained some
other collections. Most are superseded by the new collection types. Even so, they are not deprecated because
they are in widespread use in existing code and will continue to be used until programs shift over to the new
types. You are therefore likely to encounter these legacy collections so you should learn about them, including
their relationship to the newer collection types. The legacy collections consist of the following types:
- Enumeration Analogous to Iterator.
Vector Analogous to ArrayList, maintains an ordered list of elements that are stored in an
underlying array.
•
Stack A subclass of Vector that adds methods to push and pop elements so that you can treat the
vector by using the terms normal to a stack.•
Dictionary Analogous to the Map interface, although Dictionary is an abstract class, not an
interface.[4][4]Dictionary is not an interface because it predates the addition of interfaces to
the language, which gives you some idea of how old these legacy collections are.•
- Hashtable Analogous to HashMap.
Properties A subclass of Hashtable. Maintains a map of key/value pairs where the keys and
values are strings. If a key is not found in a properties object a "default" properties object can be
searched.