By: Nicholas Duchon.

- operations:
- Insert (add, push, enqueue)
- Remove (delete, pop, dequeue)
- Find (contains)
- Iterate (new Iterator, hasNext, getNext) (for or for each loop)
- map (key-value pairs, insert, find)

- ordering
- FIFO = queue
- LIFO = stack
- other = priority queue

- performance
- O(n), O(log n), O(1) for various insert, find, and remove operations
- choice of structure depends on what is done often
- modification (insert and remove)
- searching (find)

- Linear structures
- Traversals
- requires: knowing current location to get next element in
structure

- arrays - fixed and dynamic
- ring buffer

- linked lists
- singly
- doubly
- circular singly or doubly

- sorting
- O(n
^{2}) sorts: bubble, insertion, selection - O(n log n) sorts: quick, merge, heap

- O(n
- searching
- linear O(n) - on any ordering
- binary O(log n) - on sorted structures

- Trees
- connected acyclic graph with a distinguished node called the root
- general - any number of children per node

- binary - up to two children per node (left and right)

- binary search tree - totally sorted

- operator expression evaluation tree
- heap - partially sorted binary tree with shape
property

- binary search tree - totally sorted
- types of nodes:
- root
- internal
- leaf
- parent, child, ancestor, descendant

- traversals
- requires: remembering branch points, recursion works
well here

- pre-order (node then children)
- post-order (children then node)
- in-order (binary tree, left then node then right)
- level order

- requires: remembering branch points, recursion works
well here
- balancing algorithms
- AVL
- Red-Black
- Splay

- DSW

- searching - from O(log n) to O(n)

- Graphs
- nodes
- edges or links - may be weighted and/or directed

- representation: array, linked lists, internal links from node to nodes
- traversal
- requires: marking nodes already visited since there
can be cycles

- depth first
- breadth first

- requires: marking nodes already visited since there
can be cycles
- typical questions, see http://en.wikipedia.org/wiki/Graph_theory
- shortest path between nodes
- circuits

- A given data set may have more than one structure put upon it
- A data base table may use a number of index fields - effectively creating multiple priority queues on it.

ND.