Common Data Structure Operations

Why This Matters

Every data structures exam tests your ability to choose the right tool for the job—and that means understanding not just what operations exist, but why certain structures handle them efficiently while others don't. You're being tested on time complexity trade-offs, memory access patterns, and the fundamental question: when does constant time matter, and when is logarithmic good enough?

The operations covered here—insertion, deletion, traversal, and search—form the backbone of algorithm analysis. Whether you're writing an FRQ about implementing a priority queue or analyzing why a hash table outperforms a linked list for lookups, you need to connect each operation to its underlying mechanism: contiguous vs. linked memory, ordering constraints, and hashing principles. Don't just memorize that arrays have $O(n)$ insertion—know why shifting elements creates that cost.

---

Sequential Access Structures

These structures store elements in a defined order and require traversal to access arbitrary elements. The key trade-off is between memory locality (arrays) and flexibility (linked lists).

Array Insertion and Deletion

• Shifting elements causes $O(n)$ time complexity—every insertion or deletion (except at the end) requires moving subsequent elements to maintain contiguous storage
• Fixed-size allocation means arrays must be resized when capacity is exceeded, typically by copying to a new, larger array
• Cache-friendly memory layout makes arrays excellent for iteration despite costly modifications—this is why they're preferred when reads dominate writes

Linked List Traversal and Manipulation

• Node-based structure with pointers enables $O(1)$ insertion and deletion when you already have a reference to the target node
• Sequential traversal required for access—no random indexing means finding the $k$th element takes $O(n)$ time
• Dynamic memory allocation eliminates resizing overhead, making linked lists ideal for frequent insertions at known positions

---

LIFO and FIFO Abstractions

Stacks and queues restrict access to specific ends of the structure. This constraint is a feature, not a limitation—it guarantees constant-time operations and models real-world processes.

Stack Push and Pop Operations

• Last In First Out (LIFO) means only the top element is accessible—push adds to top, pop removes from top, both $O(1)$
• Function call management relies on the call stack to track return addresses and local variables during recursion
• Expression evaluation uses stacks for parsing parentheses and converting between infix/postfix notation—a classic exam topic

Queue Enqueue and Dequeue Operations

• First In First Out (FIFO) processes elements in arrival order—enqueue adds to back, dequeue removes from front, both $O(1)$
• Scheduling applications include CPU task scheduling, print queues, and breadth-first search traversal
• Circular array implementation avoids the shifting problem by treating the array as a ring buffer with front/rear pointers

---

Hierarchical Structures

Trees and heaps organize data in parent-child relationships. The branching factor and balance constraints determine whether operations achieve logarithmic efficiency.

Binary Tree Insertion, Deletion, and Traversal

• Balanced trees achieve $O(\log n)$ operations—but unbalanced trees can degrade to $O(n)$, essentially becoming linked lists
• Traversal orders serve different purposes: in-order gives sorted output for BSTs, pre-order copies tree structure, post-order enables safe deletion
• Foundation for advanced structures including binary search trees, AVL trees, red-black trees, and heaps

Heap Insertion and Extraction

• Complete binary tree with heap property ensures the min (or max) element is always at the root—perfect for priority queues
• Bubble-up during insertion restores heap order by swapping with parent until the property holds, taking $O(\log n)$ time
• Heapify-down during extraction fills the root vacancy and restores order by swapping downward, also $O(\log n)$

---

Hash-Based Structures

Hash tables trade ordering for speed by using a hash function to compute storage locations directly. The magic of $O(1)$ average case depends entirely on minimizing collisions.

Hash Table Insertion, Deletion, and Lookup

• Hash function maps keys to indices enabling average-case $O(1)$ for all operations—no traversal or comparison needed
• Collision resolution strategies include chaining (linked lists at each index) and open addressing (probing for empty slots)
• Load factor affects performance—too many elements relative to table size increases collisions and degrades toward $O(n)$

---

Graph Traversal Algorithms

Graphs model relationships without hierarchical constraints. BFS and DFS are the two fundamental strategies, each suited to different problem types.

Breadth-First Search (BFS)

• Level-by-level exploration using a queue visits all neighbors before moving deeper—guarantees shortest path in unweighted graphs
• Time complexity $O(V + E)$ where $V$ is vertices and $E$ is edges—every node and edge is examined once
• Applications include shortest path, connected components, and testing bipartiteness

Depth-First Search (DFS)

• Explores as deep as possible before backtracking using a stack (or recursion's implicit call stack)
• Same $O(V + E)$ complexity as BFS, but different traversal order yields different applications
• Applications include cycle detection, topological sorting, and finding strongly connected components

---

Sorting and Searching Algorithms

These algorithms transform and query data. Understanding their complexity guarantees helps you choose the right approach for different input characteristics.

Quicksort and Mergesort

• Quicksort averages $O(n \log n)$ using divide-and-conquer with a pivot, but degrades to $O(n^2)$ on already-sorted input without randomization
• Mergesort guarantees $O(n \log n)$ and is stable (preserves relative order of equal elements), making it ideal for linked lists
• Space trade-off: quicksort is in-place ($O(\log n)$ stack space) while mergesort requires $O(n)$ auxiliary space

Binary Search

• Requires sorted input and achieves $O(\log n)$ by halving the search space with each comparison
• Comparison with linear search: binary search's $O(\log n)$ vastly outperforms linear search's $O(n)$ on large datasets
• Foundational technique appearing in tree operations, database indexing, and countless optimization problems

---

Quick Reference Table

---

Self-Check Questions

1. Which two structures offer $O(1)$ insertion and deletion but differ in the order elements are removed? What real-world scenarios favor each?

2. A hash table and a balanced BST both support insertion, deletion, and lookup. Compare their time complexities and explain when you would choose a BST despite its slower average case.

3. You need to process customer service requests in the order they arrive. Which data structure should you use, and what are its core operations?

4. Compare BFS and DFS: both have $O(V + E)$ complexity, so what determines which algorithm to use for a given graph problem?

5. An FRQ asks you to implement a system that always returns the smallest element efficiently. Compare using a sorted array, a BST, and a min-heap—which offers the best trade-off for repeated insertions and extractions?