why python list size is different in below 2 cases

Question

Both lists have 3 elements but why list size is different? Thanks!

l1.append(1)
l1.append(2)
l1.append(3)
print（l1.__sizeof__()） # the size is 72

l2 = [1,2,3]
print（l2.__sizeof__()） # the size is 64

Answer 1

l1.__sizeof__() was 72, but after appending another element it was still 72.

l1.append(4)
print(l1.__sizeof__()) # prints 72 again

So it seems appending may allocate too much space the first time, and will use up that space with extra appends.

l1 = []
print(l1.__sizeof__())  # prints 40
l1.append(1)
print(l1.__sizeof__())  # prints 72

4 elements - still prints 72
5 elements - prints 104

So, 72 - 40 = 32 (assume 40 bytes overhead for the list object)
32/4 = 8 (the non-overhead space for 4 integers)
8 bytes per element. Seems right for a 64-bit machine.

Applying that to the literally-defined list:

list with 3 elements of size 64.

64 - 40 = 24 # remove the fixed overhead size from the size of the list

24 / 8 = 3 # divide the remaining space by size of an integer

We get exactly 3 elements.

Yep, the literally defined list was allocated the exact amount of space it needed.

Answer 2

import time

empty_list_size = [].__sizeof__()  # 40 bytes

lyst = []
while True:
    list_size = (lyst.__sizeof__() - empty_list_size) // 8  # 8 bytes per element
    print(len(lyst), list_size)
    lyst.append("foo")
    time.sleep(.05)  # don't go too fast

Will output

0 0
1 4
2 4
3 4
4 4
5 8
6 8
7 8
8 8
9 16
10 16
11 16
12 16
13 16
14 16
15 16
16 16
17 25

and so on:

When you append to a list that doesn't have enough memory to store the element, it needs to be re-sized. Resizing means you get a new, bigger chunk of memory and then have to copy the entire list to it, which is expensive (linear time complexity). If you just appended to a list, there's a good chance you are going to append again and we want to avoid resizing the list on every append. So instead of resizing it to be big enough to fit the element(s) you want to append, the list is resized by some percentage of the size it is already. This effectively makes appending a constant time operation because as the list becomes larger, you still have to iterate over the entire list to copy it from time to time, but it becomes rarer the larger the list gets.

Whereas declaring a list literal l = [1, 2, 3] allocates exactly the amount of memory needed to hold a list of that size.

See https://en.wikipedia.org/wiki/Dynamic_array#Geometric_expansion_and_amortized_cost

This is implemented in CPython in listobject.c