A data structure (DS) is a specialized format for organizing, storing, retrieving, and managing data in a computer so that it can be used efficiently. It defines the relationship between data elements and the operations (insert, delete, search, traverse…) that can be performed on them.
It is NOT just "storage" — a shelf full of random boxes isn't a data structure. A labeled, alphabetically-sorted bookshelf is, because the arrangement makes "find book X" fast.
Same data, different arrangement → wildly different performance. Choosing the right DS is often the difference between an app that responds instantly and one that times out.
• Reusability — DS + algorithms are the reusable building blocks of all software
• Scalability — apps serving millions of users live or die by DS choice
• Abstraction — DS hide low-level memory details behind clean operations
These two are always paired but are not the same thing:
Algorithm = the "verb" — the step-by-step procedure operating on that arrangement (Binary Search, DFS, Merge Sort…)
Program = Data Structures + Algorithms (Niklaus Wirth, 1976)
Operations must produce the right result for every valid input, including edge cases (empty, full, single element).
How the operation's runtime scales as the number of elements (n) grows — measured with Big-O.
How much extra memory is needed beyond the input itself, as n grows.
An Abstract Data Type is defined only by its behavior (the operations you can call and the contract each one honors), not by its internal representation. The same ADT can have multiple valid implementations.
push, pop, peek, isEmpty with LIFO order.
You could implement it using an array or a linked list — the user of the Stack never needs to know which. That hidden choice is the "concrete data structure"; the promise is the "abstract data type."
| ADT | Core Operations | Order Guarantee | Typical Implementation |
|---|
Implemented via Array (fast random access) or Linked List (fast insert/delete at known position).
Implemented via Hash Table (average O(1)) or balanced Tree (guaranteed O(log n), sorted keys).
Inverted indexes (hash maps + sorted lists) map every word to the documents containing it. Tries speed up autocomplete. Graphs model the web itself for PageRank.
Road networks are graphs; Dijkstra's / A* algorithms run over adjacency lists to find shortest routes in milliseconds.
B-Trees / B+Trees index rows on disk for O(log n) lookups. Hash indexes give O(1) equality lookups. Query planners use graphs of operations.
Stacks track undo history, function call frames, and expression parsing (e.g. converting infix → postfix, balancing brackets).
Queues manage processes waiting for CPU time; priority queues (heaps) implement priority-based and shortest-job-next scheduling.
Tensors (multi-dim arrays) hold weights/activations; k-d trees and graphs power nearest-neighbor search and GNNs.
| Type | Category | Access | Search | Insert | Delete |
|---|
Imagine you have a box of toys and you want to find your favorite one.
📚 O(log n) — Logarithmic: Your toys are sorted by size. You check the middle, decide "bigger or smaller", and throw away half the box each time. A million toys? Still done in ~20 checks!
🔎 O(n) — Linear: Toys are dumped in a pile, unsorted. You must look at every single one until you find it. 2× the toys = 2× the time.
🧮 O(n log n): You first sort the pile (like organizing by size in groups), then search. Slightly more work than O(n), but WAY better than checking every pair.
🐢 O(n²) — Quadratic: For every toy, you compare it against every other toy (like checking if any two toys match). 2× the toys = 4× the time!
🐌 O(2ⁿ) — Exponential: For every new toy you add, the work DOUBLES. Just 30 toys can already take longer than the age of the universe to fully check every combination.
These three describe the growth rate of a function f(n) (your algorithm's runtime) by comparing it to a simpler reference function g(n), for large enough n.
"My algorithm will never be slower than this, once n is big enough." It's a promise about the ceiling, not the exact speed.
"My algorithm can never be faster than this." It's a guarantee about the floor.
f(n) is sandwiched between two constant multiples of g(n) — meaning f(n) grows exactly like g(n), not faster, not slower. This is the most informative of the three.
Choose which complexity classes to race, drag n, then hit Animate. Watch how fast the "runners" separate — that gap IS what Big-O is trying to describe.
Take f(n) = 3n² + 2n + 5. We claim f(n) = Θ(n²). Adjust c₁, c₂ and n₀ below and watch whether the sandwich bound c₁·n² ≤ f(n) ≤ c₂·n² actually holds for every n ≥ n₀.
Space complexity asks the same "how does it scale?" question, but for extra memory used (beyond the input itself) as n grows.
• O(n) space — copying an array, building a hash map of n items, recursion with n stack frames.
• O(n²) space — storing a full adjacency matrix for a graph, a 2D DP table.