|
Collection
|
Underneath
|
Good For?
|
|
ArrayList
|
Under the ArrayList we have an array of Objects - Inserting at end O(1), inserting in front O(n) - because we have to shift
|
Good when we need to jump around in the array. Also if sorted - Binary Search (O (log n)).
|
|
PriorityQueue
|
We have an array which is kept in a heap. Removing takes O(1) and then O(log n) to reheap (reheap down). Adding to a takes O(log n) for reheaping (reheap up).
|
Good when you are taking out the min or max value (quick to add and remove)
|
|
LinkedList
|
Doubly linked list with head and tail links. Will start at closest end when we search for kth element (so worse case always O(n/2) for get(n)
|
Good when we add to end or front. Good for inserting and deleting on ends (O(1)). Bad for searching through the list (O(n)) or getting an element.
|
|
Stack
|
Array of Objects
|
Good for working with one end. O(1) inserting and deleting. Works with far side of array. When it pops one it just changes the Count for the top (actually, physically leaves name in the array). There is an overhead in that array must be copied to new array that is formed when first one fills, but it is done very seldom. The gain in not having to create new memory every time with ListNode or LinkedList makes it worth it. |
|
HashMap
|
Array of pointers to LinkedList - placed by hashing key. Array started at size 16 and then went to 32. Items were rehashed over new space. Collisions are resolved by chaining. Array was doubled on 13th entry. Some items do hash to same spot. |
O(1) for placing, O(1) for retrieving (although it can be O(n) for worst case depending on resolution of collisions). Good for searching and retrieving. Lose order of placement. Not good for printing in order. |
|
TreeMap
|
A balanced tree - with left, right and parent pointers.
|
O(log n) for placing and searching. Slower than HashMap for searching and placing but the tree is ordered (by Comparable). Can print tree in order using the Iterator or for-each loop.
|
|
TreeSet
|
A tree - with left, right and parent pointers.
|
O(log n) for placing and searching. Slower than HashMap for searching and placing but the tree is ordered (by Comparable). Can print tree in order with iterator.
|
|
HashSet
|
An array - placement by hashing (actually uses the HashMap - just doesn't use the Object field)
|
O(1) for checking and placing. Items are returned in arbitrary order when we iterate through them (size is largest size the set has ever been).
|
