Computing · Subjects

Computer Science

Core data structures, common algorithms, and Big O notation - the vocabulary that shows up in almost every intro CS course.

Foundations

Data structures glossary

Structure	What it is
Array	A fixed-size, ordered collection of elements accessed by index; fast lookups, slow inserts in the middle
Linked list	A chain of nodes where each points to the next; fast inserts/deletes, slow lookups
Stack	Last-in, first-out (LIFO) - like a stack of plates. Used for undo functions, call stacks
Queue	First-in, first-out (FIFO) - like a line at a store. Used for task scheduling, breadth-first search
Hash table (map)	Stores key-value pairs with near-instant lookup by key
Tree	A hierarchical structure of nodes with a single root; binary search trees keep data sorted for fast lookup
Graph	A set of nodes connected by edges, used to model networks (maps, social connections, dependencies)

Problem-Solving

Binary search: Repeatedly halves a sorted list to find a target - O(log n) instead of checking every element.
Bubble sort: Repeatedly swaps adjacent out-of-order elements. Simple to understand but slow - O(n²) - on large lists.
Merge sort: Splits a list in half recursively, sorts each half, then merges them - O(n log n), much faster than bubble sort at scale.
Breadth-first search (BFS): Explores a graph level by level using a queue - finds the shortest path in an unweighted graph.
Depth-first search (DFS): Explores a graph by going as deep as possible before backtracking, typically using a stack or recursion.

Efficiency

Notation	Name	Example
`O(1)`	Constant	Accessing an array element by index
`O(log n)`	Logarithmic	Binary search
`O(n)`	Linear	Looping through a list once
`O(n log n)`	Linearithmic	Merge sort, quicksort (average case)
`O(n²)`	Quadratic	Nested loops over the same list (bubble sort)

Big O describes how an algorithm's running time grows as input size grows - it's about scalability, not raw speed on small inputs.