CS50 Fall 2025 - Lecture 5 - Data Structures (live, unedited)

Overview

CS50's Lecture 5 explores fundamental data structures in C, contrasting arrays with linked lists and introducing abstract data types like stacks and queues. The lecture details memory management with `malloc`, `realloc`, and `free`, demonstrating dynamic array resizing and the implementation of linked lists. It then delves into binary search trees and hash tables, highlighting trade-offs between space, time complexity, and implementation complexity, culminating in a discussion of tries for achieving near-constant time lookups.

Key takeaways

Arrays offer O(1) access but require fixed-size allocation, while linked lists provide dynamic sizing at the cost of O(n) search/insertion/deletion.
Binary Search Trees (BSTs) balance dynamism with O(log n) average performance, but can degenerate to O(n) if unbalanced.
Hash tables use a hash function to map keys to buckets (often linked lists), aiming for O(1) average lookup but susceptible to collisions.
Tries provide guaranteed O(L) lookup (effectively constant for bounded key lengths) by storing strings implicitly, but consume significant memory.
Data structure choice involves trade-offs between time complexity, space complexity, and implementation complexity based on the specific application's needs.

Chapters

14:05 Introduction to Data Structures: Stacks and Queues

Data structures are fundamental to efficient problem-solving.
Stacks follow a Last-In, First-Out (LIFO) principle.
Queues follow a First-In, First-Out (FIFO) principle.
Abstract Data Types (ADTs) define functionality independent of implementation.

16:54 Implementing Queues and Stacks with Arrays

Arrays can implement stacks and queues but have fixed size limitations.
Fixed-size arrays lead to trade-offs between memory waste and capacity.
Recompiling code is necessary to change array capacity.

20:00 Dictionaries as Abstract Data Types

Dictionaries associate keys with values.
Examples include word definitions and phone book entries.
Implementation choices affect performance and scalability.

20:36 Arrays: Contiguous Memory Allocation

Arrays store elements contiguously in memory.
Declaration requires specifying a fixed size in advance.
Accessing elements is O(1) via index.

24:30 Dynamic Memory Allocation with `malloc`

Arrays require static size allocation, problematic for dynamic data.
`malloc` allocates memory dynamically from the heap.
Must check `malloc` return value for `NULL` to handle allocation failures.

26:20 Pointer Arithmetic and Array Equivalence

C allows treating pointers as arrays and vice-versa using bracket notation.
`list[i]` is syntactic sugar for `*(list + i)`.
Dynamic allocation offers flexibility but requires careful memory management.

29:30 Resizing Dynamically Allocated Memory: `realloc`

Manually resizing arrays involves allocating new memory, copying data, and freeing old memory.
`realloc` attempts to resize an existing memory block, potentially moving it.
Requires checking `realloc` return value for `NULL` and handling potential memory leaks.

35:00 Memory Leaks and `free()`

Memory leaks occur when allocated memory is no longer accessible but not freed.
Always `free` dynamically allocated memory when it's no longer needed.
Programs should handle allocation failures gracefully, freeing previously allocated resources.

40:15 Linked Lists: Dynamic Data Structures

Linked lists overcome array's fixed-size limitation by storing nodes non-contiguously.
Each node contains data and a pointer to the next node.
The list itself is represented by a pointer to the first node.

44:20 Implementing Linked List Nodes

A `node` struct contains data (e.g., an `int`) and a `next` pointer.
The `next` pointer points to the subsequent `node` or `NULL`.
Forward declaration (`struct node`) is needed for self-referential structs.

49:00 Building a Linked List: Prepending Nodes

Initialize list pointer to `NULL` for an empty list.
Allocate new node using `malloc`.
Set new node's `next` pointer to the current list head.
Update list head to point to the new node.

52:15 Traversing and Printing a Linked List

Use a temporary pointer (`PTR`) initialized to the list head.
Loop while `PTR` is not `NULL`.
Access node data via `PTR->number` or `(*PTR).number`.
Advance `PTR` using `PTR = PTR->next`.

54:20 Linked List Insertion: Appending and Sorted Order

Appending requires traversing to the end of the list (O(n)).
Inserting in sorted order requires finding the correct position (O(n)).
Prepending is O(1), while appending and sorted insertion are O(n).

58:20 Handling Insertion Scenarios in Linked Lists

Scenarios: empty list, prepend, append, insert in middle.
Code must handle each case correctly to maintain list integrity.
Requires careful pointer manipulation to avoid memory leaks or orphaned nodes.

1:02:00 Freeing Linked List Memory

Iterate through the list, freeing each node individually.
Requires a temporary pointer to track the next node before freeing the current one.
A dedicated `unload` function encapsulates this logic.

1:09:00 Recap: Arrays vs. Linked Lists

Arrays offer O(1) access but fixed size and slow resizing.
Linked lists offer dynamic size but O(n) search, insertion, and deletion.
Trade-off: speed vs. memory flexibility.

1:17:30 Binary Search Trees (BSTs): Combining Speed and Dynamism

BSTs store data in a tree structure, enabling O(log n) average search, insertion, and deletion.
Each node has a value, a left child pointer, and a right child pointer.
BST property: left child < parent < right child.

1:20:00 BST Search Algorithm (Recursive)

Base case: If tree is `NULL`, return `false`.
Compare target value with current node's value.
Recursively search left subtree if target is smaller, right subtree if larger.
Return `true` if target matches current node's value.

1:23:20 BST Challenges: Balancing and Degeneration

Unbalanced BSTs (e.g., inserting sorted data) can degenerate into linked lists (O(n) performance).
Self-balancing BSTs (e.g., AVL trees, Red-Black trees) maintain O(log n) performance but add complexity.
BSTs use more memory per node than arrays due to pointers.

1:28:00 Hashing: Mapping Infinite to Finite Domains

Hashing aims for O(1) average time complexity for lookups.
A hash function maps input values (keys) to a finite range of indices (buckets).
Collisions occur when different keys map to the same index.

1:29:00 Hash Function Implementation

Simple hash function for names: convert first letter to uppercase, subtract ASCII value of 'A'.
Handles case-insensitivity by converting to uppercase.
Returns an index between 0 and 25 for English alphabet names.

1:31:00 Hash Tables: Arrays of Linked Lists

Hash tables combine arrays and linked lists.
An array of buckets, where each bucket is a linked list.
Hash function determines the bucket for a given key.

1:34:00 Hash Table Collisions and Trade-offs

Collisions are inevitable when mapping a large domain to a smaller range.
Chaining (using linked lists in buckets) resolves collisions.
Performance degrades towards O(n) if collisions are frequent and lists become long.
Trade-off: Hash function quality vs. memory usage (larger array reduces collisions but uses more space).

1:40:00 Tries: Achieving Constant Time Lookups

Tries (prefix trees) store strings implicitly based on character sequences.
Each node is an array of pointers (e.g., size 26 for English alphabet).
Path from root to a node represents a prefix; a boolean flag marks word endings.

1:42:00 Trie Implementation and Lookup

Nodes contain an array of child pointers and potentially data (e.g., phone number).
Lookup involves traversing the trie based on characters of the key.
Lookup time is proportional to the length of the key, effectively constant for bounded key lengths.

1:44:00 Trie vs. Hash Table: Space vs. Time

Tries offer guaranteed O(L) lookup (where L is key length, effectively constant) but use significant memory.
Hash tables offer O(1) average lookup but can degrade to O(n) with poor hash functions and collisions.
Hash tables are often preferred in practice due to better space efficiency.

1:45:00 Real-World Hashing: Sweetgreen Example

Restaurants like Sweetgreen use hashing for order pickup shelves.
Buckets based on name initial ranges (e.g., A-E, F-J).
Potential for overflow if distribution is uneven, requiring dynamic resizing or re-bucketing.

1:46:40 Final Data Structures and Problem Set 5

Tries achieve constant time but use substantial memory.
Hash tables are practical, offering good average performance with manageable memory.
Problem Set 5 involves implementing hash tables for a spell checker.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, CS50.