Each topic listed below corresponds to an important data structure that we have studied. For each data structure you need to know:

- What operations are typically supported by the data structure
- Algorithms for implementing these operations
- Running times of these algorithms
- Some details of Bailey's implementations of these data structures
- One or two major applications of these data structures (for example, application of queues to BFS)

I expect that all your answers will be fairly short.
Any `java` code fragment or function you write will be no longer than 10 lines
of code.
Some possibilities for a typical question on the exam are: (i) add a small new function to Bailey's implementation
of a data structure or (ii) how might you implement a small variant of one of the data
structures listed below or (iii) analyze the running time of one of Bailey's implementations.

- Linked lists
- Chapter 8, class notes, discussion section notes, Quizzes 5 and 6, and Project 2
- Singly linked lists, doubly linked lists, circularly linked lists
- Bailey's implementation of these data structures (
`SinglyLinkedList`,`DoublyLinkedList`,`CircularList`) - The running time of various operations on these data structures
- Adjacency list representation of graphs as an application of linked lists

- Queues
- Section 9.2, class notes, discussion section notes, Quiz 7, and Project 2
- Bailey's implementation of Queues using arrays, Vectors, and lists (
`QueueArray`,`QueueVector`, and`QueueList`) - The running time of various operations on the queue data structure
- Using queues to implement BFS on graphs

- Stacks
- Section 9.1, class notes, discussion section notes and Quizzes 7 and 8
- Bailey's implementation of stacks using arrays, Vectors and linked lists (
`StackArray`,`StackVector`,`StackList`) - The running time of various operations on the stack data structure
- Using stacks to implement DFS on graphs
- A recursive implementation of DFS that does not explicitly use stacks
- Using stacks to simulate recursion

- Binary heaps
- Section 12.4, class notes, discussion section notes, Quiz 9, and Project 3
- Bailey's implementation of binary heaps (
`VectorHeap`) - The running time of various operations on the heap data structure
- Heapsort
- Implementation of Dijkstra's shortest path algorithm using binary heaps

- Binary trees and binary search trees
- Sections 11.4, 11.6, 13.1, and 13.7, class notes, discussion section notes, and Quiz 10
- Bailey's implementation of binary trees (
`BinaryTree`) and binary search trees (`BinarySearchTree`) - The running time of various operations on the binary tree and binary search tree data structures
- Red-black trees, the 5 red-black tree properties, and what these properties imply about the height of a red-black tree.