3. Lists

Tutorial

list is Python's dynamic array — $O(1)$ index access, $O(1)$ amortized append, $O(n)$ insert/delete at arbitrary positions.

# --- Creation ---
nums  = [1, 2, 3, 4, 5]
zeros = [0] * n                     # [0, 0, ..., 0]
grid  = [[0] * cols for _ in range(rows)]   # 2D — use comprehension!
# ❌ [[0]*cols]*rows  — all rows share the same object!

# --- Access & Slicing ---
nums[0]        # first
nums[-1]       # last
nums[1:4]      # [2, 3, 4]  — new list
nums[::-1]     # reversed copy
nums[::2]      # every other element

# --- Modification ---
nums.append(6)          # O(1) amortized — end
nums.insert(0, 99)      # O(n) — avoid for performance-critical code
nums.pop()              # O(1) — remove last
nums.pop(i)             # O(n) — remove at index i
nums.remove(val)        # O(n) — remove first occurrence of val
nums.extend([7, 8])     # O(k) — append multiple
nums += [7, 8]          # same as extend
nums + [9]               # creates a NEW list — original unchanged
del nums[i]             # O(n) — delete at index

nums.reverse()          # O(n) — reverses in place
nums[::-1]              # O(n) — creates a NEW reversed list

# --- Sorting ---
nums.sort()                           # in-place, O(n log n)
nums.sort(reverse=True)
nums.sort(key=abs)
nums.sort(key=lambda x: -x)           # custom key (descending)
nums.sort(key=lambda x: (x[1], x[0]))  # multi-key
sorted_copy = sorted(nums)            # new list

# --- Search ---
3 in nums          # O(n) — linear scan; use set for O(1)
nums.index(3)      # O(n) — ValueError if missing
nums.count(3)      # O(n) — count occurrences

# --- Copy ---
copy = nums[:]     # shallow copy
copy = nums.copy() # same
# Nested lists (grids, adjacency lists): shallow copy still shares inner
# lists — use copy.deepcopy() for a fully independent clone (see §15)

# --- Stack (use list — O(1) push/pop at end) ---
stack = []
stack.append(x)   # push
stack.pop()       # pop
stack[-1]         # peek

# --- Queue (use deque, NOT list — list.pop(0) is O(n)) ---
from collections import deque
queue = deque([1, 2, 3])
queue.append(4)        # enqueue right — O(1)
queue.popleft()        # dequeue left  — O(1)
queue.appendleft(0)    # add to front — O(1)

# --- Useful patterns ---
prefix = [0] * (n + 1)
for i, x in enumerate(nums):
    prefix[i+1] = prefix[i] + x     # prefix sum

# accumulate (Python stdlib)
from itertools import accumulate
prefix = [0] + list(accumulate(nums))

Reference

Operation	Complexity	Notes
lst[i]	$O(1)$	Random access
lst.append(x)	$O(1)$†	End only
lst.pop()	$O(1)$†	End only
lst.insert(i, x)	$O(n)$	Shifts elements
lst.pop(i)	$O(n)$	Shifts elements
lst.remove(v)	$O(n)$	Scan + shift
x in lst	$O(n)$	Use set for $O(1)$
lst.sort()	$O(n \log n)$	In-place Timsort, stable
lst[i:j]	$O(j-i)$	Creates new list
len(lst)	$O(1)$
2D init	[[0]*c for _ in range(r)]	Never [[0]*c]*r

† Amortized

---