Introduction to Data Structures

Learning Objectives

By the end of this page, you should be able to:

• Define a data structure and explain why choosing the right one changes program performance.
• List the major categories of data structures (linear vs. non-linear, primitive vs. non-primitive) and give an example of each.
• Read and write Big-O notation for time and space complexity, and explain what "worst case" means.
• Compare arrays, linked lists, stacks, queues, and hash tables at a high level, including at least one strength and one weakness of each.
• Trace through a simple operation (like array access or a stack push) and identify its time complexity.
• Explain why the same problem can be solved with different data structures with different efficiency trade-offs.

Quick Answer

A data structure is a specific way of organizing and storing data in memory so it can be accessed and modified efficiently. The same collection of values — say, a list of student names — behaves very differently depending on whether you store it in an array, a linked list, or a hash table: some make searching fast, others make insertion fast, and none make everything fast at once. Studying data structures matters because almost every performance problem in software ("why is this slow?") traces back to picking the wrong one for the job. This page introduces the major categories, the vocabulary you'll need (time complexity, space complexity, Big-O), and sets up the deeper dives into arrays, linked lists, trees, and hashing that follow in this series.

What Is a Data Structure, Really?

Strip away the jargon and a data structure is just an answer to two questions: where do I put each piece of data, and how do I get back to it later?

A phone doesn't just "store contacts" — it stores them in a structure (often a balanced tree or hash table under the hood) so that typing three letters instantly narrows down thousands of names. If contacts were stored as an unsorted list, that same search would mean checking every single entry. Same data, wildly different experience — that's the entire reason data structures exist.

Definition: A data structure is a scheme for organizing related data items in memory, together with the set of operations (insert, delete, search, traverse) defined on it.

Common Misunderstanding: Students often think a data structure is just "a variable that holds a list of things." In reality, a data structure is defined as much by its operations and their costs as by what it stores. A Python list and a Python set can both hold the numbers 1, 2, 3 — but x in my_set and x in my_list have completely different costs (O(1) average vs O(n)). The data structure is the combination of layout + allowed operations + their complexity, not just "a container."

Categories of Data Structures

Data structures are usually split along two axes: how the language treats them (primitive vs. non-primitive) and how the data is arranged (linear vs. non-linear).

Primitive vs. Non-Primitive

• Primitive data structures are the basic types built into a language — int, float, char, boolean. They hold a single value and are the raw material everything else is built from.
• Non-primitive data structures are built by combining primitives — arrays, linked lists, trees, graphs, hash tables. This is what people usually mean when they say "data structures."

Linear vs. Non-Linear

• Linear data structures arrange elements sequentially, one after another. Each element (except the first/last) has exactly one predecessor and one successor. Examples: arrays, linked lists, stacks, queues.
• Non-linear data structures arrange elements hierarchically or in networks, where an element can connect to multiple others. Examples: trees, graphs, heaps.

Real-World Example: A playlist is linear — song 1 leads to song 2 leads to song 3. A family tree is non-linear — one person can have multiple children, and tracing ancestry branches outward rather than in a single line.

Common Misunderstanding: Students sometimes assume "non-linear" means "unordered" or "random." A tree is highly ordered (a binary search tree, for instance, enforces a strict left-smaller/right-larger rule) — it's non-linear because of its branching shape, not because it lacks order.

A Quick Tour of the Major Structures

This page is an overview — each of these gets its own deep-dive chapter later in this series. Here's the elevator pitch for each one.

Arrays — a fixed-layout, contiguous block of memory holding elements of the same type. You get to any element instantly if you know its index.

scores = [88, 92, 79, 95]
print(scores[2])  # 79 — direct jump to memory offset 2, O(1)

Linked Lists — a chain of nodes, each holding data and a pointer to the next node. No contiguous memory requirement, so growing the list doesn't require shifting anything.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(10)
head.next = Node(20)  # 10 -> 20, connected by reference, not position

Stacks — Last-In-First-Out (LIFO). Think of a stack of plates: you only add or remove from the top.

stack = []
stack.append("A")
stack.append("B")
stack.pop()  # removes "B" — the last one in, is the first one out

Queues — First-In-First-Out (FIFO). Think of a checkout line: first person in line is served first.

from collections import deque
queue = deque()
queue.append("A")
queue.append("B")
queue.popleft()  # removes "A" — the first one in, is the first one out

Trees — a hierarchy of nodes where each node can have children, but exactly one parent (except the root, which has none).

Graphs — vertices connected by edges, with no restriction on how many connections a node can have. Roads, social networks, and web links are all naturally graphs.

Hash Tables — store key-value pairs using a hash function to compute where a value lives, giving average O(1) lookup, insertion, and deletion.

Real-World Example: A web browser uses a stack for the back button (last page visited is the first one you return to), a queue for print jobs sent to a printer, and a hash table for its DNS cache (looking up an IP address for a domain name instantly instead of re-searching).

Common Misunderstanding: New programmers assume more "advanced" structures (trees, graphs, hash tables) are always better than "simple" ones (arrays). Advanced doesn't mean superior — it means specialized. An array is unbeatable for a fixed-size list you access by position; a hash table is overkill (and uses more memory) if you only ever need index-based access.

Why Study Data Structures?

1. Efficiency — the right structure can turn an O(n) operation into O(1) or O(log n), which matters enormously as data grows. A search that takes 1 millisecond on 1,000 records might take over 15 minutes on 1 billion records if you picked the wrong structure.
2. Problem-solving — most coding interview and real-world engineering problems are, underneath, "which data structure models this relationship well?"
3. Memory management — structures like linked lists trade memory overhead (extra pointers) for flexibility (no resizing cost); arrays trade flexibility for compactness.
4. Foundation for algorithms — sorting, searching, graph traversal, and dynamic programming are all built on top of specific data structures.

Measuring Efficiency: Time and Space Complexity

You can't compare data structures meaningfully without a common language for "how fast" and "how much memory." That language is Big-O notation — it describes how the cost of an operation grows as the input size (n) grows, ignoring constant factors and focusing on the worst case.

Big-O	Name	What it means in practice
O(1)	Constant	Cost doesn't change with input size — e.g., array index access
O(log n)	Logarithmic	Cost grows slowly — e.g., binary search, balanced tree lookup
O(n)	Linear	Cost grows directly with input size — e.g., scanning a list
O(n log n)	Linearithmic	Typical of efficient sorting algorithms (merge sort, heap sort)
O(n²)	Quadratic	Nested loops over the same data — e.g., bubble sort, naive duplicate check
O(2ⁿ)	Exponential	Cost doubles with each additional input — e.g., naive recursive Fibonacci

Common Misunderstanding: Big-O is not a measure of actual runtime in seconds — it's a measure of growth rate. An O(n²) algorithm can outperform an O(n log n) algorithm on small inputs because Big-O hides constant factors. The crossover only becomes visible as n gets large. Also, Big-O by convention describes the worst case unless stated otherwise (you'll sometimes see Big-Theta for average case and Big-Omega for best case, but most courses default to worst-case Big-O).

Here's how the structures introduced above compare once you apply this lens (details and derivations come in their dedicated chapters):

Structure	Access	Search	Insert	Delete	Notes
Array	O(1)	O(n)	O(n)*	O(n)*	*O(1) only if inserting/deleting at the end
Linked List	O(n)	O(n)	O(1)**	O(1)**	**O(1) only if you already have a reference to the node
Stack	O(n)	O(n)	O(1)	O(1)	Insert/delete restricted to the top
Queue	O(n)	O(n)	O(1)	O(1)	Insert at rear, delete from front
Hash Table	—	O(1) avg	O(1) avg	O(1) avg	Worst case O(n) if many keys collide
Binary Search Tree (balanced)	O(log n)	O(log n)	O(log n)	O(log n)	Degrades to O(n) if unbalanced

Common Misunderstanding: "Hash tables are O(1), so they're always fastest" — only true on average, assuming a good hash function and low collision rate. A poorly implemented hash table with many collisions degrades toward O(n), the same as a linked list. Average-case and worst-case complexity are different guarantees, and exam questions love testing whether you know which one applies.

Other Foundational Concepts

Recursion is a function calling itself to break a problem into smaller identical subproblems (e.g., traversing a tree, computing a factorial). It's central to how many data structure operations — especially on trees and graphs — are naturally expressed.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Iteration solves the same kinds of problems using loops instead of self-calls. Both approaches can implement the same logic; recursion often reads more naturally for hierarchical data (trees), while iteration is usually more memory-efficient (no call stack buildup).

Common Misunderstanding: Students think recursion is "the tree/graph way" and iteration is "the array way," as if you must choose one per data structure. In reality, almost anything recursive can be rewritten iteratively using an explicit stack — recursion is a convenience the call stack gives you, not a requirement of the data structure itself.

Real-World Applications

• Web browsers: hash tables cache DNS lookups and page resources; a stack powers the back/forward button history.
• Social media platforms: graphs represent the friend/follow network; queues buffer notifications and message delivery.
• Database systems: B-trees (a generalized tree structure) power indexes for fast lookups; hash tables back in-memory caches.
• Search engines: inverted indexes (hash tables mapping words to documents) make keyword search near-instant across billions of pages.
• Video games: heaps schedule which game events fire next by priority; linked lists implement undo/redo stacks for level editors.

Key Terms

Term	Definition	Context/Related
Data Structure	A way of organizing and storing data along with the operations defined on it	Foundation for arrays, lists, trees, graphs
Time Complexity	A measure of how the runtime of an operation grows with input size	Expressed using Big-O notation
Space Complexity	A measure of how much memory an algorithm or structure uses relative to input size	Also expressed using Big-O notation
Big-O Notation	Mathematical notation describing the upper-bound growth rate of an algorithm's cost	O(1), O(log n), O(n), O(n log n), O(n²)
Linear Data Structure	A structure where elements are arranged sequentially	Arrays, linked lists, stacks, queues
Non-Linear Data Structure	A structure where elements branch or connect in multiple directions	Trees, graphs, heaps
Primitive Data Type	A basic built-in type holding a single value	int, float, char, boolean
Recursion	A function solving a problem by calling itself on smaller subproblems	Common in tree/graph traversal
Abstract Data Type (ADT)	A conceptual model (e.g., "stack," "queue") defined by its behavior, independent of implementation	Can be implemented via array or linked list

Common Mistakes

Misconception 1: "The most complex data structure is always the best choice." Why it's wrong: More sophisticated structures usually carry more memory overhead and implementation complexity, and their advantages only appear for specific operation patterns. Correct explanation: Choose the simplest structure that meets your actual access pattern. If you only ever append and read by index, an array beats a tree or graph on every axis — memory, speed, and simplicity.

Misconception 2: "Big-O notation tells you exactly how many seconds an operation takes." Why it's wrong: Big-O describes growth rate as input size increases, not an absolute measurement. It intentionally ignores constant factors, hardware speed, and small-input behavior. Correct explanation: Use Big-O to compare how two algorithms scale, not to predict wall-clock time. An O(n) algorithm with a huge constant factor can be slower than an O(n log n) algorithm for realistic input sizes.

Misconception 3: "Arrays and linked lists are basically interchangeable — pick whichever." Why it's wrong: They have opposite strengths. Arrays give O(1) index access but O(n) insertion in the middle; linked lists give O(1) insertion (given a node reference) but O(n) access. Correct explanation: Pick based on your dominant operation. Frequent random access with rare insertions → array. Frequent insertions/deletions with rare random access → linked list.

Comparison and Connections

Concept A	Concept B	Key Difference
Array	Linked List	Array gives O(1) access via contiguous memory; linked list gives O(1) insertion via pointers but O(n) access
Stack	Queue	Stack is LIFO (top in, top out); queue is FIFO (rear in, front out)
Linear Data Structure	Non-Linear Data Structure	Linear elements have one predecessor/successor; non-linear elements (trees, graphs) can branch to many
Time Complexity	Space Complexity	Time measures speed of operations; space measures memory used — improving one can worsen the other (a classic trade-off)
Data Structure	Algorithm	A data structure organizes data; an algorithm is the step-by-step process that operates on that data (often relying on a specific structure)
Worst-case complexity	Average-case complexity	Worst-case is a guaranteed upper bound; average-case reflects typical behavior (e.g., hash tables are O(1) average but O(n) worst-case)

Practice Questions

Recall 1: What is the definition of a data structure? Answer guidance: A way of organizing and storing data in memory along with the set of operations (insert, delete, search, traverse) defined on it — not just "a container for values."

Recall 2: Name the two data structures that follow LIFO and FIFO ordering, respectively. Answer guidance: Stack follows LIFO (Last-In-First-Out); Queue follows FIFO (First-In-First-Out).

Understanding 1: Explain why an array gives O(1) access time but a linked list gives O(n) access time. Answer guidance: An array stores elements in contiguous memory, so the address of index i can be computed directly via base_address + i * element_size. A linked list has no such formula — nodes are scattered in memory, so reaching the k-th node requires following next pointers one at a time from the head.

Understanding 2: Why is Big-O notation described as focusing on the "worst case" and why does that matter? Answer guidance: Big-O typically describes an upper bound on cost as input size grows, guaranteeing performance won't get worse than that bound. It matters because it gives a reliability guarantee — for a hash table, average-case is O(1), but knowing the worst case is O(n) (under many collisions) is critical for systems where consistent performance matters, like real-time applications.

Application 1: You're building a music app's "recently played" feature where users can undo their last few plays in reverse order. Which data structure fits, and why? Answer guidance: A stack — the most recently played song should be the first one "undone," matching LIFO behavior. Pushing a song onto the stack when played, popping when undoing, both O(1).

Application 2: A customer support system needs to handle support tickets in the exact order they arrive, ensuring first-come-first-served. Which data structure fits, and why? Answer guidance: A queue — tickets should be processed FIFO, so the first ticket submitted is the first one handled. Enqueue on arrival, dequeue when an agent picks it up.

Analysis 1: A junior developer proposes replacing a program's array (used for fast index-based lookups of daily sales figures) with a linked list "because linked lists are more flexible." Evaluate this decision. Answer guidance: This is likely a poor trade. If the dominant operation is index-based lookup (e.g., "get sales for day 47"), the array's O(1) access is far more valuable than the linked list's easier insertion. Flexibility (easy insert/delete) only matters if the program frequently inserts/removes days from arbitrary positions — for a fixed daily record set, that flexibility isn't being used, so the switch trades away a real performance benefit for an unused one.

Analysis 2: Compare a hash table and a balanced binary search tree (BST) for storing employee records keyed by ID, where you also need to print all employees sorted by ID. Answer guidance: A hash table gives O(1) average lookup/insert/delete but has no inherent ordering — you'd need to extract all keys and sort them, costing O(n log n) whenever you want the sorted list. A balanced BST gives O(log n) lookup/insert/delete but maintains sorted order automatically, so an in-order traversal produces sorted output in O(n) with no extra sort step. If sorted output is needed frequently, the BST's slightly slower per-operation cost is worth it for the ordering guarantee.

FAQ

Q: Do I need to memorize every data structure's Big-O before I can start coding? A: No — start by understanding the reasoning (why array access is fast, why linked list insertion is fast), and the complexities will stick because they'll make sense rather than being rote facts. This page's table is a reference to return to, not a memorization drill.

Q: Is a "data structure" the same thing as an "abstract data type (ADT)"? A: Not quite. An ADT (like "stack" or "queue") defines behavior — what operations exist and what they promise — without specifying implementation. A data structure is the actual implementation (e.g., a stack ADT can be implemented using an array or a linked list underneath).

Q: Why do interviews focus so heavily on data structures? A: Because picking the right one demonstrates whether you understand the trade-offs behind a solution, not just whether you can write code that works. A brute-force O(n²) solution and an optimized O(n log n) solution might produce identical output but behave very differently at scale — interviewers want to see you reason about that difference.

Q: What's the difference between time complexity and actual speed? A: Time complexity describes how the number of operations scales with input size, ignoring hardware and constants. Actual speed depends on hardware, language, and implementation details too. Two O(n) algorithms can have very different real-world speeds even though they share the same complexity class.

Q: Should I learn arrays or linked lists first? A: Arrays first — most languages give you arrays/lists as a built-in feature, and understanding contiguous memory access is the easiest mental model to build the rest of your intuition on. Linked lists (covered in the next chapter) build directly on that foundation by contrasting it.

Q: Why do some structures have "average case" and "worst case" complexities that differ so much? A: It usually comes down to how well the structure's assumptions hold. Hash tables assume a good, evenly-distributing hash function — if that assumption breaks (many collisions), performance degrades toward O(n). Binary search trees assume roughly balanced branching — if data is inserted in sorted order without rebalancing, the tree degenerates into a linked list, and O(log n) becomes O(n).

Quick Revision

• A data structure = organization scheme + the operations allowed on it, not just "a container."
• Primitive types (int, char, boolean) are the building blocks; non-primitive structures (arrays, lists, trees, graphs) are built from them.
• Linear structures (array, linked list, stack, queue): each element has one predecessor and successor.
• Non-linear structures (tree, graph, heap): elements can branch to multiple connections.
• Array: O(1) access, O(n) insert/delete in the middle — contiguous memory.
• Linked List: O(n) access, O(1) insert/delete given a node reference — chained via pointers.
• Stack = LIFO (last in, first out); Queue = FIFO (first in, first out).
• Hash Table: O(1) average for access/insert/delete, but O(n) worst case under heavy collisions.
• Big-O notation measures growth rate of cost as input size increases — not literal seconds, and usually describes the worst case.
• Common complexities from fastest to slowest growth: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
• Recursion and iteration can both implement the same logic; recursion suits hierarchical/branching problems naturally.
• There is no single "best" data structure — only the best one for a given access pattern.

Related Topics

Prerequisites:

• Basic programming concepts (variables, loops, functions)
• Familiarity with a programming language (Python/Java/C++ examples used throughout this series)

Related Topics:

• Algorithm design and analysis
• Object-oriented programming (classes are often used to implement structures like nodes and trees)

Next Topics:

• Arrays and Strings (deep dive into contiguous storage, dynamic arrays, and string algorithms)
• Linked Lists (singly, doubly, and circular linked list implementations)
• Stacks and Queues (implementation details and real applications like expression evaluation and BFS)