Recitation 21a: Exam 2 Review

Material from Recitation:

• [Data Structure Runtimes] A cleaned up version of the one we filled in together.

The above chart summarizes the runtimes of the primary data structures we've used so far. It's kind of hard to draw direct comparisons between each, since it means a different thing depending on the data structure. For example, with linked lists and UBAs, it makes sense to differentiate insertion based on where we insert, but this doesn't make sense for hash tables. Similarly, not all operations are valid in all cases. For example, we don't insert into the middle of a queue--that's not part of the interface. If you were asked to choose a data structure for some task, consider the operations that would be performed most frequently and then what data structure closely aligns with that, in terms of fast runtimes. Moral of the story: there is no universal data structure.

We spent the rest of the time working through some of the sample exams. See the main course website for the exams and solutions.

If you have any comments or see any errors, please let me know.