CS50 Week 5 - Data Structures and Design

Overview

• Revisiting topics from past weeks with a focus on design possibilities via data structures.
• Data Structures: Methods to structure data, using computer memory cleverly to solve problems.
• Types of Data Structures:
  • Abstractions: High-level descriptions.
  • Implementation: Lower-level details.

Key Concepts

Abstract Data Types (ADT)

• Offers specific properties and characteristics.
• Implementation details are up to the programmer.

Queue

• Real-world analogy: lines/queues.
• FIFO (First In, First Out): Order of service.
• Operations:
  • Enqueue: Add an item.
  • Dequeue: Remove an item.

Stack

• LIFO (Last In, First Out): Opposite of FIFO, e.g., stack of plates.
• Real-world example: Email inbox.
• Operations:
  • Push: Add an item.
  • Pop: Remove an item.

Implementation Details

Arrays

• Store data contiguously.
• Problem: Fixed size - copying and reallocating is inefficient.

Linked Lists

• Nodes containing data and a pointer to the next node.
• Pros: Dynamic size, no need to copy data.
• Cons: Uses more memory for pointers, slower access times.
• Operations:
  • Insertion can be constant time if prepending.
  • Searching is linear time (O(n)).

Trees

Binary Search Trees (BST)

• Organizes data hierarchically.
• Properties:
  • Left child is smaller.
  • Right child is larger.
• Operations: Logarithmic search time (O(log n)) if balanced.
• Can degrade to linked list performance if not balanced.

Hash Tables

• Combine arrays and linked lists.
• Hash Function: Maps input to array index.
• Operations:
  • Ideally constant time (O(1)), but can degrade to linear time (O(n)) in worst case.
  • Collision handling using linked lists.

Tries

• Structure: Trees of arrays.
• Operations: Constant time (O(1)) search, insertion, deletion.
• Cons: Requires a lot of space.

Application Examples

• Sweetgreen Salad Pickup: Uses dictionary-like structure to organize orders by first letter of the name.

Conclusion

• Data structures are integral to efficient problem solving in computing.
• The choice of data structure impacts performance and efficiency, often involving trade-offs between time and space complexity.
• Emphasis on understanding theoretical and practical implications of each data structure.