[h2]General data structure types and interfaces[h2]
- Collection General bag of stuff. Lets you add, remove and iterate when you don’t really care what the underlying structure is.
- List Ordered list of stuff. Use when you want objects kept in order, but you don’t care what the underlying structure is.
- Set. A collection that does not allow duplicates. Use when having the same object twice in your collection is an error.
- Map. Map of key-value pairs. Use when you want fast lookups from some kind of identifying key to another object.
[h2]Lists & queues[/h2]
- ArrayList Growable list, implemented with an array that is resized under the hood.
- LinkedList Doubly linked list. Faster insertion and removal than an ArrayList, but slower to iterate over.
- PriorityQueue Ordered list where objects are sorted by a priority value.
- Unrolled linked list
[h2]Lookup tables[/h2]
[h2]Ordered collections[/h2]
- TreeSet (node based, binary tree)
- PriorityQueue (array based, binary heap)
[h2]Thread-safe collections[/h2]
Most containers can be wrapped to create thread safe versions using the methods in Collections. Eg. Collections.synchronizedList(new ArrayList()) More specialised containers can be found in java.util.concurrent.
- ConcurrentHashMap. Map with non-blocking get(), useful for caches which may be populated from a loader thread.
- ConcurrentLinkedQueue. Non-blocking queue, useful for multithreaded pipelines where producers and consumers may share a common queue.
[h2]General Advice[/h2]
[li]Always declare using the most general type you need. This isn’t so important for locals, but it makes a huge difference for fields, as this allows you to swap the implementation of a datastructure without breaking code, that may otherwise already have dependencies on the explicitly defined implementation. For example:
// Don't do this!
ArrayList<Foo> foos = new ArrayList<Foo>();
HashMap<Foo,Bar> foobar = new HashMap<Foo,Bar>();
// Do this instead
List<Foo> foos = new ArrayList<Foo>();
Map<Foo,Bar> foobar = new HashMap<Foo,Bar>();
[h2]References[h2]
- Interactive applet. Visualization tool that walks through the steps of: BST, AVL, B-tree, AA Tree, Red Black, Skiplist, Max & Min Heap, Treap, Scapegoat and Splay.
