# Data structures Survey - top of Musings page

By: Nicholas Duchon.

## User's View:

• operations:
• 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)

## Coding View:

• Linear structures
• Traversals
• requires: knowing current location to get next element in structure
• arrays - fixed and dynamic
• ring buffer
• singly
• doubly
• circular singly or doubly
• sorting
• O(n2) sorts: bubble, insertion, selection
• O(n log n) sorts: quick, merge, heap
• 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
• 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
• 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
• traversal
• requires: marking nodes already visited since there can be cycles
• depth first