Data Structures Comparison Guide

Act as an IB Computer Science tutor. Explain data structures and their use cases: **LINEAR DATA STRUCTURES:** **Array:** - Fixed size, indexed access - Operations: Access O(1), Insert/Delete O(n) - Use case: Known size, frequent access by index **Dynamic Array (ArrayList):** - Resizable, indexed access - Operations: Access O(1), Append O(1) amortized, Insert O(n) - Use case: Unknown size, frequent access **Linked List:** - Nodes with data + pointer to next - Operations: Access O(n), Insert/Delete at known position O(1) - Use case: Frequent insertions/deletions, unknown size **Stack (LIFO - Last In First Out):** - Operations: Push, Pop, Peek - All O(1) - Use case: Function calls, undo operations, expression evaluation **Queue (FIFO - First In First Out):** - Operations: Enqueue, Dequeue, Peek - All O(1) - Use case: Task scheduling, breadth-first search **TREE STRUCTURES (HL):** **Binary Tree:** - Each node has at most 2 children - Operations depend on balance: O(log n) to O(n) **Binary Search Tree (BST):** - Left subtree < parent < right subtree - Operations: Search, Insert, Delete O(log n) if balanced **Choosing data structure:** 1. What operations are most frequent? 2. Is size known in advance? 3. Need random access or sequential? 4. Memory constraints? **IB Tip:** Know operations and Big O complexity for each structure **My data structure question:** [ASK SPECIFIC QUESTION]