Data Structures Basics Every Beginner Must Know

DSA · Beginner Guide · Interview Prep

Data Structures Basics Every Beginner Must Know

SECTION 01What data structures actually are

A data structure is a way of organizing data in memory so that specific operations — insert, search, delete, traverse — are fast and predictable. The same data can be stored in many ways, and the choice decides whether your program finishes in milliseconds or minutes.

Everyday analogies that actually stick:

SECTION 02Big-O — why complexity matters

Big-O describes how an operation's cost grows as the input size n grows. It is not about exact milliseconds — it is about the shape of the curve. Two programs can be identical on 10 items and wildly different on 10 million.

SECTION 03Arrays and linked lists

These are the two foundational linear structures — data laid out in a sequence. They differ in how memory is arranged, and that single difference drives every performance trade-off.

Arrays store elements in a contiguous block of memory. Because the computer knows the start address and the size of each element, index access is pure arithmetic — O(1). The cost is insertion and deletion in the middle: everything after the gap must shift, which is O(n).

Linked lists store each element in a node that also holds a pointer to the next node. Inserting at the head is O(1) — just rewire two pointers. But reaching the 500th element means walking 500 links, which is O(n). There is no index math.

# Array — Python's list is a dynamic array
arr = [12, 7, 4, 9, 2]
print(arr[2])         # 4  → O(1) index access
arr.append(5)         # O(1) amortised — grows at the end
arr.insert(0, 99)     # O(n) — every element shifts right

# Linked list — a minimal node in Python
class Node:
    def __init__(self, val):
        self.val  = val
        self.next = None

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# Insert at head — O(1)
new = Node(0)
new.next = head
head = new

SECTION 04Stacks, queues, and hash maps

These three cover the majority of day-to-day programming. If you learn only four structures, learn arrays plus these three.

Stack (LIFO) — last in, first out. Push adds to the top, pop removes from the top. Both O(1). Used for undo history, the function call stack, balanced-parentheses checks, and depth-first search.

Queue (FIFO) — first in, first out. Enqueue at the back, dequeue from the front. Both O(1) with the right implementation. Used for printer queues, breadth-first search, task scheduling and message queues.

Hash map — a key-value store. A hash function turns the key into an integer, which maps to a bucket in an array. Average lookup, insert and delete are all O(1). Worst case is O(n) if every key collides into one bucket, but good implementations resize to avoid that. A set is a hash map with keys but no values — perfect for uniqueness and membership tests.

# Stack — LIFO
stack = []
stack.append("a")        # push
stack.append("b")
print(stack.pop())      # "b" — last in, first out

# Queue — FIFO (use deque, not list)
from collections import deque
q = deque()
q.append("task1")       # enqueue
q.append("task2")
print(q.popleft())     # "task1" — first in, first out

# Hash map — frequency counting
words  = ["apple", "banana", "apple", "cherry"]
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1

print(counts)          # {'apple': 2, 'banana': 1, 'cherry': 1}

# Set — O(1) membership checks
seen = set()
for w in words:
    if w in seen:
        print("duplicate:", w)
    seen.add(w)

SECTION 05Trees and graphs

Trees and graphs handle hierarchical and connected data — the shapes that show up in file systems, databases, social networks and maps.

Trees are nodes with children and no cycles. A binary tree has at most two children per node. A binary search tree keeps the left subtree smaller and the right subtree larger, so search is O(log n) when balanced — but degrades to O(n) when skewed. A heap keeps the smallest (or largest) element at the root and powers priority queues. Real uses: file systems, database indexes (B-trees), expression parsing, autocomplete (tries).

Graphs are nodes (vertices) connected by edges — directed or undirected, weighted or unweighted. They're stored as an adjacency list (sparse, memory-efficient) or an adjacency matrix (dense, O(1) edge checks). Traversal is BFS using a queue, or DFS using a stack or recursion. Real uses: social networks, maps, dependency graphs, recommendation engines.

SECTION 06Interview Q&A — data structures

SECTION 07Test yourself — data structures

SECTION 08Frequently asked questions

SECTION 09Related reads