Previous Topic

What Are Data Structures?

Data structures are organized ways to store and manage data so it can be used efficiently. They pair with algorithms to process information. Many languages provide built-in implementations (like lists, maps, and sets), but understanding how they work helps you choose the right tool, reason about performance, and implement custom solutions. It is also useful to distinguish between an Abstract Data Type (ADT)—the behavior promised by an interface (e.g., Stack: push, pop)—and a concrete implementation (e.g., array-backed or linked-list-backed).

Why They Matter

• Speed: The right structure can turn a slow operation into a fast one (e.g., O(n) to O(log n) or O(1)).
• Memory: Structures differ in overhead and locality, affecting cache use and space.
• Correctness: Some structures naturally enforce invariants (e.g., priority queues always expose the min/max).
• Scalability: Good choices handle larger inputs and growth gracefully.
• Expressiveness: Data layout often clarifies the design of a system or algorithm.

Core Concepts and Operations

• Access: Get an element by index or key.
• Search: Find an element by value or predicate.
• Insert/Delete: Add or remove elements at various positions.
• Traversal: Visit elements sequentially or via a structure-specific order (e.g., tree traversals).
• Big-O Complexity: Asymptotic time and space costs guide choices under growth.

Fundamental Structures

Arrays

• Idea: Contiguous block of memory with fixed or dynamic size.
• Performance: O(1) random access; inserts/deletes in the middle are O(n) due to shifting.
• Notes: Excellent cache locality; dynamic arrays occasionally resize (amortized O(1) append).
• Use cases: Index-based access, buffers, small collections with frequent iteration.

Linked Lists

• Idea: Nodes linked via pointers (singly or doubly linked).
• Performance: O(1) insert/delete at known node; O(n) access/search.
• Notes: Extra memory per node; poorer cache locality than arrays.
• Use cases: Frequent insertions/deletions, queues, implementing other structures.

Stacks

• Idea: Last-In, First-Out (LIFO).
• Operations: push, pop, top/peek all O(1).
• Use cases: Function call stacks, undo/redo, parsing, DFS.

Queues and Deques

• Queue: First-In, First-Out (FIFO): enqueue, dequeue O(1).
• Deque: Insert/remove at both ends in O(1).
• Implementations: Linked lists or circular buffers (array-based).
• Use cases: Task scheduling, BFS, sliding window algorithms (deques).

Hash Tables (Maps/Sets)

• Idea: Map keys to indices via a hash function.
• Performance: Average O(1) insert/search/delete; worst-case O(n) with poor hashing or adversarial input.
• Notes: Handle collisions (chaining or open addressing), choose good hash functions, manage load factor and resizing.
• Use cases: Fast lookups, frequency counting, caching, symbol tables.

Trees

• Idea: Hierarchical nodes with parent-child relationships.
• Binary Search Trees (BSTs): Left subtree < node < right subtree; average O(log n) search/insert/delete if balanced.
• Balanced BSTs: AVL, Red-Black maintain O(log n) operations.
• Heaps: Priority queue with O(log n) push/pop and O(1) peek (min/max).
• Use cases: Indexing, priority scheduling, range queries, maintaining sorted order.

Graphs

• Idea: Nodes (vertices) connected by edges; directed or undirected, weighted or unweighted.
• Representations: Adjacency list (sparse, memory-efficient) vs. adjacency matrix (dense, O(1) edge queries).
• Use cases: Networks, dependency graphs, routing, social connections.

Choosing the Right Structure

• What operations dominate? (access vs. search vs. insert/delete)
• Do you need ordering or sorting guarantees?
• Memory constraints and overhead per element.
• Iteration patterns and cache friendliness.
• Concurrency needs and immutability considerations.
• Language/library support and simplicity of maintenance.

Practical Tips

• Favor standard library implementations for reliability and performance.
• Know amortized vs. worst-case costs (e.g., dynamic array resizing, rehashing).
• Be cautious with hash functions; poor choices degrade performance.
• Benchmark real workloads; asymptotics don’t capture constants and cache effects.
• Document invariants (e.g., sortedness, heap property) and test them.

Mini Scenarios

• Balanced parentheses: Use a stack to push opening symbols and pop on closing; empty at end means balanced.
• Top-k tasks by priority: Use a heap to repeatedly extract the highest priority.
• Counting frequencies: Use a hash map from item to count for O(n) average-time aggregation.
• Level-order traversal: Use a queue to perform BFS on a tree or graph.

Key Terms

• Size: Number of elements currently stored.
• Capacity: Space allocated before resizing is needed.
• Head/Tail: Ends of a list or queue; Top/Front/Rear for stacks/queues.
• Load factor: Hash table fullness; influences rehashing.
• Height (trees): Longest path from root to a leaf; affects complexity.

Next Topic