Selecting the Best Java Collection Class for Your Application, Page 2
How Collections Organize Objects
Table 2 shows the objects' supported organizations and which classes support each organization. Notice that some of the Collection classes appear multiple times in the table. This is because some classes can support more than one organization.
Descriptions of the organizations follow Table 2.
Lists are collections whose contents have an explicit position within the collection. The position of each object in a List may be determined by the order in which objects are added. Collection classes that organize objects into lists implement the List interface.
If you have decided that a list is the organization that you need, here are suggestions regarding which class to use:
- Vector: Vector is the oldest List class. It suffers from some inconsistencies with other List classes. All of its methods are synchronized, which can introduce unneeded overhead. Generally, you should not use the Vector class in new code; use ArrayList instead.
- ArrayList: The ArrayList class is the most widely used List class. Most of the ArrayList class's operations are fast and the time they take is independent of how many objects are in the list. These fast operations include adding an object to and removing an object from the end of the list. Other fast operations are getting the size of the list, getting the object at a specified position in the list, and setting the object at a specified position in the list.
Other operations take time proportional to the number of objects in the list.
- LinkedList: The LinkedList class takes more time to perform most operations than the ArrayList class. The exception is that the LinkedList class can quickly add objects to the middle of a list or quickly remove objects from the middle of a list in constant time. The time that the ArrayList class takes to perform these operations is proportionate to the number of objects in the list after the position to which objects were being added or from which they were being removed. Unless you are going to perform a lot of these operations, the ArrayList class is usually the better choice.
The LinkedList class is also useful for organizing queues, deques (double-ended queues), and stacks. In the rare situations where you need this flexibility, LinkedList may be a good choice.
- CopyOnWriteArrayList: The CopyOnWriteArrayList class is used to solve a specific concurrency problem without having to resort to locks. To ensure that an iterator sees a consistent view of an ArrayList object when it is iterating over the object, the contents of the ArrayList object must not change. If they do, then the next time the iterator's next or previous method is called, the method will throw a ConcurrentModificationException exception.
To avoid this situation, you could create a lock to prevent methods that would modify the ArrayList object from being called while an iterator is active. If you rarely iterate an ArrayList object while it is being modified, then using a lock is a good solution. However, if iterating over a ArrayList object is common, then solving the problem with a lock can create another problem: the amount of time threads spend waiting to modify the ArrayList object may be unacceptably high.
The CopyOnWriteArrayList class is functionally similar to the ArrayList class, with one important difference. All operations that change the contents of a CopyOnWriteArrayList collection cause the underlying array to be replaced with a copy of itself before the contents of the array are changed. Any active iterators will continue to see the unmodified array, so there is no need for locks.
Iterators created by a CopyOnWriteArrayList object cannot change the underlying array. Though these iterators do have methods for changing the underlying collection, their implementations throw an UnsupportedOperationException instead of modifying the underlying collection.