Python Data Structures

& Algorithms Cheat Sheet

(Quick Reference for Java Developers)

1 Python Basics vs. Java

• Indentation replaces braces; end statements are implicit.
• Variables are dynamically typed; annotate for readability only.
• Print: print("hello") (System.out.println in Java).
• Functions: def func(arg1: int)-> int: (type hints optional).
• Comprehensions: [x*x for x in range(5)].
• Lambdas: square = lambda x: x*x.
• Truthiness: empty collections, 0, None evaluate to False.

2 Core Built-in Collections

2.1 Lists (dynamic arrays)
• Declare: nums = [1, 2, 3]; analogous to ArrayList<Integer>.
• Indexing: nums[-1] (last); slicing nums[1:4].
• Common ops: append, insert, pop, sort (Timsort O(n log n)).
• Time complexity: access O(1), append O(1), insert/delete O(n).

2.2 Tuples (immutable lists)

• Syntax: pt = (x, y); hashable → usable as dict keys / set elements.

2.3 Dictionaries (hash maps)

• Declare: m = {"a": 1, "b": 2} (HashMap<String,Integer>).
• Avg lookup/insertion O(1) via hashing.
• Methods: get, items, update, setdefault.

2.4 Sets (hash set)

• seen = set(); supports union/intersection.
• Fast membership tests O(1).

2.5 Quick-Lookup: Common Collection Methods

List (list) Dictionary (dict)

append(x) add to end get(k,def) safe lookup
extend(it) concat iterable keys() key view
insert(i,x) add at index values() value view
pop([i]) remove items() (k,v) pairs
remove(x) delete first x update(m) merge/overwrite
clear() empty list pop(k) delete key
index(x) first index x popitem() LIFO pair
count(x) occurrences x setdefault(k,def) default-put
sort() in-place sort clear() empty dict
reverse() in-place reverse fromkeys(seq, v) new dict
copy() shallow copy 1
 Set (set) Tuple (tuple) & String
add(x) insert x count(x) times x appears
update(it) union in-place index(x) first idx x
remove(x) KeyError if absent String Highlights
discard(x) safe remove split(sep) to list
pop() arbitrary pop join(it) combine with sep
clear() empty set replace(old,new) global replace
union(s) s1 s2| strip() trim ends
intersection(s) s1 & s2 startswith(s) prefix test
difference(s) s1 - s2 endswith(s) suffix test
symmetric_difference(s) s1 ^ s2 format(...) legacy interp.
issubset(s) subset test upper(), lower() case convert
issuperset(s) superset test isdigit(), isalpha() type checks
isdisjoint(s) disjoint test

3 collections Module Gems

• deque: O(1) appends/pops both ends – ideal BFS queue.
• Counter: freq map; Counter(arr).most_common(3).
• defaultdict: auto-init missing keys; dd = defaultdict(int).
• namedtuple / dataclass: lightweight records.
• heapq: min-heap (priority queue) O(log n).
• bisect: binary search on sorted lists O(log n).

4 Algorithm Primitives
4.1 Sorting
• In-place: arr.sort() (stable Timsort O(n log n)).
• Non-destructive: sorted(iterable, key=..., reverse=True).

4.2 Searching – Binary Search

from bisect import bisect_left
idx = bisect_left ( sorted_list , target )
if idx < len ( sorted_list ) and sorted_list [ idx ] == target :
print ( " found " )

4.3 Heaps / Priority Queue

import heapq
pq = []
heapq . heappush ( pq , ( priority , item ) )
priority , item = heapq . heappop ( pq ) # smallest first

4.4 Graph Traversal – BFS

from collections import deque
def bfs ( graph , src ) :
q , seen = deque ([ src ]) , { src }
while q :
v = q . popleft ()
for nbr in graph [ v ]:

2
 if nbr not in seen :
seen . add ( nbr ) ; q . append ( nbr )

4.5 Graph Traversal – DFS

def dfs ( graph , v , seen = None ) :
if seen is None :
seen = set ()
seen . add ( v )
for nbr in graph [ v ]:
if nbr not in seen :
dfs ( graph , nbr , seen )
return seen

4.6 Dijkstra Shortest Path

import heapq , math
def dijkstra ( graph , src ) :
dist = { v : math . inf for v in graph }; dist [ src ] = 0
pq = [(0 , src ) ]
while pq :
d , u = heapq . heappop ( pq )
if d > dist [ u ]:
continue
for v , w in graph [ u ]:
nd = d + w
if nd < dist [ v ]:
dist [ v ] = nd
heapq . heappush ( pq , ( nd , v ) )
return dist

5 Complexity Cheat Sheet

Operation List Dict/Set Notes
Index lookup O(1) – contiguous memory
Append/Add O(1) O(1) amortized for list
Insert/Delete mid O(n) O(1) dict resize rare
Membership test O(n) O(1) scan vs hash
Sort O(n log n) – Timsort (stable)

6 Idiomatic Patterns
6.1 Frequency Map
freq = Counter(arr) (replaces Java loops + HashMap).

6.2 Two-Pointer Technique

lo , hi = 0 , len ( nums ) - 1
while lo < hi :
s = nums [ lo ] + nums [ hi ]
if s == target :
break
lo += ( s < target ) # bool to int conversion
hi -= ( s > target )

3
6.3 Memoization / DP
from functools import lru_cache
@lru_cache ( maxsize = None )
def fib ( n ) :
if n < 2:
return n
return fib (n -1) + fib (n -2)

6.4 Sliding Window

def max_sum_s u b a r r a y ( arr , k ) :
window_sum = sum ( arr [: k ])
max_sum = window_sum
for i in range (k , len ( arr ) ) :
window_sum += arr [ i ] - arr [i - k ]
max_sum = max ( max_sum , window_sum )
return max_sum

7 Java → Python Translation Hints

• For-loops: for i in range(n): vs for(int i=0;i<n;i++)
• Enhanced for-each: for s in lst: vs for(String s : list)
• Generics rarely needed; rely on duck typing
• Static methods → module-level functions
• No checked exceptions; use try/except
• Constants: ALL_CAPS at module level (no static final)
• String concatenation: use "".join() for multiple strings
• Array length: len(arr) vs arr.length

8 Essential Stdlib Modules

• itertools: combinations, permutations, accumulate, product, cycle
• functools: lru_cache, cmp_to_key, reduce
• math: constants and math funcs; math.inf, math.gcd
• random: RNG utilities; random.randint, random.choice
• re: regular expressions; re.match, re.search, re.findall

9 Handy Built-ins
• enumerate(iter): index, value pairs; for i, val in enumerate(arr):
• zip(*iters): parallel iteration; for a, b in zip(list1, list2):
• any(), all(): logical reductions over iterables
• map(), filter(): functional programming helpers
• sum(), min(), max(): aggregation functions
• range(): range(start, stop, step) – memory efficient
• reversed(): reverse iterator; for x in reversed(arr):

10 Common Pitfalls
• Mutable default args: use def f(x, lst=None): lst = lst or []
• Integer division: // floors (watch negatives); / is float division
• Copy lists with lst.copy() or lst[:] (shallow copy)
• dict preserves insertion order (CPython ≥ 3.7)

4
 • Variable scope: no block scope, only function/class/module scope
• Late binding closures: use default parameters to capture loop variables

11 Quick Syntax Reference

List Comprehensions: Unpacking:
[expr for item in iterable if condition] a, b = pair
Dict Comprehensions: first, *middle, last = arr
{k: v for k, v in pairs if condition} **kwargs(dict unpacking)
Set Comprehensions: F-strings (Python 3.6+):
{expr for item in iterable if condition} f"Value: {var:.2f}"
Generator Expressions: Walrus Operator (Python 3.8+):
(expr for item in iterable if condition) if (n := len(arr))> 5:

Practice on LeetCode / HackerRank – muscle memory beats memorization. Happy coding!