Core Data Structures (Beginner Friendly)

If you're starting DSA, learn when to use each structure before memorizing code.

1) Array / List

• Why use: fast index access
• Where used: storing ordered items, prefix sums, sliding window
• Tradeoff: insert/delete in middle is O(n)

arr = [10, 20, 30]
arr.append(40)      # add end
first = arr[0]      # O(1) access

const arr = [10, 20, 30];
arr.push(40);
const first = arr[0];

import java.util.*;
List<Integer> arr = new ArrayList<>(List.of(10, 20, 30));
arr.add(40);
int first = arr.get(0);

2) Linked List

• Why use: efficient insert/delete when you already have node reference
• Where used: LRU cache internals, pointer problems, interview fundamentals
• Tradeoff: no random access, traversal is O(n)

class Node:
    def __init__(self, v, nxt=None):
        self.v, self.next = v, nxt
head = Node(1, Node(2, Node(3)))

class Node {
  constructor(v, next = null) { this.v = v; this.next = next; }
}
const head = new Node(1, new Node(2, new Node(3)));

class Node {
  int v; Node next;
  Node(int v, Node next) { this.v = v; this.next = next; }
}
Node head = new Node(1, new Node(2, new Node(3, null)));

3) Stack (LIFO)

• Why use: reverse order processing
• Where used: parentheses validation, DFS, recursion simulation

st = []
st.append(5)     # push
top = st.pop()   # pop

const st = [];
st.push(5);
const top = st.pop();

Deque<Integer> st = new ArrayDeque<>();
st.push(5);
int top = st.pop();

4) Queue (FIFO)

• Why use: process items in arrival order
• Where used: BFS, task scheduling, buffering

from collections import deque
q = deque([1, 2])
q.append(3)
front = q.popleft()

const q = [1, 2];
q.push(3);
const front = q.shift();

Queue<Integer> q = new ArrayDeque<>();
q.offer(1); q.offer(2); q.offer(3);
int front = q.poll();

5) Hash Map / Dictionary

• Why use: fast key-value lookup
• Where used: counting, caching, frequency maps, complements

freq = {}
for x in [1,2,2]:
    freq[x] = freq.get(x, 0) + 1

const freq = new Map();
[1,2,2].forEach(x => freq.set(x, (freq.get(x) ?? 0) + 1));

Map<Integer, Integer> freq = new HashMap<>();
for (int x : new int[]{1,2,2}) {
  freq.put(x, freq.getOrDefault(x, 0) + 1);
}

6) Hash Set

• Why use: fast membership checks
• Where used: duplicate detection, visited nodes, unique elements

seen = set([1, 2])
seen.add(3)
has_two = 2 in seen

const seen = new Set([1, 2]);
seen.add(3);
const hasTwo = seen.has(2);

Set<Integer> seen = new HashSet<>(List.of(1, 2));
seen.add(3);
boolean hasTwo = seen.contains(2);

7) Tree (Binary Tree / BST)

• Why use: hierarchical data
• Where used: expression parsing, file systems, range queries, search

class TreeNode:
    def __init__(self, v, l=None, r=None):
        self.v, self.left, self.right = v, l, r
root = TreeNode(2, TreeNode(1), TreeNode(3))

class TreeNode {
  constructor(v, left = null, right = null) {
    this.v = v; this.left = left; this.right = right;
  }
}
const root = new TreeNode(2, new TreeNode(1), new TreeNode(3));

class TreeNode {
  int v; TreeNode left, right;
  TreeNode(int v, TreeNode l, TreeNode r) { this.v = v; this.left = l; this.right = r; }
}
TreeNode root = new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null));

8) Heap / Priority Queue

• Why use: repeatedly get min/max efficiently
• Where used: top-k, scheduling, shortest path (Dijkstra)

import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
mn = heapq.heappop(h)  # 1

// JS has no built-in heap; use a library or custom class for production.
// Concept: keep smallest element at index 0.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1);
int mn = pq.poll(); // 1

9) Graph (Adjacency List)

• Why use: model connections/relationships
• Where used: networks, routes, prerequisites, social links

g = {1: [2,3], 2: [1], 3: [1]}

const g = new Map([[1, [2,3]], [2, [1]], [3, [1]]]);

Map<Integer, List<Integer>> g = new HashMap<>();
g.put(1, Arrays.asList(2,3));
g.put(2, Arrays.asList(1));
g.put(3, Arrays.asList(1));

Quick Beginner Rule

• Need fast lookup by key → HashMap
• Need unique items / visited → HashSet
• Need first-in-first-out → Queue
• Need last-in-first-out → Stack
• Need top-k/min/max repeatedly → Heap
• Need hierarchy → Tree
• Need connections/pathfinding → Graph

Beginner Guide: Arrays & Strings

• Start here first. Most interview problems reduce to this topic.
• Main question: contiguous segment or arbitrary picks?

Theory

• Contiguous segment → sliding window or prefix sums
• Sorted pair/triplet search → two pointers

Example

# fixed-size window max sum
arr, k = [2,1,5,1,3,2], 3
win = sum(arr[:k]); best = win
for i in range(k, len(arr)):
    win += arr[i] - arr[i-k]
    best = max(best, win)

Common pitfalls: off-by-one, duplicate handling, missing empty/single-element edge cases.

Arrays & Strings

Arrays store elements in contiguous memory — O(1) access, O(n) insert/delete in middle.

Complexity Cheatsheet

Pattern 1: Two Pointers

Eliminates nested loops. Move pointers inward or in same direction.

def two_sum_sorted(arr, target):
    l, r = 0, len(arr) - 1
    while l < r:
        s = arr[l] + arr[r]
        if s == target: return [l, r]
        elif s < target: l += 1
        else: r -= 1
    return []

# 3Sum: sort, fix one, two-pointer rest
def three_sum(nums):
    nums.sort(); res = []
    for i, v in enumerate(nums):
        if i > 0 and v == nums[i-1]: continue
        l, r = i+1, len(nums)-1
        while l < r:
            s = v + nums[l] + nums[r]
            if s == 0: res.append([v,nums[l],nums[r]]); l+=1
            elif s < 0: l += 1
            else: r -= 1
    return res

Pattern 2: Sliding Window

Maintain a window; expand right, shrink left based on a constraint.

def longest_no_repeat(s):
    seen = {}; l = res = 0
    for r, ch in enumerate(s):
        if ch in seen and seen[ch] >= l:
            l = seen[ch] + 1
        seen[ch] = r
        res = max(res, r - l + 1)
    return res

def max_sum_k(arr, k):
    win = sum(arr[:k]); best = win
    for i in range(k, len(arr)):
        win += arr[i] - arr[i-k]
        best = max(best, win)
    return best

Pattern 3: Prefix Sums

Precompute for O(1) range queries. Essential for subarray sum problems.

def build_prefix(arr):
    pre = [0] * (len(arr)+1)
    for i,v in enumerate(arr): pre[i+1] = pre[i]+v
    return pre
# Range sum [l,r] = pre[r+1] - pre[l]

# Subarray sum equals k:
def subarray_sum(nums, k):
    count = 0; cur = 0; seen = {0:1}
    for n in nums:
        cur += n
        count += seen.get(cur-k, 0)
        seen[cur] = seen.get(cur,0)+1
    return count

Pattern 4: Kadane's Algorithm

Max subarray in O(n). Reset when running sum goes negative.

def max_subarray(nums):
    cur = best = nums[0]
    for n in nums[1:]:
        cur = max(n, cur+n)
        best = max(best, cur)
    return best

Key heuristics:

• Sorted input? → binary search or two pointers
• Subarray/substring? → sliding window or prefix sums
• Pairs/triplets? → hash map or two pointers
• Matrix? → treat as 1D: index = i*cols + j