Adding elements to list

When an element is added to the end of a list, the time needed is \(O(1)\) or \(O(n)\) depending on whether the memory area reserved for the list has room for the new element or not. If there is no room, a new, bigger memory area is reserved and all the elements are copied there from the old memory area.

Although the worst case time complexity is \(O(n)\), it can be shown that the amortized time complexity is \(O(1)\) with an appropriate method of memory reservation. Here amortized \(O(1)\) means that any series of $n$ operations takes $O(n)$ time. To achieve this complexity, one such method is to double the reserved memory area whenever more memory is needed.

Consider a situation, where the list contains \(n\) elements and it was just moved to a new memory area. That last relocation moved \(n\) elements, the one before that moved \(n/2\) elements, the one before that moved \(n/4\) elements, etc.. Thus the total number of element moves is:

Because \(n\) elements have been added to the list and the total number of moves is \(O(n)\), the number of moves per element addition is \(O(1)\).

More generally, if the size of the memory area is multiplied by \(c\) with each expansion, the number of moves is

where \(c\) is any constant bigger than \(1\). The constant \(c\) controls a tradeoff between efficiency and memory use. A bigger \(c\) means that there is less copying and more memory reserved but unused.

Python implementation

We can study the memory use of a Python list with the following code:

import sys

n = 100

numbers = []
old_size = 0

for i in range(n):
    new_size = sys.getsizeof(numbers)

    if new_size != old_size:
        print(len(numbers), new_size)
        old_size = new_size

    numbers.append(1)

The code uses the function sys.getsizeof that returns the memory used by the given object in bytes. The code creates an empty list and then adds elements to the list one at a time. Whenever the memory usage changes, the code prints out the length and memory use of the list.

In the test computer (CPython 3.10.6), the code prints:

0 56
1 88
5 120
9 184
17 248
25 312
33 376
41 472
53 568
65 664
77 792
93 920

This shows that an empty list requires 56 bytes of memory, and that each additional element needs 8 bytes. The memory usage grows when the number of elements grows to 1, 5, 9, 17, 25, etc.. For example, when the element count reaches 17, the new memory usage is 248 bytes and there is room for (248 - 56) / 8 = 24 elements. Thus the next expansion happens when the element count reaches 25.

Studying the list implementation in CPython shows that the number of elements that fit in the new memory area is \(n + \lfloor n/8 \rfloor + 6\) rounded down to the nearest multiple of 4, where $n$ is the element count that triggered the expansion. For example when \(n=17\), the formula evaluates to \(17+\lfloor 17/8 \rfloor + 6 = 25\) and the nearest multiple of 4 is \(24\). This means that the memory size changes approximately by the factor $9/8$ in each expansion.

Removing elements from list

Removing elements from the end of a list takes \(O(1)\) time by just keeping track of the position of the last element. However, this leaves unnecessary memory occupied. Mimicing the doubling scheme on insertions, one could copy the elements to a new memory area when the list becomes half empty, but there is a problem: Consider a series of alternating deletions and insertions on an initially half empty list. This would cause linear time reallocation at every step. To cope with this problem, one can postpone the reallocation until the list is three-quarters empty. One can then show that any series of \(n\) insertions and deletions at the end takes \(O(n)\) time. To observe this postponing of reallocation between insertions and deletions in Python, consider the following code that continues our previous example:

for i in range(n):
    new_size = sys.getsizeof(numbers)

    if new_size != old_size:       
        print(len(numbers), new_size)
        old_size = new_size
        for j in range(n):
            new_size = sys.getsizeof(numbers)
            if new_size != old_size:       
                print(len(numbers), new_size)
                break
            numbers.append(j)
        break

    numbers.pop()    

The code prints:

53 568
65 664

This means that after deleting 46 last elements, some unallocated memory is freed, but leaving enough space to fit 11 elements (in general, constant fraction of \(n\)) before allocating more memory.

Note that Python list syntax supports deletions from arbitrary positions, but such deletions always cause full reallocation. The following code illustates the efficiency gap:

import time

numbers = []
n = 100000
for i in range(n):
    numbers.append(i)

start = time.time()
for i in range(n):
    numbers.pop()
end = time.time()
print(end-start)

for i in range(n):
    numbers.append(i)
start = time.time()
for i in range(n):
    numbers.pop(0)
end = time.time()
print(end-start)

The code prints:

0.003998279571533203
8.7571702003479