Data Structures Overview Cheat Sheet

A printable reference covering arrays, linked lists, stacks, queues, trees, hash tables, graphs, and Big-O complexity for grades 10-12.

Download PNG

Data structures are ways to organize data so a program can store, search, update, and remove information efficiently. This cheat sheet helps students compare common structures such as arrays, linked lists, stacks, queues, trees, hash tables, and graphs. Choosing the right data structure affects how fast a program runs and how much memory it uses. Students need this reference when analyzing algorithms, writing code, or preparing for computer science exams. The most important ideas are access patterns, insertion and deletion costs, ordering rules, and Big-O complexity. Arrays give fast index access, stacks use last in, first out behavior, and queues use first in, first out behavior. Trees organize data hierarchically, hash tables map keys to values, and graphs model relationships between connected items. Big-O notation describes how running time or memory grows as the input size n increases.

Key Facts

An array stores elements in consecutive indexed positions, and accessing A[i] takes O(1) time when the index i is known.
A linked list stores nodes with data and pointers, so inserting after a known node takes O(1) time but searching for a value takes O(n) time.
A stack follows LIFO, which means the last item pushed is the first item popped, and push(x), pop(), and peek() are usually O(1).
A queue follows FIFO, which means the first item enqueued is the first item dequeued, and enqueue(x) and dequeue() are usually O(1).
A binary search tree stores smaller values in the left subtree and larger values in the right subtree, giving average search time O(log n) when balanced.
A hash table stores key value pairs using an index computed by hash(key), and average lookup, insert, and delete time is O(1).
A graph is G = (V, E), where V is the set of vertices and E is the set of edges connecting pairs of vertices.
Big-O describes growth rate, so O(1) is constant, O(log n) is logarithmic, O(n) is linear, O(n log n) is near linear, and O(n^2) is quadratic.

Vocabulary

Array: An array is a fixed or resizable indexed collection where each element can be accessed directly by position.
Linked List: A linked list is a sequence of nodes where each node stores data and one or more references to other nodes.
Stack: A stack is a collection that allows insertion and removal only at the top using last in, first out order.
Queue: A queue is a collection that removes items in the same order they were added using first in, first out order.
Hash Table: A hash table is a structure that uses a hash function to store and find values by key quickly.
Big-O Notation: Big-O notation describes the upper-bound growth rate of an algorithm as the input size n becomes large.

Common Mistakes to Avoid

Confusing an index with a value is wrong because A[3] means the element at position 3, not necessarily the number 3.
Assuming linked lists always beat arrays is wrong because linked lists have O(n) search time and extra pointer memory, while arrays have O(1) index access.
Forgetting stack and queue removal order is wrong because a stack removes the most recent item first, while a queue removes the oldest item first.
Treating hash table operations as always O(1) is wrong because many collisions can make lookup, insert, or delete take O(n) in the worst case.
Ignoring balanced versus unbalanced trees is wrong because a balanced binary search tree can search in O(log n), while a badly unbalanced tree can search in O(n).

Practice Questions

1 An array starts at memory address 2000, each integer uses 4 bytes, and indexing starts at 0. What memory address stores A[7]?
2 A stack receives push(4), push(9), pop(), push(2), push(8), pop(). What values remain in the stack from bottom to top?
3 A hash table has 10 buckets and uses hash(key) = key mod 10. Which bucket stores keys 37, 42, and 90?
4 A program must frequently search users by username and rarely list them in sorted order. Which data structure is likely better, a hash table or a binary search tree, and why?