CS 61B: Data Structures
Welcome to my CS61B Guide! #
This is a non-comprehensive guide to data structures written with an intention to supplement learning and reviewing of Berkeleyās CS61B material. Main topics include:
- Object oriented programming basics
- Abstract data types
- Asymptotics and runtime analysis
- Sorting algorithms
- Search algorithms
- And some more miscellaneous topics thrown in!
This guide is written to be as easy to follow and digestible as possiblešIāve included lots of diagrams, practice problems, and more intuitive explanations instead of the more straightforward approach most textbooks use. This isnāt a replacement for lectures and other course content. You probably need to look at those first, and come here if something isnāt sticking!
The 61B Concept Map #
Who is this for? #
Mostly me; making unnecessarily detailed guides is my goto method of making sure I understand everythingš But you are welcome to use it as well for reviewing for 61B exams, touching up on data structures knowledge, or whatever you want!
Basic programming knowledge gained from CS61A or equivalent is assumed. Click here for my notes for that!
How to use this guide #
Again, I will emphasize that this isnāt a textbook. While I try to be as comprehensive as possible, Iām sure I missed plenty of important concepts or assume you know others. Please open an issue if you think somethingās wrong!
This content was ported from my original 61B Notes, so you may see some strange formatting here and there. Again, please create an issue if you spot anything overly egregious.
Content Note
For more difficult topics, Iāll put a warning like this at the top of the page with links to prerequisites or supporting topics!
There are also plenty of practice problems to try out! Hereās an non-exhaustive list of pages with those if you are mostly interested in them and not the conceptual content.
- Access Control
What is Access Control? In Java, we can specify the level of access certain variables and methods have. With this power,...
- Dynamic Method Selection
Dynamic Method Selection Content Note > This is a very tricky topic. Make sure you are comfortable with inheritance and access controlbefore...
- Generic Types
Generic Types
Sometimes, we want things to support any type, including user defined types that we don't know about! For example, it...
- Asymptotics Practice
Asymptotics Practice Content Note > Make sure to review Asymptotic Analysis Basics before proceeding with these problems. Introduction Asymptotics is a very intuition-based concept...
How to contribute #
See the
contributing guide
Thanks for your interest in contributing to my notes! There's a lot of room for improvement, and I don't have...Contributing
The pages that could be most improved (in no particular order) are
Union Find (Disjoint Sets)
Union Find (Disjoint Sets)
Content Note
> This is not a complete entry, because I feel like existing course materials already cover...
Stacks and queues are two very common data structures used for a variety of applications from CPU processes to finding... Content Note
> This page assumes prior knowledge of linked lists from CS61A or equivalent. I'll assume you have already worked... Warning
> This page is incomplete. help make it better!
Basics
A Set stores a collection of values with no duplicates. Sets have... Sorting Guide
> For more information about specific sorting algorithms covered in 61B, see my guide on sorting that covers all... Binary Search
Binary search is a way of finding a specific node in a tree. It only works on binary trees... Exceptions
Basics
An exception occurs when something unintended occurs and the interpreter must exit.
While this might sound like a bad thing, we...Union Find (Disjoint Sets)
Sorting
Additionally, there are plenty of topics (Regex, Testing, Files/Scanners, Ranges, GUI just to name a few) that arenāt currently covered in this guide. If you want to add one of these topics, please create an issue first but it will almost certainly be approved.