Topic 5. Data Structures

Lectures

• Lecture 17. Hashing, Part I

  Hash functions are magical tools for building complex software systems. This lecture explores what they are and see how to use them to implement a surprisingly fast and elegant set.

  • Code

• Lecture 18. Hashing, Part II

  This lecture explores three different strategies for building hash tables - chained hashing, linear probing, and Robin Hood hashing.

• Lecture 19. Linked Lists, Part I

  Linked lists are a fundamentally different strategy for storing sequences of items. This lecture explores how to think about and manipulate them both iteratively and recursively.

  • Code

• Lecture 20. Linked Lists, Part II

  This lecture explores some further nuances of linked lists: pointers by reference and tail pointers.

  • Code

• Lecture 21. Binary Search Trees, Part I

  Binary search trees are flexible and powerful data structures for storing collections of data in sorted order. This lecture explores the basics of how BSTs work.

  • Code

• Lecture 22. Binary Search Trees, Part II

  This lecture explores binary search tree algorithms in more depth and discuss their efficiency.

  • Code

Sections

• Section 5.1 Dynamic Arrays and Hashing

• Section 5.2 Hash Tables and Linked Lists

Assignments