Review of Course Content

Data Structures, Performance, Pros and Cons

• Lists
  • Basic Lists

  • Stacks

  • Queues

  • Optimizations to support traversals

  • Doubly linked lists

• Trees
  • Binary Trees

  • Ordered Trees

  • Complete Binary Trees

• Arrays and Strings
  • Multi-D arrays

  • Contiguous representations of arrays

  • Sparse arrays

  • Strings

• List and Tree Implementations of Sets
  • Unordered lists

  • Ordered Lists

  • Skip lists

  • Binary Search Trees

  • Static Binary Search Trees

• Tree Structures for Dynamic Dictionaries
  • AVL Trees

  • 2-3 Trees

  • B-Trees

  • Splay Trees

• Sets of Digital Data
  • Bit Vectors

  • Tries

  • Digital Search Trees

  • Hashing
    • Chaining

    • Open Addressing

    • Extendible

  • Sets with Special Operations
    • Priority Queues
      • Balanced Trees

      • Heaps

    • Disjoint Sets with Union
      • Up-Trees