DATA STRUCTURES

d, Implement & Master Java & Python Reference for Placeme

Arrays Linked List Stack Queue Tree Heap Hash Map Graph Trie

This PDF is your one-stop placement preparation guide covering the most asked data structures in
technical interviews. Each section explains the concept, provides working code in both Java and
Python, shows complexity analysis, and highlights key placement tips.

DSA — Data Structures in Java & Python | Page 1

Table of Contents
pg
1. Arrays
3

pg
2. Linked List
4

pg
3. Stack
6

pg
4. Queue & Deque
8

pg
5. Binary Tree & BST
9

pg
6. Heap / Priority Queue
11

pg
7. Hash Map & Hash Set
13

pg
8. Graph (BFS / DFS)
15

pg
9. Trie (Prefix Tree)
17

DSA — Data Structures in Java & Python | Page 2

1. Arrays
An array is a contiguous block of memory storing elements of the same type. It is the most fundamental
data structure — every major algorithm uses arrays. Mastering array operations is non-negotiable for
placements.

Java Implementation
■ Java — Array — Declaration, Traversal, Sorting, Searching

import [Link];

public class ArrayDemo {

public static void main(String[] args) {
// 1. Declaration & Initialization
int[] arr = {5, 3, 8, 1, 9, 2};
int n = [Link];

// 2. Traversal
[Link]("Original: ");
for (int x : arr) [Link](x + " ");

// 3. Sorting — O(n log n)

[Link](arr);
[Link]("\nSorted: ");
for (int x : arr) [Link](x + " ");

// 4. Binary Search — O(log n) on sorted array

int idx = [Link](arr, 8);
[Link]("\nIndex of 8: " + idx); // Output: 4

// 5. 2D Array
int[][] matrix = new int[3][3];
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
matrix[i][j] = i * 3 + j;
}
}

Python Implementation
■ Python — Array (List) — Operations

# Python lists act as dynamic arrays

arr = [5, 3, 8, 1, 9, 2]

# Traversal
print('Original:', arr)

# Sorting — O(n log n) Timsort

[Link]()
print('Sorted: ', arr) # [1, 2, 3, 5, 8, 9]

# Binary Search using bisect

DSA — Data Structures in Java & Python | Page 3

 import bisect
idx = bisect.bisect_left(arr, 8)
print('Index of 8:', idx) # 4

# List comprehension (powerful pattern)

squares = [x**2 for x in arr]
print('Squares:', squares)

# 2D matrix
matrix = [[i*3+j for j in range(3)] for i in range(3)]
print('Matrix:', matrix)

Operation Java Class / Python Time Space

Access by index int[] / list O(1) O(1)

Search (linear) int[] / list O(n) O(1)

Search (binary) [Link] O(log n) O(1)

Insertion (end) ArrayList / [Link] O(1) amort O(1)

Insertion (middle) [Link] O(n) O(n)

Sort [Link] / [Link] O(n log n) O(log n)

■ Placement Tip: Two-pointer and sliding-window techniques are built on arrays. Practice 'Two Sum', 'Max
Subarray', 'Merge Intervals' — these appear in 80%+ of placements.

DSA — Data Structures in Java & Python | Page 4

2. Linked List
A linked list is a sequence of nodes where each node stores data and a pointer to the next node. Unlike
arrays, nodes are not stored contiguously in memory. Singly, Doubly, and Circular variants are all common
interview topics.

Java — Singly Linked List (Custom Build)

■ Java — Node + LinkedList: insertFront, insertEnd, delete, reverse

public class LinkedList {

static class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
Node head;

// Insert at front — O(1)

void insertFront(int data) {
Node node = new Node(data);
[Link] = head;
head = node;
}

// Insert at end — O(n)

void insertEnd(int data) {
Node node = new Node(data);
if (head == null) { head = node; return; }
Node cur = head;
while ([Link] != null) cur = [Link];
[Link] = node;
}

// Delete by value — O(n)

void delete(int key) {
if (head == null) return;
if ([Link] == key) { head = [Link]; return; }
Node cur = head;
while ([Link] != null && [Link] != key)
cur = [Link];
if ([Link] != null) [Link] = [Link];
}

// Reverse in-place — O(n)

void reverse() {
Node prev = null, cur = head, next;
while (cur != null) {
next = [Link];
[Link] = prev;

DSA — Data Structures in Java & Python | Page 5

 prev = cur;
cur = next;
}
head = prev;
}

// Detect cycle — Floyd's algorithm O(n)

boolean hasCycle() {
Node slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link];
fast = [Link];
if (slow == fast) return true;
}
return false;
}
}

Python — Doubly Linked List

■ Python — DLL: insert, delete, print forward & backward

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

class DoublyLinkedList:
def __init__(self):
[Link] = None

def insert_end(self, data): # O(n)

node = Node(data)
if not [Link]:
[Link] = node; return
cur = [Link]
while [Link]:
cur = [Link]
[Link] = node
[Link] = cur

def delete(self, key): # O(n)

cur = [Link]
while cur:
if [Link] == key:
if [Link]: [Link] = [Link]
else: [Link] = [Link]
if [Link]: [Link] = [Link]
return
cur = [Link]

def print_forward(self):

DSA — Data Structures in Java & Python | Page 6

 cur = [Link]
while cur:
print([Link], end=' <-> ')
cur = [Link]
print('None')

# Usage
dll = DoublyLinkedList()
for v in [10, 20, 30, 40]: dll.insert_end(v)
dll.print_forward() # 10 <-> 20 <-> 30 <-> 40 <-> None
[Link](20)
dll.print_forward() # 10 <-> 30 <-> 40 <-> None

Operation Java Class / Python Time Space

Insert at head LinkedList O(1) O(1)

Insert at tail LinkedList O(n) O(1)

Delete by value LinkedList O(n) O(1)

Reverse LinkedList O(n) O(1)

Detect cycle Floyd's algo O(n) O(1)

■ Placement Tip: Most LL interview questions involve reversal, cycle detection, or finding the middle. Learn
Floyd's two-pointer by heart. Java's built-in LinkedList uses a doubly-linked list internally.

DSA — Data Structures in Java & Python | Page 7

3. Stack
A stack is a LIFO (Last-In-First-Out) structure. Core operations: push, pop, peek/top. Used in balanced
parentheses, expression evaluation, undo-redo, DFS, and monotonic stack problems.

Java — Stack Using Array + Built-in

■ Java — Custom Stack & [Link] / Deque

import [Link];
import [Link];

// --- Custom Stack (array-backed) ---

class MyStack {
private int[] data;
private int top = -1;
MyStack(int cap) { data = new int[cap]; }

void push(int val) {

if (top == [Link] - 1) throw new RuntimeException("Stack full");
data[++top] = val;
}
int pop() { if (isEmpty()) throw new RuntimeException("Empty"); return data[top--]; }
int peek() { if (isEmpty()) throw new RuntimeException("Empty"); return data[top]; }
boolean isEmpty() { return top == -1; }
int size() { return top + 1; }
}

// --- Preferred: Deque as Stack (Java best practice) ---

Deque<Integer> stack = new ArrayDeque<>();
[Link](10); [Link](20); [Link](30);
[Link]([Link]()); // 30
[Link]([Link]()); // 30

// --- Classic problem: Valid Parentheses ---

static boolean isValid(String s) {
Deque<Character> st = new ArrayDeque<>();
for (char c : [Link]()) {
if (c=='(' || c=='{' || c=='[') [Link](c);
else {
if ([Link]()) return false;
char t = [Link]();
if ((c==')' && t!='(') || (c=='}' && t!='{') || (c==']' && t!='['))
return false;
}
}
return [Link]();
}

Python — Stack + Min Stack

DSA — Data Structures in Java & Python | Page 8

■ Python — Stack using list + MinStack implementation

# Python list as stack

stack = []
[Link](10) # push
[Link](20)
[Link](30)
print(stack[-1]) # peek -> 30
print([Link]()) # pop -> 30

# --- Min Stack (O(1) getMin) --- classic interview question

class MinStack:
def __init__(self):
[Link] = []
self.min_stack = [] # tracks current minimum

def push(self, val):

[Link](val)
cur_min = min(val, self.min_stack[-1] if self.min_stack else val)
self.min_stack.append(cur_min)

def pop(self):
[Link]()
self.min_stack.pop()

def top(self): return [Link][-1]

def get_min(self): return self.min_stack[-1]

ms = MinStack()
for v in [5, 3, 7, 2, 8]: [Link](v)
print(ms.get_min()) # 2
[Link]()
print(ms.get_min()) # 2
[Link]()
print(ms.get_min()) # 3

Operation Java Class / Python Time Space

push ArrayDeque / [Link] O(1) O(1)

pop ArrayDeque / [Link]() O(1) O(1)

peek ArrayDeque / list[-1] O(1) O(1)

getMin (MinStack) Auxiliary stack O(1) O(n)

■ Placement Tip: Monotonic stack is heavily tested — 'Next Greater Element', 'Largest Rectangle in
Histogram'. Always prefer ArrayDeque over [Link] (Stack extends Vector — legacy and slower).

DSA — Data Structures in Java & Python | Page 9

4. Queue & Deque
A queue is a FIFO (First-In-First-Out) structure. A deque (double-ended queue) supports
insertion/deletion at both ends. Queues power BFS, task scheduling, and sliding-window maximum
problems.

Java — Queue, PriorityQueue, Deque

■ Java — LinkedList as Queue + ArrayDeque + BFS template

import [Link].*;

// --- Queue (FIFO) ---

Queue<Integer> q = new LinkedList<>();
[Link](1); [Link](2); [Link](3);
[Link]([Link]()); // 1 (front)
[Link]([Link]()); // 1 (removes front)

// --- Deque (double-ended) ---

Deque<Integer> dq = new ArrayDeque<>();
[Link](10); [Link](20); [Link](5);
[Link](dq); // [5, 10, 20]
[Link](); [Link]();

// --- BFS Template (used for trees & graphs) ---

// Assuming graph is List<List<Integer>> adj, source = 0
static void bfs(List<List<Integer>> adj, int src) {
boolean[] visited = new boolean[[Link]()];
Queue<Integer> queue = new LinkedList<>();
visited[src] = true;
[Link](src);
while (![Link]()) {
int node = [Link]();
[Link](node + " ");
for (int nb : [Link](node)) {
if (!visited[nb]) {
visited[nb] = true;
[Link](nb);
}
}
}
}

Python — [Link] + Circular Queue

■ Python — deque as Queue/Stack + Circular Queue class

from collections import deque

# deque as FIFO queue

q = deque()

DSA — Data Structures in Java & Python | Page 10

 [Link](1); [Link](2); [Link](3) # enqueue
print(q[0]) # peek front -> 1
print([Link]()) # dequeue -> 1

# deque as stack
[Link](99) # push to front
[Link]() # pop from back

# --- Circular Queue ---

class CircularQueue:
def __init__(self, k):
self.q = [None] * k
[Link] = [Link] = -1
[Link] = k

def enqueue(self, val):

if self.is_full(): return False
if self.is_empty(): [Link] = 0
[Link] = ([Link] + 1) % [Link]
self.q[[Link]] = val
return True

def dequeue(self):
if self.is_empty(): return -1
val = self.q[[Link]]
if [Link] == [Link]: [Link] = [Link] = -1
else: [Link] = ([Link] + 1) % [Link]
return val

def is_empty(self): return [Link] == -1

def is_full(self): return ([Link] + 1) % [Link] == [Link]

cq = CircularQueue(4)
[Link](1); [Link](2); [Link](3)
print([Link]()) # 1

Operation Java Class / Python Time Space

Enqueue [Link] / [Link] O(1) O(1)

Dequeue [Link] / [Link] O(1) O(1)

Peek [Link]() / deque[0] O(1) O(1)

Deque ops ArrayDeque / [Link] O(1) O(1)

■ Placement Tip: 'Sliding Window Maximum' uses a monotonic deque — a top-tier interview problem. Use
ArrayDeque in Java for both stack and queue; it's faster than LinkedList.

DSA — Data Structures in Java & Python | Page 11

5. Binary Tree & Binary Search Tree (BST)
A binary tree has nodes with at most two children. A BST maintains: left child < parent < right child.
Traversals (inorder, preorder, postorder, level-order) and BST operations are must-know topics.

Java — Build BST + All Traversals

■ Java — BST insert/search + DFS traversals + BFS level-order

import [Link].*;

class TreeNode {
int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}

class BST {
TreeNode root;

TreeNode insert(TreeNode node, int val) { // O(log n) avg

if (node == null) return new TreeNode(val);
if (val < [Link]) [Link] = insert([Link], val);
else if (val > [Link]) [Link] = insert([Link], val);
return node;
}

boolean search(TreeNode node, int val) { // O(log n) avg

if (node == null) return false;
if ([Link] == val) return true;
return val < [Link] ? search([Link], val)
: search([Link], val);
}

// Inorder (Left-Root-Right) -> gives sorted order for BST

void inorder(TreeNode node) {
if (node == null) return;
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}

// Level-order BFS
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
[Link](root);
while (![Link]()) {
int size = [Link]();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode cur = [Link]();

DSA — Data Structures in Java & Python | Page 12

 [Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](level);
}
return res;
}

int height(TreeNode node) { // O(n)

if (node == null) return 0;
return 1 + [Link](height([Link]), height([Link]));
}
}

Python — Binary Tree Traversals

■ Python — TreeNode + recursive & iterative traversals

from collections import deque

class TreeNode:
def __init__(self, val=0):
[Link] = val
[Link] = [Link] = None

# Build example tree: 4

# / \
# 2 6
# / \ / \
# 1 3 5 7
def build_bst(values):
root = None
def insert(node, v):
if not node: return TreeNode(v)
if v < [Link]: [Link] = insert([Link], v)
else: [Link] = insert([Link], v)
return node
for v in values:
root = insert(root, v)
return root

def inorder(node): # Left Root Right -> sorted

if not node: return []
return inorder([Link]) + [[Link]] + inorder([Link])

def preorder(node): # Root Left Right -> used in copy/serialize

if not node: return []
return [[Link]] + preorder([Link]) + preorder([Link])

def level_order(root): # BFS

if not root: return []
q, res = deque([root]), []
while q:

DSA — Data Structures in Java & Python | Page 13

 level = []
for _ in range(len(q)):
node = [Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
[Link](level)
return res

root = build_bst([4, 2, 6, 1, 3, 5, 7])

print('Inorder:', inorder(root)) # [1,2,3,4,5,6,7]
print('Preorder:', preorder(root)) # [4,2,1,3,6,5,7]
print('Level-order:', level_order(root)) # [[4],[2,6],[1,3,5,7]]

Operation Java Class / Python Time Space

Insert (BST) TreeNode recursion O(log n) avg / O(n) worst O(h)

Search (BST) TreeNode recursion O(log n) avg / O(n) worst O(h)

Traversals All 4 traversals O(n) O(h)

Height Recursive O(n) O(h)

Level Order (BFS) Queue O(n) O(w)

■ Placement Tip: Inorder of BST = sorted array — exploit this property. Know iterative inorder using a stack.
Height is the most recursively tested function; practice deriving it from scratch.

DSA — Data Structures in Java & Python | Page 14

6. Heap / Priority Queue
A heap is a complete binary tree satisfying the heap property. A min-heap gives the smallest element in
O(1). A max-heap gives the largest. Used in: Kth largest, Dijkstra, Merge K Sorted Lists, Top K Frequent
Elements.

Java — PriorityQueue (Min + Max Heap)

■ Java — Min-heap, Max-heap, Custom comparator, Top-K

import [Link].*;

// --- Min Heap (default) ---

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
int[] nums = {5, 3, 8, 1, 9, 2};
for (int n : nums) [Link](n);
[Link]([Link]()); // 1 (smallest)
[Link]([Link]()); // 2

// --- Max Heap ---

PriorityQueue<Integer> maxHeap = new PriorityQueue<>([Link]());
for (int n : nums) [Link](n);
[Link]([Link]()); // 9 (largest)

// --- Top K Largest Elements (using Min Heap of size K) ---

static int[] topKLargest(int[] arr, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(k);
for (int n : arr) {
[Link](n);
if ([Link]() > k) [Link](); // remove smallest
}
return [Link]().mapToInt(i -> i).toArray();
}

// --- Custom object heap ---

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
[Link](new int[]{1, 5}); // {id, distance}
[Link](new int[]{2, 2});
[Link]([Link]([Link]())); // [2, 2]

Python — heapq (Min Heap) + Custom Max Heap

■ Python — heapq module + Kth largest + merge K sorted

import heapq

# --- Min Heap ---

nums = [5, 3, 8, 1, 9, 2]
heap = nums[:]
[Link](heap) # O(n) in-place
print([Link](heap)) # 1
print([Link](heap)) # 2

DSA — Data Structures in Java & Python | Page 15

 [Link](heap, 0)
print([Link](heap)) # 0

# --- Max Heap (negate values trick) ---

max_heap = [-x for x in nums]
[Link](max_heap)
print(-[Link](max_heap)) # 9 (largest)

# --- Top K Largest ---

def top_k_largest(arr, k):
return [Link](k, arr) # O(n log k)

print(top_k_largest(nums, 3)) # [9, 8, 5]

# --- Kth Smallest Element ---

def kth_smallest(arr, k):
return [Link](k, arr)[-1]

print(kth_smallest(nums, 2)) # 2

# --- Merge K sorted lists ---

def merge_k_sorted(lists):
h = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
[Link](h)
result = []
while h:
val, i, j = [Link](h)
[Link](val)
if j + 1 < len(lists[i]):
[Link](h, (lists[i][j+1], i, j+1))
return result

Operation Java Class / Python Time Space

heapify PriorityQueue / heapify O(n) O(n)

push/offer PriorityQueue / heappush O(log n) O(1)

pop/poll PriorityQueue / heappop O(log n) O(1)

peek/min [Link]() / heap[0] O(1) O(1)

Top K Min-heap of size K O(n log k) O(k)

■ Placement Tip: 'Kth Largest Element' is one of the most asked heap questions. Two-heap technique
(median of stream) uses one min-heap + one max-heap simultaneously.

DSA — Data Structures in Java & Python | Page 16

7. Hash Map & Hash Set
A HashMap stores key-value pairs with O(1) average-case access. A HashSet stores unique elements.
Both use hashing internally. Frequency counting, grouping, and 'two-sum' patterns rely entirely on these
structures.

Java — HashMap + HashSet + LinkedHashMap

■ Java — Frequency count, anagram grouping, two-sum

import [Link].*;

// --- HashMap basics ---

Map<String, Integer> freq = new HashMap<>();
String[] words = {"apple","banana","apple","cherry","banana","apple"};
for (String w : words)
[Link](w, [Link](w, 0) + 1);
[Link](freq); // {apple=3, banana=2, cherry=1}

// --- HashSet ---

Set<Integer> seen = new HashSet<>();
int[] arr = {1,2,3,2,4,1,5};
List<Integer> duplicates = new ArrayList<>();
for (int n : arr)
if () [Link](n);
[Link]("Duplicates: " + duplicates); // [2, 1]

// --- Two Sum (O(n)) ---

static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < [Link]; i++) {
int comp = target - nums[i];
if ([Link](comp))
return new int[]{[Link](comp), i};
[Link](nums[i], i);
}
return new int[]{};
}
[Link]([Link](twoSum(new int[]{2,7,11,15}, 9))); // [0,1]

// --- LinkedHashMap (insertion-order) ---

Map<String,Integer> ordered = new LinkedHashMap<>();
[Link]("first",1); [Link]("second",2); [Link]("third",3);
[Link]((k,v) -> [Link](k + ":" + v));

Python — dict + Counter + defaultdict

■ Python — [Link], defaultdict, set operations

from collections import Counter, defaultdict

# --- Counter (frequency map) ---

DSA — Data Structures in Java & Python | Page 17

 words = ['apple','banana','apple','cherry','banana','apple']
freq = Counter(words)
print(freq) # Counter({'apple':3,'banana':2,'cherry':1})
print(freq.most_common(2)) # [('apple',3),('banana',2)]

# --- defaultdict ---

graph = defaultdict(list) # adjacency list
edges = [(0,1),(0,2),(1,3)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
print(dict(graph)) # {0:[1,2],1:[0,3],2:[0],3:[1]}

# --- Group Anagrams ---

def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s))
groups[key].append(s)
return list([Link]())

print(group_anagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'],['tan','nat'],['bat']]

# --- Set operations ---

a, b = {1,2,3,4}, {3,4,5,6}
print(a & b) # intersection {3,4}
print(a | b) # union {1,2,3,4,5,6}
print(a - b) # difference {1,2}
print(a ^ b) # sym. diff {1,2,5,6}

Operation Java Class / Python Time Space

put / insert HashMap / dict O(1) avg O(n)

get / lookup HashMap / dict O(1) avg O(1)

remove / delete HashMap / dict O(1) avg O(1)

contains / in HashSet / set O(1) avg O(n)

Set union/intersect Set ops O(n) O(n)

■ Placement Tip: Two Sum, Subarray Sum Equals K, Longest Consecutive Sequence — all solved with
HashMap in O(n). Python's Counter is a shortcut for frequency problems that saves 3-4 lines every time.

DSA — Data Structures in Java & Python | Page 18

8. Graph (BFS / DFS)
A graph is a collection of vertices (nodes) and edges. Represented as an adjacency list (HashMap / List
of Lists) or adjacency matrix. BFS finds shortest path in unweighted graphs; DFS explores paths and
detects cycles.

Java — Graph with BFS + DFS + Cycle Detection

■ Java — Adjacency list, BFS shortest path, DFS recursive, cycle detection

import [Link].*;

class Graph {
private int V;
private List<List<Integer>> adj;

Graph(int v) {
V = v;
adj = new ArrayList<>();
for (int i = 0; i < v; i++) [Link](new ArrayList<>());
}

void addEdge(int u, int v) { // undirected

[Link](u).add(v);
[Link](v).add(u);
}

// BFS — shortest path (unweighted)

int[] bfsDistance(int src) {
int[] dist = new int[V];
[Link](dist, -1);
Queue<Integer> q = new LinkedList<>();
dist[src] = 0; [Link](src);
while (![Link]()) {
int u = [Link]();
for (int nb : [Link](u)) {
if (dist[nb] == -1) {
dist[nb] = dist[u] + 1;
[Link](nb);
}
}
}
return dist;
}

// DFS — recursive
void dfs(int node, boolean[] visited) {
visited[node] = true;
[Link](node + " ");
for (int nb : [Link](node))
if (!visited[nb]) dfs(nb, visited);

DSA — Data Structures in Java & Python | Page 19

 }

// Cycle detection (undirected) using DFS

boolean hasCycle() {
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++)
if (!visited[i] && cycleUtil(i, -1, visited)) return true;
return false;
}
private boolean cycleUtil(int node, int parent, boolean[] vis) {
vis[node] = true;
for (int nb : [Link](node)) {
if (!vis[nb]) { if (cycleUtil(nb, node, vis)) return true; }
else if (nb != parent) return true;
}
return false;
}
}

Python — Graph BFS + DFS + Topological Sort

■ Python — defaultdict adjacency list + BFS + DFS + Topo sort (Kahn's)

from collections import defaultdict, deque

class Graph:
def __init__(self):
[Link] = defaultdict(list)

def add_edge(self, u, v, directed=False):

[Link][u].append(v)
if not directed: [Link][v].append(u)

def bfs(self, src):

visited = {src}
q = deque([src])
order = []
while q:
node = [Link]()
[Link](node)
for nb in [Link][node]:
if nb not in visited:
[Link](nb)
[Link](nb)
return order

def dfs(self, src, visited=None):

if visited is None: visited = set()
[Link](src)
result = [src]
for nb in [Link][src]:
if nb not in visited:
result += [Link](nb, visited)

DSA — Data Structures in Java & Python | Page 20

 return result

# Topological Sort — Kahn's BFS (directed acyclic graph)

def topological_sort(self, num_nodes):
in_degree = defaultdict(int)
for u in [Link]:
for v in [Link][u]: in_degree[v] += 1
q = deque(i for i in range(num_nodes) if in_degree[i] == 0)
order = []
while q:
node = [Link](); [Link](node)
for nb in [Link][node]:
in_degree[nb] -= 1
if in_degree[nb] == 0: [Link](nb)
return order if len(order) == num_nodes else [] # [] if cycle

g = Graph()
for u, v in [(0,1),(0,2),(1,3),(2,3)]: g.add_edge(u, v)
print('BFS:', [Link](0)) # [0,1,2,3]
print('DFS:', [Link](0)) # [0,1,3,2]

Operation Java Class / Python Time Space

Build adjacency list ArrayList / defaultdict O(V+E) O(V+E)

BFS Queue O(V+E) O(V)

DFS Recursion / Stack O(V+E) O(V)

Topological Sort Kahn's BFS O(V+E) O(V)

Cycle Detection DFS coloring O(V+E) O(V)

■ Placement Tip: 'Number of Islands' (BFS/DFS on 2D grid), 'Clone Graph', 'Course Schedule' (topo sort)
are the top-3 graph questions asked in FAANG-level placements. Practice all three cold.

DSA — Data Structures in Java & Python | Page 21

9. Trie (Prefix Tree)
A Trie is a tree-shaped data structure for storing strings where each path from root to a marked node
represents a word. Optimal for prefix-search, autocomplete, and word dictionary problems. All operations
run in O(L) where L = length of the string.

Java — Trie Build + Insert + Search + StartsWith

■ Java — TrieNode array[26] + insert + search + startsWith + delete

class Trie {
private static class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd = false;
}

private TrieNode root = new TrieNode();

// Insert word — O(L)

public void insert(String word) {
TrieNode cur = root;
for (char c : [Link]()) {
int idx = c - 'a';
if ([Link][idx] == null)
[Link][idx] = new TrieNode();
cur = [Link][idx];
}
[Link] = true;
}

// Search exact word — O(L)

public boolean search(String word) {
TrieNode cur = root;
for (char c : [Link]()) {
int idx = c - 'a';
if ([Link][idx] == null) return false;
cur = [Link][idx];
}
return [Link];
}

// Prefix search — O(L)

public boolean startsWith(String prefix) {
TrieNode cur = root;
for (char c : [Link]()) {
int idx = c - 'a';
if ([Link][idx] == null) return false;
cur = [Link][idx];
}
return true;

DSA — Data Structures in Java & Python | Page 22

 }
}

// Test
Trie t = new Trie();
[Link]("apple"); [Link]("app"); [Link]("application");
[Link]([Link]("app")); // true
[Link]([Link]("ap")); // false
[Link]([Link]("appl")); // true

Python — Trie with HashMap children

■ Python — Trie using dict children + count words with prefix

class TrieNode:
def __init__(self):
[Link] = {} # char -> TrieNode
self.is_end = False
[Link] = 0 # number of words passing through

class Trie:
def __init__(self):
[Link] = TrieNode()

def insert(self, word): # O(L)

cur = [Link]
for c in word:
if c not in [Link]:
[Link][c] = TrieNode()
cur = [Link][c]
[Link] += 1
cur.is_end = True

def search(self, word): # O(L)

cur = [Link]
for c in word:
if c not in [Link]: return False
cur = [Link][c]
return cur.is_end

def starts_with(self, prefix): # O(L)

cur = [Link]
for c in prefix:
if c not in [Link]: return False
cur = [Link][c]
return True

def count_prefix(self, prefix): # words starting with prefix

cur = [Link]
for c in prefix:
if c not in [Link]: return 0
cur = [Link][c]
return [Link]

t = Trie()

DSA — Data Structures in Java & Python | Page 23

 for w in ['apple','app','application','apply','banana']: [Link](w)
print([Link]('app')) # True
print(t.starts_with('appl')) # True
print(t.count_prefix('app')) # 4 (apple,app,application,apply)
print(t.count_prefix('ban')) # 1

Operation Java Class / Python Time Space

insert TrieNode[26] / dict O(L) O(L * ALPHA)

search TrieNode / dict O(L) O(1)

startsWith TrieNode / dict O(L) O(1)

count prefix Modified Trie O(L) O(1)

delete Backtrack DFS O(L) O(1)

■ Placement Tip: 'Word Search II' (Trie + DFS on grid) and 'Design Add and Search Words Data Structure'
are the hardest Trie problems asked. Also know how to implement autocomplete using DFS on Trie.

Quick Complexity Reference

Data Structure Access Search Insert Delete Space

Array O(1) O(n) O(n) O(n) O(n)

Linked List O(n) O(n) O(1) head O(1) known O(n)

Stack O(n) O(n) O(1) O(1) O(n)

Queue O(n) O(n) O(1) O(1) O(n)

BST (avg) O(log n) O(log n) O(log n) O(log n) O(n)

Heap O(1) top O(n) O(log n) O(log n) O(n)

Hash Map O(1) O(1) avg O(1) avg O(1) avg O(n)

Trie O(L) O(L) O(L) O(L) O(L*n)

Graph (adj) - O(V+E) O(1) O(V+E) O(V+E)

Best of luck with your placement interviews! Master these 9 data structures and you will be
equipped to tackle 90% of coding rounds. Consistency beats intensity — solve 2–3 problems daily
using these patterns and the rest will follow. You've got this!

DSA — Data Structures in Java & Python | Page 24