Data Structures Terms Every Beginner Should Understand

Linear structures — quick examples:

ARRAY
[10, 20, 30, 40]
- Fast index access: arr[2] → 30
- Inserting in the middle shifts elements

LINKED LIST
10 -> 20 -> 30 -> null
- Fast insert at head: 5 -> 10 -> 20 -> 30
- Slow random access; must walk from head

STACK (LIFO)
push 10, push 20, push 30
pop → 30 (last in, first out)

QUEUE (FIFO)
enqueue 10, enqueue 20, enqueue 30
dequeue → 10 (first in, first out)

When to use each:

ARRAY when:
- You need fast random access by index
- Size is mostly fixed
- You iterate over elements often

LINKED LIST when:
- You insert/delete at the start often
- Size varies a lot
- Memory fragmentation is not a concern

STACK when:
- You need LIFO (undo history, function calls, DFS)
- Matching brackets or tokens

QUEUE when:
- You need FIFO (task queues, printers, BFS)
- Processing in order

Quick rule of thumb:
- Frequent lookups → array
- Frequent inserts at start → linked list
- LIFO → stack
- FIFO → queue

Non-linear structures — visual intuition:

TREE
        10
       /  \
      5    15
     / \   / \
    3   7 12 20
- Each node has at most one parent
- Ordered left-to-right in a BST

GRAPH
A -- B -- C
|    |
D -- E
- Nodes connected by edges
- Edges can be directed or undirected, weighted or not

HASH TABLE
key "apple" → hash → bucket 3
key "banana" → hash → bucket 7
- Keys are hashed to a bucket
- Lookups are O(1) on average
- Collisions are handled with chaining or open addressing

HEAP (min-heap example)
        1
       / \
      3   5
     / \ / \
    8  7 6  10
- Parent is always ≤ children
- Extract min = peek at root, then re-heapify

Hash tables vs trees:

HASH TABLE:
- Best for exact lookups (is this key present?)
- O(1) average
- Not ordered
- Bad for range queries

TREE (BALANCED BST):
- Good for ordered data
- O(log n) lookup, insert, delete
- Supports range queries and sorted traversal
- Foundation of many databases and indexes

When to use which:
- Exact membership → hash table (set, map)
- Sorted order, range queries → balanced tree
- Priority lookups → heap
- Relationships, networks → graph

Real-world mapping:
- Dictionary / cache → hash table
- Database index → B-tree
- Task scheduler by priority → heap
- Friend network / map → graph

Big O in code:

O(1) — constant
def get_first(arr):
    return arr[0]

O(n) — linear
def sum_all(arr):
    total = 0
    for x in arr:
        total += x
    return total

O(n²) — quadratic
def has_duplicate(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

O(log n) — binary search
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Recursion vs iteration:

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

- Elegant, mirrors the problem definition
- Uses call stack; risk of stack overflow
- Not always the fastest

ITERATION
def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

- More memory-efficient
- Often faster in practice
- Sometimes less readable for tree problems

When to use which:
- Trees, graphs, divide-and-conquer → recursion
- Simple loops, large inputs → iteration

Big O view:
- Both factorial examples run in O(n) time
- Recursion uses O(n) extra stack space

Glossary of data structures terms (A-Z):

Array: Fixed-size or dynamic list of items in order.
Balanced Tree: Tree where height is kept small (O(log n) ops).
Big O: Upper bound on growth rate of an algorithm.
BST: Binary Search Tree — left < node < right.
DFS: Depth-First Search — go deep before going wide.
BFS: Breadth-First Search — go wide before going deep.
Graph: Nodes connected by edges; used for networks.
Hash Table: Key-value store using a hash function.
Heap: Tree with a heap property; used for priority queues.
Linked List: Nodes pointing to each other.
LIFO / FIFO: Stack = LIFO; Queue = FIFO.
Node: A single element in a data structure.
O(1), O(log n), O(n), O(n log n), O(n²): Common Big O classes.
Queue: FIFO container.
Recursion: A function calling itself.
Space Complexity: Memory used by an algorithm.
Stack: LIFO container.
Time Complexity: Runtime growth as input grows.
Tree: Parent-child hierarchical structure.

Study tracker — data structures terms:

Week: _____
Terms learned this week:
1. 
2. 
3. 

Code I wrote to practice:
1. 
2. 

Interview-style questions I can now answer:
1. 
2. 

Terms still fuzzy:
1. 
2. 

Next week's focus:
_______________________________

Big O chart — from fastest to slowest:

O(1)         Constant      Array index access
O(log n)     Logarithmic   Binary search
O(n)         Linear        Simple scan
O(n log n)   Linearithmic  Merge sort, heap sort
O(n²)        Quadratic     Nested loops
O(n³)        Cubic         Triple nested loops
O(2^n)       Exponential   Naive recursive fib
O(n!)        Factorial     Brute-force permutations

Rule of thumb:
- Aim for O(n log n) or better when possible
- O(n²) is fine for small inputs, slow for large ones
- O(2^n) and O(n!) only work for tiny inputs