This page lists several basic data types, data structures, and algorithms that are typically covered in CS 225, with pointers to the corresponding Wikipedia entries. (For more focused descriptions, you may prefer to consult your data structures textbook or notes; The Wikipedia Cloud occasionally makes some very strange choices.) We assume you are already familiar with all of them. You can use any of these in your homework or exam solutions without providing further details or citing any source. If you need to modify one of these objects, just describe your changes; don't describe your solution from scratch.Data types
- scalars (booleans, characters, integers, reals, etc.)
- records
- pointers / references
- strings
- arrays / vectors (indexed sequences)
- stacks (LIFO lists)
- queues (FIFO lists)
- deques (double-ended queues)
- priority queues
- dictionaries
- graphs (directed and undirected)
Data structures
- binary numbers, including 2's complement representation of negative integers
- arrays
- linked lists (single and double, linear and circular)
- hash tables
- binary trees: worst-case depth is O(n)
- binary heaps
- binary search trees
- balanced search trees: worst-case depth is O(log n)
- At least one of the following: B-trees (such as 2-3-trees or (a,b)-trees), AVL trees, red-black trees, skip lists
- adjacency matrices
- adjacency lists
- The difference between this list and the previous list
Algorithms
- elementary arithmetic á la Al-Kwarizmi
- sequential search
- binary search
- comparison-based sorting:
- insertion sort, selection sort, (standard) quicksort: worst-case time is O(n²)
- mergesort, heapsort: worst-case time is O(n log n)
- radix sort
- binary tree traversal: pre-order, post-order, in-order, level-order
- depth-first search
- breadth-first search
- topological sorting