Python Lists
List Fundamentals
Lists are ordered, mutable sequences and one of the most commonly used data structures in Python. They can hold elements of any type and adjust size dynamically.
Key characteristics:
- Ordered (maintain insertion order)
- Mutable (elements can be updated or removed)
- Heterogeneous (can store mixed data types)
- Indexable and sliceable
- Dynamically resizable
Example
# List creation examples
primes = [2, 3, 5, 7, 11]
mixed = [1, 'two', 3.0, True]
matrix = [[1, 2], [3, 4]]
# Using list() constructor
chars = list('hello') # ['h', 'e', 'l', 'l', 'o']Output
# Results shown in comments
Memory Management
Lists are backed by dynamic arrays that grow with overallocation to reduce frequent resizing:
- Begin with small capacity and expand as needed
- Growth pattern roughly follows 0, 4, 8, 16, 25, 35, ...
- `append()` runs in amortized O(1) time
- Arbitrary insertions require shifting elements, costing O(n)
Example
import sys
lst = []
for i in range(10):
print(f"Length: {len(lst)}, Size in bytes: {sys.getsizeof(lst)}")
lst.append(i)ℹ️ Note: Over-allocation ensures efficient appends by minimizing costly reallocations.
Performance Characteristics
| Operation | Time Complexity | Example |
|---|---|---|
| Index access | O(1) | lst[5] |
| Append | O(1) amortized | lst.append(x) |
| Insert | O(n) | lst.insert(0, x) |
| Pop last | O(1) | lst.pop() |
| Pop at index | O(n) | lst.pop(2) |
| Search (in) | O(n) | x in lst |
| Slice | O(k) | lst[2:5] |
| Sort | O(n log n) | lst.sort() |