Python Data Structures, Compared with Java

This note is a comparison I made while switching from Java to Python. The main goals are:

Quickly map Java habits to Python equivalents.
Avoid performance and semantic pitfalls in coding interviews and business code.

Overview

Scenario	Common Java usage	Common Python usage
Dynamic array	`ArrayList`	`list`
Hash map	`HashMap`	`dict`
Hash set	`HashSet`	`set`
Stack	`ArrayDeque` / `Stack`	`list`
Queue / deque	`ArrayDeque`	`collections.deque`
Min heap	`PriorityQueue`	`heapq` + `list`

Array and Dynamic List

# Java: List<Integer> list = new ArrayList<>()
arr = []

# Java: list.add(1)
arr.append(1)

# Java: list.get(i)
arr[0]

# Java: list.size() / arr.length
len(arr)

# Java: list.remove(list.size() - 1)
arr.pop()

# Java: list.subList(start, end)  # left-closed, right-open
sub = arr[start:end]

My notes:

Inserting or deleting at the head of a Python list is O(n). For frequent queue operations, use deque.
Slicing with arr[a:b] returns a new list, not a view.

Hash Map

# Java: Map<String, Integer> map = new HashMap<>()
tmap = {}

# Java: map.put("apple", 1)
tmap["apple"] = 1

# Java: map.containsKey("apple")
"apple" in tmap

# Java: map.get("apple")
# Note: raises KeyError if the key does not exist
tmap["apple"]

# Java: map.getOrDefault("apple", 0)
tmap.get("apple", 0)

# Java: map.remove("apple")
del tmap["apple"]

# Java: for (String key : map.keySet())
for key in tmap:
    pass

# Java: for (Map.Entry<String, Integer> entry : map.entrySet())
for key, value in tmap.items():
    pass

My notes:

del tmap[k] raises an error if the key does not exist. A safer option is tmap.pop(k, None).
For high-frequency counting, prefer collections.Counter or defaultdict(int).

Hash Set

# Java: Set<Integer> set = new HashSet<>()
tset = set()

# Java: set.add(1)
tset.add('a')

# Java: set.contains(1)
'a' in tset

# Java: set.remove(1)  # raises an error if missing
tset.remove('a')

# Python-specific: no error if missing
tset.discard('a')

# Java: set.size()
len(tset)

My notes:

set is unordered, so do not rely on iteration order.
For order-preserving deduplication, use dict.fromkeys(seq) or maintain the order manually.

Stack and Deque

from collections import deque

# Stack, last in first out
# Java: Deque<Integer> stack = new ArrayDeque<>()
stack = []
stack.append(1)   # push
stack.pop()       # pop
# Check before peek
if stack:
    top = stack[-1]

# Queue, first in first out
# Java: Deque<Integer> queue = new ArrayDeque<>()
queue = deque()
queue.append(1)       # addLast
queue.appendleft(2)   # addFirst
queue.popleft()       # pollFirst
queue.pop()           # pollLast
if queue:
    head = queue[0]   # peekFirst
if not queue:
    pass

My notes:

For queues in Python, prefer deque; do not use list.pop(0).
Check whether the stack or queue is empty before reading the top/head to avoid IndexError.

Heap / Priority Queue

import heapq

# Java: PriorityQueue<Integer> pq = new PriorityQueue<>()
heap = []
heapq.heappush(heap, 5)  # offer
heapq.heappush(heap, 2)
heapq.heappop(heap)      # poll

# peek
if heap:
    top = heap[0]

# Python only provides a min heap by default
# Java maxHeap: new PriorityQueue<>((a, b) -> b - a)
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -2)
val = -heapq.heappop(max_heap)

My notes:

heapq is not a full container class. It is a set of heap operations over a list.
For fixed-size top-K problems, a common pattern is to keep K elements in a min heap.

Safe Patterns I Use Often

# safe dict read
v = tmap.get("k", 0)

# safe dict deletion
tmap.pop("k", None)

# check before reading stack/queue
if stack:
    x = stack[-1]

if queue:
    y = queue[0]

# check before reading heap top
if heap:
    z = heap[0]

Summary

After switching from Java to Python, my main changes are:

Care less about class names and more about operation complexity.
Use deque first for queues and heapq first for heaps.
Build muscle memory around existence checks and safe access for dictionaries and sets.

Later I plan to add another note on Python templates for sorting, binary search, prefix sums, and monotonic stacks.