Key Concepts in Data Structures

Why This Matters

Data structures are the backbone of every algorithm you'll encounter in AP Info—and the exam knows it. You're being tested on your ability to choose the right structure for a given problem, which means understanding not just what each structure does, but why it performs the way it does. The concepts here connect directly to algorithm efficiency, memory management, and problem-solving strategies that appear throughout the course.

Think of data structures as tools in a toolbox: arrays are your reliable hammer, hash tables are your power drill, and trees give you precision when you need hierarchy. The exam will ask you to analyze trade-offs between access speed, insertion cost, memory usage, and organizational structure. Don't just memorize definitions—know what problem each structure solves best and when you'd reach for one over another.

---

Linear Structures: Sequential Access Patterns

These structures organize data in a straight line, one element after another. The key trade-off is between fast access (arrays) and fast modification (linked lists).

Arrays

• Fixed-size, contiguous memory—elements sit next to each other in memory, enabling instant access via index
• $O(1)$ retrieval time makes arrays ideal when you know exactly which position you need
• $O(n)$ insertion/deletion cost because shifting elements is required to maintain order

Linked Lists

• Node-based structure where each node holds data plus a pointer to the next node
• $O(1)$ insertion and deletion when you already have a reference to the target position
• $O(n)$ access time since you must traverse from the head—no jumping to middle elements

---

LIFO and FIFO: Controlled Access Structures

Stacks and queues restrict how you interact with data, which makes them perfect for specific algorithmic patterns. The restriction is the feature—it enforces order.

Stacks

• Last In, First Out (LIFO)—the most recently added element comes off first
• Push and pop operations are both $O(1)$, making stacks extremely efficient
• Use cases include function call management, undo features, and backtracking algorithms like maze solving

Queues

• First In, First Out (FIFO)—elements leave in the same order they arrived
• Enqueue and dequeue operations add to the back and remove from the front, both $O(1)$
• Essential for BFS algorithms, task scheduling, and any situation requiring fair ordering

---

Hierarchical Structures: Trees and Their Variants

Trees organize data in parent-child relationships, enabling efficient searching and sorted storage. The branching structure is what gives trees their logarithmic performance.

Trees

• Root node with child nodes creates a hierarchical, non-linear organization
• Efficient operations for searching, insertion, and deletion—especially in balanced variants
• Real-world applications include file systems, organizational charts, and database indexing

Binary Search Trees

• Left child < parent < right child—this ordering property enables fast lookups
• $O(\log n)$ average case for search, insert, and delete when the tree stays balanced
• Maintains sorted order automatically, making it ideal for dynamic datasets requiring frequent lookups

Heaps

• Heap property ensures the root is always the max (max-heap) or min (min-heap) element
• $O(1)$ access to extreme value plus $O(\log n)$ insertion makes heaps highly efficient
• Powers priority queues and sorting algorithms like heapsort—know this for algorithm questions

---

Relationship-Based Structures: Graphs and Networks

Graphs model connections between entities, making them essential for network analysis and pathfinding. The flexibility of edges—directed or undirected, weighted or unweighted—is what makes graphs so powerful.

Graphs

• Vertices connected by edges represent relationships—think social networks, maps, or dependencies
• Directed vs. undirected and weighted vs. unweighted variations allow modeling of diverse scenarios
• Fundamental for shortest path algorithms (Dijkstra's), network flow, and social connection analysis

---

Optimized Lookup: Hash-Based Storage

Hash tables sacrifice ordered storage for blazing-fast retrieval. The hash function is the magic—it converts keys directly into memory locations.

Hash Tables

• Key-value storage with a hash function that maps keys to array indices
• $O(1)$ average case for search, insert, and delete—the fastest lookup structure
• Collision handling via chaining (linked lists at each index) or open addressing (probing for empty slots)

---

Analyzing Efficiency: Time and Space Complexity

Understanding why structures perform differently requires analyzing their complexity. Big O notation is your language for comparing efficiency.

Time and Space Complexity Analysis

• Big O notation expresses the upper bound of growth rate—how performance scales with input size
• Time complexity measures operations; space complexity measures memory usage
• Guides structure selection—knowing that hash tables are $O(1)$ average but $O(n)$ worst case helps you make informed choices

---

Quick Reference Table

---

Self-Check Questions

1. Which two structures both offer $O(1)$ insertion but differ in how you access elements afterward?

2. You need to process tasks in the exact order they were received. Which structure enforces this, and what principle does it follow?

3. Compare and contrast binary search trees and heaps: when would you choose each, and what ordering guarantee does each provide?

4. An FRQ asks you to design a system for fast username lookups. Which structure offers the best average-case performance, and what potential issue must you address?

5. Why might a linked list outperform an array for a program that frequently inserts elements in the middle of a collection, even though arrays have faster access times?