We have to use different kind of data structures and algorithms in our code. Luckily for us, Java provide Java Collection Framework (JCF) for that purpose.
Prior to Java 1.2 Java had only few data structures like Vector, Stack, Hashtable, Enumeration.
Java 2 introduced proper collection API to address all data structures issues.
- Easy to use collections.
- High performance.
- Easy to extend.
There is no "one for all" implementation.
- Iterable - provide iteration through a collection. (this is outside of the api)
- Collection - main interface for the most of the collections. contains most of the core functionalities.
- Set - can not have duplicate. contains unique elements. doesn't maintain the insertion order.
- List - maintain the order. can have duplicates.
- Queue - define first in first out data structure.
- Map - key, value pairs.
In Collection API, interfaces provide the necessary contract but it doesn't give us an idea about real algorithm used. Multiple implementations have multiple purposes, hence we need to check the implemented class also to get the real idea.
How do they implemented?
- Array - arrays maintain adjacent positions and implemented directly in hardware. Because it maintains the position removal and insertion at given position is slow. Read at a given point, iteration is fast. (ArrayList, CopyOnWriteArrayList, EnumSet, EnumMap)
- Linked list - maintain a link to next item (and to previous item). Reading in middle is slow due to this. But insertion and removal is fast. (LinkedList)
- Hashtable - index by content. no support to access by position. (Set, Map)
- Trees - organize by content but can store and retrieve in sorted order. (TreeSet, TreeMap)