CS50x 2026 – Lecture 5 – Data Structures

Introduction to Data Structures

CS50 Lecture 5 presents a comprehensive exploration of data structures, one of the fundamental pillars of computer science education. Data structures are specialized formats for organizing, managing, and storing data efficiently within a computer program. They determine how data is accessed, modified, and used in algorithms, directly impacting program performance, memory usage, and code clarity. This lecture from Harvard University's renowned introductory computer science course walks through the theoretical foundations and practical implementations of the most essential data structures used in modern programming. Understanding these structures is crucial for anyone aspiring to write efficient, scalable code and solve complex computational problems.

Stacks and Queues in Action

The lecture begins by examining two fundamental abstract data types: stacks and queues. A stack operates on a Last-In-First-Out (LIFO) principle, similar to a stack of plates where the last plate placed is the first one removed. Queues, by contrast, follow a First-In-First-Out (FIFO) model, like a line at a coffee shop where the first person in line is the first to be served. Both structures are abstracted from their underlying implementation, meaning they can be realized using arrays, linked lists, or other storage mechanisms. The lecture illustrates how these simple yet powerful structures solve real-world problems: stacks manage function calls in programming languages, handle undo functionality in applications, and facilitate parsing algorithms. Queues, meanwhile, manage task scheduling, process management in operating systems, and breadth-first search algorithms. Understanding when and how to use these structures demonstrates the importance of choosing appropriate data organization methods.

Managing Dynamic Arrays with Resizing

A critical challenge in programming is handling arrays that need to grow dynamically. The lecture explores how arrays in memory are fixed-size blocks, yet programs often need flexibility to add more elements than initially allocated. The resizing strategy involves allocating a larger block of memory, copying existing elements into the new location, and freeing the old memory. This process has significant performance implications: each resize operation takes linear time relative to the number of elements, but strategic resizing (doubling capacity, for example) amortizes this cost over multiple insertions. The realloc function in C provides a direct tool for this operation, abstracting away the details of memory management while allowing programmers to focus on logic. Understanding memory allocation and reallocation is essential for writing robust programs that handle unpredictable data sizes gracefully.

Linked Lists and Dynamic Memory

Linked lists represent a fundamentally different approach to storing sequential data compared to arrays. Rather than relying on contiguous memory blocks, linked lists use nodes containing data and pointers to the next node in the sequence. This pointer-based structure offers advantages like efficient insertion and deletion at arbitrary positions without requiring data shifts, but trades off random access performance. Building a linked list requires understanding dynamic memory allocation, pointer manipulation, and careful memory management to avoid leaks and dangling pointers. The lecture demonstrates how to construct, traverse, search, and modify linked lists through code examples. Linked lists serve as the foundation for more complex data structures like stacks, queues, and graphs. The conceptual shift from array-based thinking to pointer-based thinking is pivotal in computer science education, opening pathways to understanding trees, graphs, and other advanced structures.

Hierarchical Organization with Trees

Trees introduce a hierarchical, non-linear way of organizing data that extends beyond the sequential nature of arrays and linked lists. A tree consists of nodes connected by edges, with a root node at the top and leaf nodes at the bottom. Binary search trees, a common variant, maintain the property that values in the left subtree are smaller than the parent node, while values in the right subtree are larger, enabling efficient searching in O(log n) time for balanced trees. The lecture covers tree traversal methods—in-order, pre-order, and post-order—each useful for different applications. Trees are everywhere in computer science: file systems use hierarchical tree structures, databases employ B-trees for indexing, and abstract syntax trees underpin compiler design. Understanding tree operations like insertion, deletion, and balancing is essential for writing efficient algorithms and working with real-world systems.

Hash Tables and Collision Resolution

Hash tables provide an extraordinarily efficient way to store and retrieve data based on keys, offering average-case O(1) lookup time. The core idea involves a hash function that converts a key into an array index, allowing direct access to stored values. However, different keys can hash to the same index, creating collisions that must be resolved. The lecture discusses collision resolution strategies: separate chaining (storing colliding elements in a linked list at each index) and open addressing (finding alternative empty slots). The quality of the hash function and the load factor (ratio of elements to table size) significantly impact performance. Hash tables power dictionaries, caches, and database indexing systems. Understanding hashing and its trade-offs between time complexity, space usage, and implementation complexity is vital for optimizing real-world applications that demand fast lookups.

Specialized Structures for Text Search

Tries (pronounced "trees") represent a specialized tree structure optimized for string searching and prefix matching. Each node in a trie represents a single character, and paths from root to leaves spell out words or strings. This structure enables efficient autocomplete functionality, spell-checking, and prefix-based searches. Unlike hash tables, tries maintain alphabetical ordering naturally and excel at finding all strings with a given prefix. The trade-off is increased memory usage compared to hash tables, especially for sparse character sets. The lecture demonstrates how tries are implemented and their applications in real systems like search engines and text editors. This specialized structure illustrates how choosing the right data structure for a specific problem—in this case, string-heavy workloads—can dramatically improve algorithm efficiency and functionality.

Practical Application and Selection Criteria

The lecture emphasizes that selecting the appropriate data structure depends on the specific problem, operations required, and performance constraints. Arrays provide fast random access but costly insertions and deletions. Linked lists offer flexible insertion and deletion but slower searches. Trees enable hierarchical organization and efficient searching with balance. Hash tables provide blazingly fast lookups but require good hash functions. Tries excel at prefix-based string operations. Real-world programming involves understanding these trade-offs and applying the right tool for each job. The course positions these foundational concepts as building blocks for advanced topics in algorithms, databases, and systems programming, empowering students to think critically about how data organization influences computational efficiency and program design.