CS50x 2025 - Lecture 5 - Data Structures

Introduction

This tutorial provides an overview of essential data structures covered in CS50's Lecture 5. Understanding these structures is vital for efficient programming and problem-solving. We'll explore stacks, queues, linked lists, trees, hash tables, and tries, along with practical implementations and concepts.

Step 1: Understanding Stacks and Queues

• Stacks: A stack is a Last In, First Out (LIFO) structure. The last element added is the first to be removed.

  • Common operations:
    • Push: Add an element to the top.
    • Pop: Remove the top element.
  • Real-World Application: Undo functionality in applications.

• Queues: A queue is a First In, First Out (FIFO) structure. The first element added is the first to be removed.

  • Common operations:
    • Enqueue: Add an element to the back.
    • Dequeue: Remove the front element.
  • Real-World Application: Print job management.

Step 2: Resizing Arrays

• Dynamic arrays allow you to resize as needed, unlike static arrays.
• Use realloc to adjust the size of an array:

  int* array = malloc(size * sizeof(int));
  array = realloc(array, new_size * sizeof(int));
  

• Tip: Always check if realloc returns NULL to avoid memory leaks.

Step 3: Exploring Linked Lists

• A linked list is a collection of nodes where each node points to the next.
  • Advantages over arrays:
    • Dynamic size.
    • Efficient insertions/deletions.
• Common operations:
  • Insertion: Add a new node.
  • Deletion: Remove a node.

Example of a Linked List Node in C:

typedef struct node {
    int value;
    struct node* next;
} node;

Step 4: Introduction to Trees

• Trees are hierarchical structures with nodes connected by edges.
• A binary tree has at most two children per node.
  • Traversal methods:
    • In-order
    • Pre-order
    • Post-order
• Real-World Application: Hierarchical data representation, like file systems.

Step 5: Understanding Binary Search Trees

• A binary search tree (BST) maintains a sorted order:
  • Left child < Parent < Right child
• Operations include:
  • Insert: Place a new node in the appropriate location.
  • Search: Efficiently locate a node.

Step 6: Working with Dictionaries

• Dictionaries are key-value pairs; they allow fast retrieval using keys.
• Implemented often using hash tables for efficiency.

Step 7: Introduction to Hashing and Hash Tables

• Hashing transforms input into a fixed-size value, used as an index.
• Hash tables store entries in key-value pairs:
  • Collision resolution strategies include chaining and open addressing.

Step 8: Learning About Tries

• A trie is a tree-like structure used for storing strings.
• Each node represents a character, and paths represent words.
• Useful for autocomplete and spell-checking applications.

Conclusion

This tutorial covered the fundamental data structures necessary for efficient programming, including stacks, queues, linked lists, trees, hash tables, and tries. Each structure has unique properties suitable for different applications. Consider implementing these structures in your own projects to solidify your understanding and improve your coding skills. Explore further by practicing with coding exercises and real-world examples.