Explain the principles of how memory managers work with lists and tuples in Python. How do the modification/addition of elements in a list and a tuple differ, and how does this affect performance?

Answer

In Python, lists (list) are mutable structures, while tuples (tuple) are immutable.

• list: When adding new elements (append, extend, insert), Python allocates memory "with a reserve" to minimize the number of allocations as the array grows ("over-allocation strategy"). Removing elements (pop, remove) happens quickly, but it can sometimes lead to memory reallocation.
• tuple: The size of a tuple is fixed, elements cannot be changed or added — this ensures high reading speed and less memory usage compared to lists when storing a large amount of immutable data.

Example illustrating the modification of list and tuple:

lst = [1, 2, 3]
lst.append(4)    # OK
lst[1] = 20      # OK

tup = (1, 2, 3)
tup[1] = 20      # TypeError

Performance:

• Lists are great for frequently changing collections.
• Tuples are slightly faster, more memory-efficient (due to fixed size and hashing principles), and suitable for dictionary keys, returned values from functions (immutable data).

---

Trick Question

Question: Why are adding elements to a list usually performed quickly (O(1)), if from the perspective of an array it should lead to memory reallocation?

Answer:

Python implements dynamic arrays with "extra memory allocation" for several elements at once. Therefore, append usually takes O(1), and memory reallocation occurs only when the reserve block is actually exhausted.

Example:

import sys
lst = []
for i in range(10):
    lst.append(i)
    print(len(lst), sys.getsizeof(lst))  # Memory size grows not strictly linearly

---

History

Example 1

---

In one project, lists were used for dictionary keys. The developer didn’t know that lists are not hashable (mutability), which caused the error "TypeError: unhashable type: 'list'".

---

Example 2

---

The developer frequently created long lists by concatenating them using +. This led to additional array copies and high memory and time overhead. It would have been more efficient to use append in a loop or generators.

---

Example 3

---

In a logging system, tuples were chosen for storing timestamps, thinking that immutability would make it faster. However, there was a periodic need for modification, which required constantly creating new tuples (copy-on-write) and slowed down work compared to using lists.

---