Computer Science - StudyReady

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.

Common Mistakes

Patterns we see again and again in student work. Each one is fixable once you know to look for it.

Reading code instead of writing it: Understanding a solution when you read it is not the same as being able to produce it. Programming is a skill, and it is built by writing code, running it, seeing it fail, and fixing it. If your study session involves no typing, it is not a programming study session.
Memorizing Big O for each algorithm instead of deriving it: The table on this page is a reference. The skill exams test is looking at a loop or a recursive call and working out the complexity. Practice on code you have not seen: count how many times the inner statement runs as the input grows.
Picking a data structure by habit: Arrays are the default and often the wrong choice. For every problem, ask what operations you need to be fast (lookup by key? insertion at the front? ordering?) and pick the structure whose strengths match. Most interview-style and exam questions are really this question in disguise.
Not tracing by hand: When code does something unexpected, the fastest fix is to take a small input and walk through the code line by line on paper, writing down every variable after every step. Students skip this because it feels slow. It is faster than staring, and it is exactly what exam trace questions ask you to do.
Ignoring edge cases: Empty input, one element, duplicates, negative numbers, the largest allowed size. Most bugs and most lost exam marks live at the edges. Before you call a solution finished, list the edge cases and test each one.