DSA Series Helper: Data Structures Cheat Sheet With Visuals, Big O and Java, Python and Rust Examples

This data structures cheat sheet is the one page you can keep open next to the daily problems in the Tekraze DSA series. Almost every coding problem is really a question about picking the right container among the common data structures. Once you know how these data structures behave, whether a stack, a queue, a hash map or a tree, the solution often falls out on its own.

Think of this data structures cheat sheet as a hack sheet. Each of the data structures gets a short plain explanation, a picture, the costs that matter and one habit that saves you in interviews. Small snippets in Java, Python and Rust come later, and I ran all of them on my machine before they went in.

Also Read: Two Sum in Java, Python and Rust shows the hash map idea from this page in a real problem.

What is a data structure and why does the choice matter?

Data structures are ways of organising data in memory so that certain jobs become cheap. Most data structures are good at something and bad at something else. An array is brilliant at jumping to an index and awkward at inserting in the middle. A hash map finds a key almost instantly but forgets the order.

Picking well is how you turn an O(n²) idea into an O(n) one. That is why this data structures cheat sheet puts the costs next to every structure. Learning data structures is mostly learning these trade offs.

How do arrays and strings work?

An array stores items side by side in memory, so the computer can jump to position i with simple arithmetic. That is why reading a[i] is O(1). The price is that inserting or deleting in the middle shifts everything after it, which is O(n). Appending at the end is cheap on average because dynamic arrays like Java’s ArrayList, Python’s list and Rust’s Vec grow by doubling.

A string is basically an array of characters with extra rules. In Java and Python strings are immutable, so every change builds a new string. Gluing text together inside a loop can quietly turn O(n) into O(n²).

Strings behave like arrays here, so the same data structures rules apply. Use a StringBuilder in Java, a list followed by join in Python, or a String with push_str in Rust. Rust strings are UTF-8, so you cannot index them by character directly.

Arrays pair naturally with a single pass trick. Our Best Time to Buy and Sell Stock solution walks the array once while remembering the lowest price so far, which is a good example of getting O(n) from an array without any extra structure. Arrays are the simplest of all data structures, and most others are built on top of them.

When should you pick a linked list instead?

A liA linked list is a chain of nodes where every node holds a value and a pointer to the next node. There is no index, so reaching the 50th item means walking 50 steps, which is O(n). In return, inserting or deleting next to a node you already hold is O(1) because you only rewire pointers and nothing shifts.

• Singly linked nodes know only the next node.
• Doubly linked nodes also know the previous one, so you can walk both ways and delete a node you already hold.
• Dummy head trick: add a fake node in front of the list so that inserting or deleting the first real node needs no special case.
• Fast and slow pointers: move one pointer two steps and another one step to find the middle or detect a cycle.

In daily work arrays usually win because they are friendlier to the CPU cache. Linked lists mostly show up in interview questions and as the building block inside other data structures.

How do a stack and a queue behave?

A stack is like a pile of plates. You add to the top and you remove from the top, so the last item in is the first item out (LIFO). Push, pop and peek are all O(1). Stacks are among the data structures you already use daily. They power the undo button, the browser back button, the function call stack and bracket matching. If you see a problem about matching parentheses or the next greater element, think stack first.

A queue is like a line at a ticket counter. You join at the back and leave from the front, so the first in is the first out (FIFO). Enqueue and dequeue are O(1). Queues drive task schedulers, print jobs and level by level tree walks. Breadth first search is built on a queue. These two data structures look alike, but they hand items back in opposite order.

What are a deque and a priority queue?

• A deque (double ended queue) lets you add and remove at both ends in O(1). It can act as a stack or a queue, which is why Java’s ArrayDeque, Python’s collections.deque and Rust’s VecDeque are the go to choice for both. It is also the tool for sliding window maximum problems. Both of these data structures are less famous than stacks, yet they solve a lot of interview problems.
• A priority queue always gives you the smallest or largest item first instead of the oldest. Under the hood it is almost always a heap, so push and pop cost O(log n) while peeking at the top is O(1).

How does a hash map or hash set find things so quickly?

A hash map runs your key through a hash function to get a number, then uses that number to pick a bucket. Looking up the key means going straight to that bucket, so insert, lookup and delete are O(1) on average. If two keys land in the same bucket (a collision) they simply share it, and a very unlucky map can slow down to O(n).

A hash map stores key and value pairs, while a hash set stores only keys and answers one question: have I seen this before? Our Two Sum post is the classic hash map story, where we store each number and its index and look for the missing partner. Contains Duplicate is the hash set story, where adding to a set and checking membership replaces a slow nested loop.

• Hash maps do not keep order. Use a sorted map (Java TreeMap, Rust BTreeMap) when you need keys in order.
• Keys must be hashable and should not change after you insert them. Python lists cannot be keys, tuples can.
• Reaching for a map or set is the single most common way to cut an O(n²) solution down to O(n).

What are a binary tree and a binary search tree?

A tree is a set of nodes connected from a single root downwards. In a binary tree every node has at most two children, called left and right. A node with no children is a leaf. The height is the number of levels from the root to the deepest leaf. Trees are non linear data structures, so they model hierarchies like folders on your disk.

A binary search tree (BST) adds one rule. Everything in the left subtree is smaller than the node and everything in the right subtree is bigger. Searching becomes a guessing game where each comparison discards half the tree, so a balanced BST gives O(log n) search, insert and delete.

If you insert already sorted data into a plain BST it grows into a stick shaped like a linked list and every operation becomes O(n). Self balancing trees such as red black trees avoid that, which is why library data structures like TreeMap use them. Java’s TreeMap is one. Rust’s BTreeMap is a B tree.

Which tree walks should you know?

• Inorder (left, node, right) gives sorted output for a BST.
• Preorder (node, left, right) is handy for copying or saving a tree.
• Postorder (left, right, node) works when children must be handled before the parent, like deleting a tree.
• Level order visits level by level with a queue.

What is a heap and how does it relate to a priority queue?

A heap is a nearly complete binary tree where every parent is smaller than its children (a min heap) or bigger (a max heap). It is not fully sorted. It only promises that the best item sits at the top. That small promise is cheap to keep, so pushing and popping cost O(log n) and peeking is O(1).

Because the tree is complete, it fits neatly into an array. For the item at index i, the left child sits at 2i + 1, the right child at 2i + 2 and the parent at (i − 1) / 2, using integer division. Building a heap from n items in one go takes only O(n). A heap is one of the data structures that hides inside a priority queue.

Reach for a heap when a problem says top k, kth largest, merge sorted lists or always process the cheapest next. Keep a min heap of size k to track the k largest items. Java’s PriorityQueue and Python’s heapq are min heaps. Rust’s BinaryHeap is a max heap, so wrap values in Reverse to flip it.

How does a graph work and what are BFS and DFS?

A graph is a set of nodes (vertices) joined by edges. Roads between cities, friends on a social app and links between web pages are all graphs. Edges can be directed or undirected and can carry weights. A tree is just a graph with no cycles. Graphs are the most general of the data structures on this page, since lists and trees are special cases.

Should you store a graph as an adjacency list or a matrix?

	Adjacency list	Adjacency matrix
What it is	Each node keeps a list of its neighbours	A V by V grid of 0 and 1 (or weights)
Space	O(V + E)	O(V²)
Is there an edge between a and b?	O(degree of a)	O(1)
Walk all neighbours of a node	O(degree)	O(V)
Best for	Sparse graphs, most interview problems	Dense graphs or very fast edge checks

What is the difference between BFS and DFS?

	BFS (breadth first)	DFS (depth first)
Idea	Visit all neighbours, then their neighbours	Go as deep as possible, then backtrack
Uses	A queue	A stack or recursion
Time	O(V + E) with a list	O(V + E) with a list
Extra space	Up to O(V) for the queue	Up to O(V) for the stack
Great for	Shortest path in an unweighted graph, level by level	Cycle detection, connected parts, paths, backtracking

In the picture above, starting at A, BFS visits A B C D E F because it finishes each layer first. DFS visits A B D E C F because it dives down the B branch before coming back to C. Both are ways to walk the same data structures, and you should always keep a visited set, otherwise a graph with a cycle will loop forever.

What is a trie and when is it useful?

A trie (say “try”), also called a prefix tree, stores words one letter per node. Words that start the same share a path, so cat and car walk the same first two nodes. A flag on a node says that a word ends there.

Insert, search and starts with all cost O(L), where L is the length of the word, no matter how many words are stored. That makes tries perfect for autocomplete, spell checkers and word search puzzles. The trade is memory, because every letter becomes a node. Not all data structures are cheap on space. If you only need exact matches, a hash set is simpler. Among data structures for text, the trie is the specialist.

python

class TrieNode:
    def __init__(self):
        self.kids = {}          # letter -> TrieNode
        self.end = False        # does a word finish here?

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):     # O(L)
        node = self.root
        for ch in word:
            node = node.kids.setdefault(ch, TrieNode())
        node.end = True

    def starts_with(self, prefix):   # O(L)
        node = self.root
        for ch in prefix:
            if ch not in node.kids:
                return False
            node = node.kids[ch]
        return True

t = Trie()
for w in ["cat", "car", "tea"]:
    t.insert(w)
print(t.starts_with("ca"), t.starts_with("to"))  # True False

What do these structures look like in Java, Python and Rust?

This data structures cheat sheet includes one small program per language that uses a stack, a queue, a BST, a min heap and a graph with BFS and DFS. The graph is the same A to F graph from the picture. Reading the same data structures in three languages shows what changes (the syntax) and what stays the same (the idea). All three print the same results: a stack pop of C, a queue dequeue of A, a sorted BST walk of 1 3 4 6 7 8 10 14, heap pops of 2 4 5 6 7 9, BFS order A B C D E F and DFS order A B D E C F.

Java

java

import java.util.*;

public class Structures {
    static class Node {                    // binary tree / BST node
        int val; Node left, right;
        Node(int val) { this.val = val; }
    }

    static Node insert(Node root, int v) { // BST insert, O(log n) average
        if (root == null) return new Node(v);
        if (v < root.val) root.left = insert(root.left, v);
        else root.right = insert(root.right, v);
        return root;
    }

    static void inorder(Node n, List<Integer> out) { // sorted order for a BST
        if (n == null) return;
        inorder(n.left, out); out.add(n.val); inorder(n.right, out);
    }

    static void dfs(Map<String, List<String>> g, String cur, Set<String> seen, List<String> order) {
        seen.add(cur); order.add(cur);
        for (String nxt : g.get(cur))
            if (!seen.contains(nxt)) dfs(g, nxt, seen, order);
    }

    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();      // stack: push and pop at the same end
        stack.push("A"); stack.push("B"); stack.push("C");
        System.out.println("stack pop: " + stack.pop());

        Queue<String> queue = new ArrayDeque<>();      // queue: add at back, remove from front
        queue.offer("A"); queue.offer("B"); queue.offer("C");
        System.out.println("queue dequeue: " + queue.poll());

        Node root = null;
        for (int v : new int[]{8, 3, 10, 1, 6, 14, 4, 7}) root = insert(root, v);
        List<Integer> sorted = new ArrayList<>(); inorder(root, sorted);
        System.out.println("bst inorder: " + sorted);

        PriorityQueue<Integer> heap = new PriorityQueue<>(); // min heap
        for (int v : new int[]{5, 9, 2, 7, 4, 6}) heap.offer(v);
        List<Integer> popped = new ArrayList<>();
        while (!heap.isEmpty()) popped.add(heap.poll());
        System.out.println("heap pops: " + popped);

        Map<String, List<String>> g = new LinkedHashMap<>(); // adjacency list
        g.put("A", List.of("B", "C")); g.put("B", List.of("A", "D", "E")); g.put("C", List.of("A", "F"));
        g.put("D", List.of("B")); g.put("E", List.of("B")); g.put("F", List.of("C"));

        List<String> bfs = new ArrayList<>();
        Queue<String> q = new ArrayDeque<>(List.of("A")); Set<String> seen = new HashSet<>(List.of("A"));
        while (!q.isEmpty()) {
            String cur = q.poll(); bfs.add(cur);
            for (String nxt : g.get(cur)) if (seen.add(nxt)) q.offer(nxt);
        }
        System.out.println("bfs: " + bfs);

        List<String> dfs = new ArrayList<>(); dfs(g, "A", new HashSet<>(), dfs);
        System.out.println("dfs: " + dfs);
    }
}

Python

python

from collections import deque
import heapq

class Node:                                  # binary tree / BST node
    def __init__(self, val):
        self.val, self.left, self.right = val, None, None

def insert(root, v):                         # BST insert, O(log n) average
    if root is None:
        return Node(v)
    if v < root.val:
        root.left = insert(root.left, v)
    else:
        root.right = insert(root.right, v)
    return root

def inorder(n, out):                         # sorted order for a BST
    if n:
        inorder(n.left, out); out.append(n.val); inorder(n.right, out)
    return out

def dfs(g, cur, seen, order):
    seen.add(cur); order.append(cur)
    for nxt in g[cur]:
        if nxt not in seen:
            dfs(g, nxt, seen, order)
    return order

stack = []                                   # stack: a list works, push and pop at the end
stack.extend(["A", "B", "C"])
print("stack pop:", stack.pop())

queue = deque(["A", "B", "C"])               # queue: deque gives O(1) at both ends
print("queue dequeue:", queue.popleft())

root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7]:
    root = insert(root, v)
print("bst inorder:", inorder(root, []))

heap = []                                    # min heap
for v in [5, 9, 2, 7, 4, 6]:
    heapq.heappush(heap, v)
print("heap pops:", [heapq.heappop(heap) for _ in range(len(heap))])

g = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"], "D": ["B"], "E": ["B"], "F": ["C"]}
bfs, q, seen = [], deque(["A"]), {"A"}
while q:
    cur = q.popleft(); bfs.append(cur)
    for nxt in g[cur]:
        if nxt not in seen:
            seen.add(nxt); q.append(nxt)
print("bfs:", bfs)
print("dfs:", dfs(g, "A", set(), []))

Rust

rust

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque};

struct Node {                                  // binary tree / BST node
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

fn insert(root: Option<Box<Node>>, v: i32) -> Option<Box<Node>> { // BST insert
    match root {
        None => Some(Box::new(Node { val: v, left: None, right: None })),
        Some(mut n) => {
            if v < n.val { n.left = insert(n.left.take(), v); }
            else { n.right = insert(n.right.take(), v); }
            Some(n)
        }
    }
}

fn inorder(n: &Option<Box<Node>>, out: &mut Vec<i32>) { // sorted order for a BST
    if let Some(node) = n {
        inorder(&node.left, out); out.push(node.val); inorder(&node.right, out);
    }
}

fn dfs<'a>(g: &HashMap<&'a str, Vec<&'a str>>, cur: &'a str, seen: &mut HashSet<&'a str>, order: &mut Vec<&'a str>) {
    seen.insert(cur); order.push(cur);
    for &nxt in &g[cur] {
        if !seen.contains(nxt) { dfs(g, nxt, seen, order); }
    }
}

fn main() {
    let mut stack = vec!["A", "B", "C"];       // stack: Vec push and pop at the end
    println!("stack pop: {}", stack.pop().unwrap());

    let mut queue: VecDeque<&str> = VecDeque::from(vec!["A", "B", "C"]); // queue: VecDeque
    println!("queue dequeue: {}", queue.pop_front().unwrap());

    let mut root = None;
    for v in [8, 3, 10, 1, 6, 14, 4, 7] { root = insert(root, v); }
    let mut sorted = Vec::new(); inorder(&root, &mut sorted);
    println!("bst inorder: {:?}", sorted);

    let mut heap = BinaryHeap::new();          // Rust heap is a max heap, Reverse makes it a min heap
    for v in [5, 9, 2, 7, 4, 6] { heap.push(Reverse(v)); }
    let mut popped = Vec::new();
    while let Some(Reverse(v)) = heap.pop() { popped.push(v); }
    println!("heap pops: {:?}", popped);

    let g: HashMap<&str, Vec<&str>> = HashMap::from([
        ("A", vec!["B", "C"]), ("B", vec!["A", "D", "E"]), ("C", vec!["A", "F"]),
        ("D", vec!["B"]), ("E", vec!["B"]), ("F", vec!["C"]),
    ]);
    let (mut bfs, mut q, mut seen) = (Vec::new(), VecDeque::from(vec!["A"]), HashSet::from(["A"]));
    while let Some(cur) = q.pop_front() {
        bfs.push(cur);
        for &nxt in &g[cur] { if seen.insert(nxt) { q.push_back(nxt); } }
    }
    println!("bfs: {:?}", bfs);

    let mut order = Vec::new(); dfs(&g, "A", &mut HashSet::new(), &mut order);
    println!("dfs: {:?}", order);
}

Which built in type matches each structure?

Structure	Java	Python	Rust
Array or list	int[], ArrayList	list	Vec, [T; N]
Stack	ArrayDeque (push, pop)	list (append, pop)	Vec (push, pop)
Queue or deque	ArrayDeque, LinkedList	collections.deque	VecDeque
Priority queue	PriorityQueue (min)	heapq (min)	BinaryHeap (max)
Hash map	HashMap	dict	HashMap
Hash set	HashSet	set	HashSet
Sorted map	TreeMap	none built in	BTreeMap
Linked list	LinkedList	none built in	LinkedList

What does the Big O cheat table look like?

This is the table to memorise. Costs are average cases unless noted. If any column feels unclear, the Big O helper post explains how these numbers are calculated, including amortized cost and why hash maps are O(1) on average but O(n) in the worst case.

Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n), O(log n) if sorted	O(n), O(1) at end	O(n)	O(n)
Linked list	O(n)	O(n)	O(1) at head or known node	O(1) at head or known node	O(n)
Stack	O(n)	O(n)	O(1) push	O(1) pop	O(n)
Queue / Deque	O(n)	O(n)	O(1)	O(1)	O(n)
Hash map / set	n/a	O(1), worst O(n)	O(1), worst O(n)	O(1), worst O(n)	O(n)
BST (balanced)	n/a	O(log n)	O(log n)	O(log n)	O(n)
BST (skewed)	n/a	O(n)	O(n)	O(n)	O(n)
Heap	O(1) top only	O(n)	O(log n)	O(log n) top	O(n)
Graph, adjacency list	n/a	O(V + E) traversal	O(1) add edge	O(E) remove edge	O(V + E)
Graph, adjacency matrix	O(1) edge check	O(V²) traversal	O(1) add edge	O(1) remove edge	O(V²)
Trie	n/a	O(L)	O(L)	O(L)	O(total letters)

How do you pick the right structure for a problem?

Ask what the problem does most often, then choose the structure where that action is cheapest. Here is a quick decision table you can run through in your head.

If the problem says or needs	Reach for	Why
Look up by index, or loop through in order	Array or list	O(1) access and cache friendly
Have I seen this before, or count things	Hash set or hash map	O(1) average lookup
Undo, matching brackets, next greater item	Stack	Last in, first out
Process in arrival order, level by level, shortest path in an unweighted graph	Queue with BFS	First in, first out
Add or remove at both ends, sliding window	Deque	O(1) at both ends
Top k, kth largest, always the next smallest	Heap or priority queue	Best item on top in O(log n)
Keep keys sorted, find the next bigger value	Balanced BST (TreeMap, BTreeMap)	O(log n) with order
Prefix search or autocomplete	Trie	O(L) per word
Connections, paths, networks, dependencies	Graph with BFS or DFS	Models relationships
Frequent inserts and deletes next to a known node	Linked list	O(1) pointer changes

What are the tips and tricks for using these structures in interviews?

• Name the operation first. Say out loud what you will do most often, such as look up, insert, remove the smallest or walk in order, then pick the structure.
• Trade memory for time. A hash map or set is the usual way to turn a nested loop into a single pass.
• Think in patterns. Most problems repeat a handful of ideas, which we cover in our post on patterns instead of memorization.
• Stack means nesting, queue means levels. Brackets and undo use stacks. Layer by layer walks use queues.
• Always use a visited set in graphs and mark nodes when you add them to the queue, not when you pop them.
• Sorted input is a hint. Think binary search, two pointers or a BST.
• Check the edges. Empty input, a single node, duplicates and cycles break more solutions than clever tricks fix.
• Say the cost. Finish every answer with time and space, and mention the trade you made.

What are the common mistakes beginners make?

• Using a list as a queue and removing from the front, which is O(n) in Python lists and Java ArrayList. Use a deque.
• Forgetting that a plain BST can become lopsided and slow.
• Treating hash map lookups as always O(1) and ignoring collisions.
• Skipping the visited set in BFS or DFS and looping forever on a cycle.
• Mutating a list while looping over it.
• Picking a fancy structure when an array and a loop would do.

How should you use this cheat sheet with the DSA series?

Read it once from top to bottom, then come back to the decision table whenever a new problem starts. Try to name the structure before you read the solution. The daily posts already use these ideas, like a hash map in Two Sum, a hash set in Contains Duplicate and a single array pass in Best Time to Buy and Sell Stock, and the Big O helper post explains every complexity line that you saw above.

Frequently asked questions

Which data structures should I learn first for coding interviews?

Start with arrays, strings, hash maps and sets, then stacks and queues. After that learn linked lists, trees, heaps and graphs, and finish with tries. Those data structures cover most interview questions, and that order follows how often they show up.

What is the difference between a stack and a queue?

A stack removes the newest item first (last in, first out) and a queue removes the oldest item first (first in, first out). Both data structures support add and remove in O(1).

When should I use BFS and when DFS?

Use BFS when you need the shortest path in an unweighted graph or want to go level by level. Use DFS for exploring all paths, detecting cycles, finding connected parts and backtracking.

Is a hash map always O(1)?

No. Lookups, inserts and deletes are O(1) on average, but many collisions can push them to O(n) in the worst case. In practice a good hash function keeps it fast.

What is the difference between a heap and a binary search tree?

A heap only guarantees that the smallest or largest item is on top, so it is great for priority queues. A BST keeps all items ordered, so it supports sorted walks and range searches but needs balancing to stay fast. The two data structures solve different problems.