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?
Understanding Data Structures Overview
A data structure is more than a container. It shapes the steps a program must take to reach information. Imagine a music playlist.
A list stored in a fixed block of positions makes jumping to song number fifty easy. Removing song number two may require shifting many later songs forward.
A chain of separate nodes makes insertion simpler once the correct location is found, but reaching that location requires following links one at a time. This difference explains why programmers first ask what operations happen most often.
Stacks and queues are useful because many processes have a natural order. A web browser can keep recently visited pages in a stack. Pressing Back removes the newest page first.
A printer queue keeps jobs in arrival order so earlier requests are handled before later ones. These structures are often built from arrays or linked nodes.
The names describe the rules for adding and removing items, not necessarily the exact memory layout. Students should distinguish the abstract behavior of a stack or queue from the code used to implement it.
Trees and hash tables solve different search problems. A tree is helpful when data must stay in sorted order. It can support finding nearby values, such as the next appointment after a chosen time.
Its performance depends heavily on its shape. If values are inserted in an unlucky order, a simple binary search tree can become a long chain and lose much of its speed. Balanced tree designs prevent this by rearranging nodes when needed.
Hash tables are better for direct lookup by an identifier, such as finding a student record from an ID number. Their speed depends on a hash function spreading keys across storage locations.
Different keys can land in the same location. This is called a collision, and the program needs a plan to store or search through those colliding entries.
Graphs become important when relationships matter more than a single order. A map app represents places as vertices and roads as edges. A social network represents people and connections.
Edges may have weights, such as travel time or distance, and they may point in one direction, such as a one way street. Graph algorithms can search for reachable places, detect groups, or find a lowest cost route. The way a graph is stored matters.
An adjacency list saves space when each vertex has few connections. An adjacency matrix can make checking for a particular connection faster, but it uses much more memory for sparse graphs.
Big O is a tool for comparing how an algorithm scales, not a stopwatch reading. Constant time can still take longer than another operation on a particular computer, and a linear method can be perfectly suitable for a small list. The key is what happens when the input becomes much larger.
When studying, trace a short example by hand. Count searches, shifts, link changes, comparisons, and visits to neighboring graph vertices.
State any assumptions, including whether a tree is balanced or a hash table has few collisions. These details turn a memorized complexity label into a reasoned explanation.