Data Structures in Java for Smith College
This website currently focuses a few weeks into the course I would usually teach, after finishing the pure-Java topics. Most of the content is presented in video format (📺); a little over 100 videos with about 6 hours of total runtime.
There is some content from earlier in the course, but that content is entirely notes-based (📖).
Java Notes
This section contains a handful of notes useful for when you're "Getting started with Java".
Data Structures Notes
I consider stacks and queues to primarily be specific uses of lists -- rather than independent topics. Some of this is a trade-off for time in this course.
Big-O notation and complexity
We use big-O notation to talk about the time-complexity (and very-occasionally the space-complexity) of data structures. These notes provide an intro.
Lists: Linked & Array
We typically spend a significant amount of time on lists as the data structure family where we practice implementing every method of a data structure.
- Fixed Size Lists and ArrayLists
- Singly Linked-Lists
- Doubly Linked-Lists
- Chunky ArrayLists
- Lists Conclusions
Sorting
A sorted list can be considered a set data structure, so covering sorting also makes a fair bit of sense -- also it provides motivation for trees and practice with recursion.
- Sorting (Part 1): Binary Search, IsSorted, BubbleSort
- Sorting (Part 2): Insertion, Selection and Merge Sort
- QuickSort
- Comparison Notes - these notes provide an aside about how to get Java to sort your own classes and objects.
Trees
Trees are broadly useful and heaps are critical to a number of applications. They also continue the journey of learning to reason about relationships between nodes and data on the way to graphs.
HashTables
HashTables can provide nearly O(1) lookup, insert, and remove by spending some additional space on empty buckets.
Algorithms Preview
Data structures naturally feeds into algorithms topics, so we cover some of these at the end of this course as a "What's-next?" setup.