🔬 Advanced List Implementation — Internals and Optimization

Understand how Python lists work internally and how to optimize for performance.

🎯 Dynamic Array Implementation

Python lists use dynamic arrays that resize automatically. They allocate extra capacity to minimize reallocation.

import sys

# Check memory size (in bytes)
empty_list = []
print(sys.getsizeof(empty_list))  # 56 bytes

lst = [1]
print(sys.getsizeof(lst))  # 88 bytes (allocated space for ~8 items)

# Each append may trigger reallocation
lst = []
for i in range(10):
    print(f"Size: {sys.getsizeof(lst)}, Length: {len(lst)}")
    lst.append(i)

# Output shows capacity grows non-linearly:
# Size: 56, Length: 0
# Size: 88, Length: 1
# Size: 88, Length: 2
# Size: 88, Length: 3
# Size: 88, Length: 4
# Size: 120, Length: 5  <- reallocation at 5

Growth factor is ~1.125 times the current capacity, providing amortized O(1) append.

💡 Slicing Operations and Copy Semantics

Slicing creates a shallow copy of the specified range, which has O(k) complexity where k is slice size.

# Slicing creates new list (shallow copy)
original = [1, 2, 3, 4, 5]
sliced = original[1:4]  # O(3) - creates new list with 3 elements

# Step parameter
every_other = original[::2]  # [1, 3, 5] - O(n/2)
reversed_list = original[::-1]  # [5, 4, 3, 2, 1] - O(n)

# Edge cases
empty_slice = original[10:20]  # No error, returns []
partial_reverse = original[3:0:-1]  # [4, 3]

# Shared references with nested structures
nested = [[1, 2], [3, 4]]
sliced_nested = nested[:]  # Shallow copy - still references same inner lists
sliced_nested[0][0] = 99
print(nested)  # [[99, 2], [3, 4]] - affected!

🎨 Advanced Indexing Patterns

# Extended slicing with all parameters
lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# start:stop:step
print(lst[2:8:2])    # [2, 4, 6]
print(lst[::3])      # [0, 3, 6, 9]
print(lst[::-1])     # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

# Negative indices with step
print(lst[-5:-1:1])  # [5, 6, 7, 8]
print(lst[-1:-5:-1]) # [9, 8, 7, 6]

# Assignment to slices
lst[1:4] = [100, 200, 300]
print(lst)  # [0, 100, 200, 300, 4, 5, ...]

# Slice with different length
lst = [1, 2, 3, 4, 5]
lst[1:3] = [20, 30, 40]  # [1, 20, 30, 40, 4, 5]

📊 Performance Characteristics

🔑 Key Takeaways

• ✅ Lists use dynamic arrays with ~1.125x growth factor

• ✅ Append is O(1) amortized, insert is O(n)

• ✅ Slicing creates shallow copies in O(k) time

• ✅ Negative indices, step parameters enable powerful slicing

• ✅ Slice assignment can change list size

Ready to practice? Challenges | Quiz