CS50x 2026 - Lecture 5 - Data Structures | CS50

This lecture explores data structures in C, focusing on trade-offs between efficiency and memory use. It begins with abstract data types like stacks (LIFO) and queues (FIFO), illustrating their properties with real-world examples such as cafeteria trays and clothing organization. The lecture then transitions to concrete implementations of arrays, highlighting the limitations of static allocation and demonstrating dynamic memory allocation using `malloc`, `realloc`, and pointers. It introduces linked lists as a solution to dynamic sizing, detailing node structure and memory management, but notes the performance cost. The lecture further examines binary search trees, balancing search speed with memory overhead, and concludes with a discussion of hash tables and tries, emphasizing the importance of choosing appropriate data structures based on specific problem requirements and resource constraints.

Outlines

Part 1: Introduction, Abstract Data Types

Part 2: Memory Management, Dynamic Allocation

Part 3: Linked Lists

Part 4: Trees, Binary Search Trees

Part 5: Hashing, Hash Tables

Part 6: Tries, Practical Applications

Sign in to continue reading, translating and more.

Continue

CS50x 2026 - Lecture 5 - Data Structures

CS50

Part 1: Introduction, Abstract Data Types

00:00Introduction to CS50 Week 5: Data Structures and Transition to Python

Introduction to CS50 Week 5: Data Structures and Transition to Python

00:25Stacks and Queues: Abstract Data Types Illustrated with Real-World Examples

Stacks and Queues: Abstract Data Types Illustrated with Real-World Examples

03:31Implementing Queues in C: Limitations of Static Arrays and Memory Allocation

Implementing Queues in C: Limitations of Static Arrays and Memory Allocation

07:00Stacks: LIFO Data Structure and its Implementation in C

Stacks: LIFO Data Structure and its Implementation in C

10:25Dictionaries as Abstract Data Types: Keys, Values, and Implementation Considerations

Dictionaries as Abstract Data Types: Keys, Values, and Implementation Considerations

Part 2: Memory Management, Dynamic Allocation

12:26Arrays in C: Static Allocation, Memory Limitations, and Contiguous Storage

Arrays in C: Static Allocation, Memory Limitations, and Contiguous Storage

16:01Dynamic Memory Allocation with Malloc: Overcoming Array Size Limitations

Dynamic Memory Allocation with Malloc: Overcoming Array Size Limitations

21:37Reallocating Memory: Avoiding Memory Leaks and Checking for Null

Reallocating Memory: Avoiding Memory Leaks and Checking for Null

25:11Realloc and Memory Management: Best Practices and Language Differences

Realloc and Memory Management: Best Practices and Language Differences

Part 3: Linked Lists

33:50Data Structures: Structs, Pointers, and the Arrow Operator

Data Structures: Structs, Pointers, and the Arrow Operator

35:27Linked Lists: Overcoming Array Limitations with Dynamic Memory Allocation

Linked Lists: Overcoming Array Limitations with Dynamic Memory Allocation

40:03Implementing Linked Lists in C: Nodes, Pointers, and Memory Allocation

Implementing Linked Lists in C: Nodes, Pointers, and Memory Allocation

47:49Traversing and Printing Linked Lists: Visualizing Memory and Pointer Manipulation

Traversing and Printing Linked Lists: Visualizing Memory and Pointer Manipulation

51:58Analyzing Linked List Performance: Insertion, Search, and Deletion

Analyzing Linked List Performance: Insertion, Search, and Deletion

55:17Maintaining Sorted Order in Linked Lists: Trade-offs in Time and Space

Maintaining Sorted Order in Linked Lists: Trade-offs in Time and Space

1:01:14Linked List Code Refinements and Memory Management

Linked List Code Refinements and Memory Management

1:05:21Linked List Performance Analysis: Insertion, Search, and Deletion

Linked List Performance Analysis: Insertion, Search, and Deletion

1:17:14Linked List Memory Management and Transition to Trees

Linked List Memory Management and Transition to Trees

Part 4: Trees, Binary Search Trees

1:20:25Trees: A Two-Dimensional Data Structure for Faster Searching

Trees: A Two-Dimensional Data Structure for Faster Searching

1:24:22Binary Search Trees: Structure and Properties

Binary Search Trees: Structure and Properties

1:27:20Searching in Binary Search Trees: Logarithmic Time Complexity

Searching in Binary Search Trees: Logarithmic Time Complexity

1:30:31Binary Search Tree Implementation: Code and Recursion

Binary Search Tree Implementation: Code and Recursion

1:33:50Binary Search Tree Performance: Potential for Degeneration

Binary Search Tree Performance: Potential for Degeneration

Part 5: Hashing, Hash Tables

1:37:10Hashing: Mapping Infinite Domains to Finite Ranges for Constant Time

Hashing: Mapping Infinite Domains to Finite Ranges for Constant Time

1:40:46Hash Functions: Mapping Names to Buckets for Efficient Data Retrieval

Hash Functions: Mapping Names to Buckets for Efficient Data Retrieval

1:42:37Implementing Hash Functions in C: ASCII Arithmetic and Code Refinements

Implementing Hash Functions in C: ASCII Arithmetic and Code Refinements

1:45:07Hash Tables: Arrays of Linked Lists for Key-Value Pair Storage

Hash Tables: Arrays of Linked Lists for Key-Value Pair Storage

1:48:34Hash Table Implementation: Pointers, Nodes, and Collision Handling

Hash Table Implementation: Pointers, Nodes, and Collision Handling

1:51:12Hash Table Performance: Balancing Speed and Collisions

Hash Table Performance: Balancing Speed and Collisions

1:53:35Improving Hash Functions: Reducing Collisions with More Memory

Improving Hash Functions: Reducing Collisions with More Memory

Part 6: Tries, Practical Applications

1:56:04Tries: Trees Made of Arrays for Constant-Time Lookups

Tries: Trees Made of Arrays for Constant-Time Lookups

2:02:21Tries: Memory Usage and Practical Considerations

Tries: Memory Usage and Practical Considerations

2:03:35Real-World Hash Tables: Sweetgreen's Salad Organization

Real-World Hash Tables: Sweetgreen's Salad Organization

2:04:00Hash Table Limitations and Problem Set 5 Overview

Hash Table Limitations and Problem Set 5 Overview