Graphs are rarely given to you as a clean object — you're usually handed an edge list or a grid and have to build the representation yourself under time pressure. This section is about the mechanical choices in that setup (adjacency list vs matrix, hashed keys vs dense integer indices, recursion vs an explicit stack) in Python, Java, Go, and JavaScript, and their real performance/memory consequences, not about the traversal or shortest-path algorithms themselves.
Language Verdict: Pros, Cons & Recommendation
defaultdict(list) turns adjacency-list construction into a single .append(), no KeyError/setdefault dancecollections.deque gives an O(1) popleft() BFS queue straight out of the standard libraryheapq ships in the standard library for Dijkstra/Prim with no extra dependency- Tuples as
(neighbor, weight) pairs and (row, col) node ids are hashable and usable as keys with zero ceremony
RecursionError hits around ~1000 frames deep — the tightest limit of the three for recursive DFS over long paths- Every hashed structure (
dict, set) pays real per-op hashing cost that a dense array sidesteps entirely
Map.computeIfAbsent(u, k -> new ArrayList<>()) is a clean, idiomatic one-liner for adjacency-list constructionPriorityQueue and ArrayDeque are both built in, covering Dijkstra's heap and BFS's queue with no extra imports- Primitive
int[]/boolean[] arrays give zero-boxing, zero-hashing dense storage for adjacency matrices and visited sets record Edge(int neighbor, int weight) gives named-field readability for weighted edges with minimal boilerplate
HashMap<Integer, List<Integer>> boxes every node-id lookup to Integer, real overhead in a hot BFS/DFS loop- Generic array creation (
new List[n]) needs an unchecked cast — a persistent, mildly ugly wart
map[int][]int{} plus adj[u] = append(adj[u], v) builds an adjacency list with no computeIfAbsent — nil-slice append is well-definedmake([][]int, n) / make([]bool, n) give dense, unboxed storage for 0..n-1 ids[2]int and structs with comparable fields are valid map keys — grid coordinates need no string serialization- A slice as a BFS queue is one line to write; recursive DFS closures use a named
var dfs func(...)
q = q[1:] is O(1) but leaks the backing-array prefix — no stdlib deque (container/list is the wrong default)container/heap is clunky compared to Python's heapq or Java's PriorityQueue — Dijkstra needs a custom heap typemake([][]int, n) leaves nil inner rows; forgetting the per-row make panics on first write
- A plain
Array of arrays for dense 0..n-1 adjacency lists is the fastest option, no hashing at all Uint8Array/Int32Array typed arrays give cache-friendly, boxing-free storage for visited flags and flat adjacency matricesMap correctly distinguishes numeric vs. string keys, unlike plain-object property coercion
- No built-in
PriorityQueue/heap at all — Dijkstra requires hand-rolling a binary heap or falling back to a slower sorted-array substitute - No built-in
Deque, so BFS needs the head-pointer-over-a-growing-array trick to avoid Array.prototype.shift()'s O(n) cost - Object keys are compared by reference, so grid/coordinate nodes need manual string serialization (e.g. a `
${row},${col} ` key) to use as map keys
Recommendation: Python remains the typical DSA default (defaultdict + deque + heapq). Java's PriorityQueue/ArrayDeque/computeIfAbsent are the most complete stdlib. Go is a strong nice-to-have — maps of slices and a slice BFS queue are clean — but q = q[1:] leaks the prefix and container/heap is clunky. JavaScript has no built-in heap, so budget time to hand-roll one before reaching for Dijkstra.
Coding Mechanics, Side by Side
When node ids are guaranteed to be a contiguous 0..n-1 range, indexing directly into an array/list is faster than hashing through a map — no hash computation, no boxing, no bucket lookup. Use the map/dict form when node ids are sparse, non-integer, or unknown ahead of time.
from collections import defaultdict
# Hashed form: works for any hashable node id
adj = defaultdict(list)
adj[u].append(v) # no KeyError even if u is new
# Dense form: nodes are 0..n-1
adj = [[] for _ in range(n)]
adj[u].append(v)
defaultdict(list) avoids the classic KeyError/setdefault dance on first insert — plain dict needs adj.setdefault(u, []).append(v) or an explicit if u not in adj check. The dense list-of-lists form skips hashing entirely and is the better default whenever nodes are known to be 0..n-1.
The only mechanical difference between directed and undirected graphs is whether you push the edge in both directions — the rest of the loop is identical in every language.
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # omit this line for a directed graph
One for over the edge list, one or two .append() calls per edge depending on directedness. Nothing algorithmic here — this is pure setup boilerplate you should be able to write without thinking.
This is the same hashed-vs-dense trade-off as the adjacency list, applied to the visited check that runs on every single node dequeued — a real, measurable performance difference on dense integer-id graphs.
# Hashed: works for any hashable node id
visited = set()
if u not in visited:
visited.add(u)
# Dense: nodes are 0..n-1
visited = [False] * n
if not visited[u]:
visited[u] = True
set() membership is O(1) average but pays a hash computation on every in/add call. A bool list indexed by node id is strictly faster for dense integer ids since it's a direct memory read with no hashing — worth mentioning out loud in an interview as the 'if ids are 0..n-1' optimization.
Same queue-performance trap as the Stacks, Queues & Deques section — see that section for the full explanation of why naive list-front operations are O(n). Here's just the graph-BFS-specific idiom in each language.
from collections import deque
q = deque([start])
visited = {start}
while q:
u = q.popleft()
for v in adj[u]:
if v not in visited:
visited.add(v)
q.append(v)
deque.popleft() is O(1). Never write queue.pop(0) on a plain list for BFS — that's O(n) per dequeue, turning the whole traversal quadratic (see Stacks, Queues & Deques for why).
Same recursion-depth caveat as Trees & Recursion Mechanics applies here — a graph with a long simple path (e.g. a linked-list-shaped graph of a few thousand nodes) can blow the call stack in a recursive DFS well before it would in a typical balanced tree. See that section for the underlying stack-frame mechanics.
# Recursive
def dfs(u):
visited.add(u)
for v in adj[u]:
if v not in visited:
dfs(v)
# Iterative, explicit stack
stack = [start]
visited = {start}
while stack:
u = stack.pop()
for v in adj[u]:
if v not in visited:
visited.add(v)
stack.append(v)
Python's default recursion limit (~1000) is the tightest of the four languages — a deep graph path hits RecursionError fastest here. The iterative version with a plain list as a stack (append/pop from the end, both O(1)) sidesteps the limit entirely, same trade-off discussed for tree DFS.
A matrix costs O(V²) space regardless of edge count but gives O(1) edge-existence checks — worth it for dense graphs or when you need isEdge(u, v) repeatedly. A list costs O(V+E), the right default for sparse graphs (most interview graphs).
# O(V^2) matrix
matrix = [[0] * n for _ in range(n)]
matrix[u][v] = 1 # mark edge, O(1) lookup later
# O(V+E) list
adj = [[] for _ in range(n)]
adj[u].append(v)
[[0] * n for _ in range(n)] is required, not [[0] * n] * n — the latter creates n references to the same inner list, a classic Python gotcha. Each row is a real Python list of ints (boxed), so memory is worse than a raw numeric buffer would be.
Positional tuple-like structures are faster and lower-overhead; named objects/records are more readable. Pick based on whether the interview values speed of writing or clarity of reading — both are acceptable.
adj = defaultdict(list)
adj[u].append((v, weight)) # tuple: (neighbor, weight)
for neighbor, weight in adj[u]:
...
Tuples are the natural fit — immutable, lightweight, and unpack cleanly in a for loop. No need for a class/namedtuple unless the edge carries more than 2-3 fields.
This is the same key-identity concern as the Hash Maps & Sets section, just showing up again because graph nodes are frequently strings, coordinate pairs, or custom objects rather than clean integers. See that section for the full explanation of hashing/equality contracts.
# Strings and tuples are already hashable — use directly as keys
adj[(row, col)].append((row + 1, col))
# Custom class needs __hash__ and __eq__ to be usable as a dict/set key
class Node:
def __init__(self, x): self.x = x
def __hash__(self): return hash(self.x)
def __eq__(self, other): return self.x == other.x
Tuples of primitives (like (row, col) grid coordinates) are hashable out of the box and are the idiomatic node id for grid graphs — no wrapper class needed. Only reach for __hash__/__eq__ if the node is a genuinely custom object with identity beyond its fields.