Summary of Elementary Data Structures -
By: Nicholas Duchon.
This seems like a good place to present a summary of the
elementary data structures:
- Protocols:
- stack (LIFO)
- reverse Polish notation evaluation
- walking trees and graphs
- queue (FIFO)
- binary search tree (BST)
- priority queue
- Structures:
- graph
- trees
- binary tree
- binary search tree
- heap tree
- linked list
- array
- circular queue
- key-value
- map
- dictionary
- hash table
- Searching
- Sorting - slow
- bubble
- insertion
- selection
- Sorting - fast
Most commons classes:
- ArrayList
- HashMap
- Collections (for sorting)
- Interface: Comparable
- one method:
compareTo (T)
- Arrays.sort (Object []) - natural
ordering, static method
- Interface: Comparator
- two required methods (lots of defaults):
equals (Object) - actually
already provided in Object class
compare (T, T)
- ???? API says "can be used with lamda expressions, implement
compare method", but I think this is backwards, Comparable is
the lambda expression class.
- Arrays.sort (Object [], Comparator)
- ArrayList.sort (Comparator) - sort is an instance method
here
- Collections.sort (List, Comparator) - static method
ND.