Lists

The Python Fundamentals course spent sixteen lessons measuring a single claim: syntax is an abbreviation, and every form of it calls a specific special method. The distinction it left at its close was this: using a protocol and writing a protocol are separate things. The object measured there was a fictional one; it descended from no built-in collection, and the only reason it could enter a for loop was that it had defined the relevant methods.

In this course, the language’s own containers carry the same protocols. They too define the same methods, but no longer for demonstration — for real data. And with real data, the question changes: not what a container can do, but what it costs. This is this lesson’s question — when a list is built, how many objects come into existence, how many of them are the list’s own product, and how many of them does the list keep alive?

What a Container Holds

A list does not contain its items. It holds an ordered sequence of slots, and every slot is a link to an object. This distinction is not specific to Python, it is a direct consequence of the object model: binding a value to a name does not copy the object, it gives it one more name. That assignment is a binding, the is/== distinction, and the alias concept were already established in the Programming Fundamentals course and are not repeated here. What’s new is that the same binding can be made to a slot, not just a name.

The consequence: every operation that grows a list increases the slot count, but it may not increase the object count. The same object can sit in five slots; the list is then five long and holds a single object.

The structural theory of ordered containers — array, dynamic array, linked list, growth rate — was built in the Data Structures course and is not repeated here. That built the mechanism; here, what’s measured is which container Python delivers that mechanism through, and what it costs in objects.

The Shared Setup: An Item That Counts Its Own Creation

A single class is enough for the measurement. Item increments a shared counter by one on every creation; it does nothing else. To know how many objects an operation creates, resetting the counter, doing the operation, and reading the counter is enough. The setup is its own oracle: creation is known because the object counts itself, sharing is known because is shows it. Three numbers are written separately throughout the course — objects created, slots held, and how many of them go to distinct objects.

An object’s identity is never printed as a number anywhere. Whether two slots point to the same object is tested only with is; the distinct-object count is the sum of these tests.

• CO1 — The counter counts only Item creation; the list, tuple, or another container itself is not counted. Container count is read separately, through an identity test.
• CO2 — In every row, the counter resets right before the operation; what’s measured is only what that row creates.
• CO3 — The distinct-object count is found through is comparisons; no identity value is printed, and no further inference about identity is drawn from a number.
• CO4 — The thousand-item measurement tests not the list’s growth behavior but only the count of objects created; growth class is the subject of the Algorithms course and is not measured here.
• CO5 — In the multiplication measurement, the multiplied list is single-item; this makes the difference between duplicating slots and duplicating objects visible on its own.

"""A list is a container: it holds slots, it does not materialize items itself."""

COUNTER = {"created": 0}


class Item:
    """An item that counts every time one is created."""

    def __init__(self, value):
        COUNTER["created"] += 1
        self.value = value

    def __repr__(self):
        return f"Item({self.value})"


def reset():
    COUNTER["created"] = 0


def created():
    return COUNTER["created"]


def distinct(container):
    """Count of identity-distinct objects. Identity is tested with `is`, never printed as a value."""
    unique = []
    for x in container:
        if not any(x is y for y in unique):
            unique.append(x)
    return len(unique)


N = 1000

print(f"{'operation':<36s}{'created':>9s}{'slots':>7s}{'distinct objects':>18s}")

reset()
lst = []
for i in range(N):
    lst.append(Item(i))
print(f"{'putting a thousand items in a list':<36s}{created():>9d}{len(lst):>7d}"
      f"{distinct(lst):>18d}")

reset()
alias = lst
print(f"{'binding the list to a second name':<36s}{created():>9d}"
      f"{len(alias):>7d}{distinct(alias):>18d}")

reset()
single = Item(0)
manual = [single, single, single, single, single]
print(f"{'appending the same item five times':<36s}{created():>9d}{len(manual):>7d}"
      f"{distinct(manual):>18d}")

reset()
product = [single] * 5
print(f"{'multiplying a one-item list by five':<36s}{created():>9d}"
      f"{len(product):>7d}{distinct(product):>18d}")

print()
print(f"alias is lst -> {alias is lst} | "
      f"product[0] is product[4] -> {product[0] is product[4]} | "
      f"product[0] is single -> {product[0] is single}")
print(f"lst[0] is lst[1] -> {lst[0] is lst[1]}")

operation                             created  slots  distinct objects
putting a thousand items in a list       1000   1000              1000
binding the list to a second name           0   1000              1000
appending the same item five times          1      5                 1
multiplying a one-item list by five         0      5                 1

alias is lst -> True | product[0] is product[4] -> True | product[0] is single -> True
lst[0] is lst[1] -> False

What the Four Rows Say

The first row is as expected: putting in a thousand items creates 1000 objects, holds 1000 slots, and all of them are distinct objects. But what creates these 1000 objects is not the list. The Item(i) call produced them; the list only held the slots. The same thousand objects could have been created without ever being put in a list, and the counter would still show 1000.

The second row proves this: binding the same list to a second name creates 0 objects. The slot count does not change, the distinct-object count does not change, only the number of names pointing to the object increases by one — and alias is lst confirms it. Passing a thousand-item list to a function is the same thing, and it costs the same: zero.

The third row shows the distinction in reverse. There are five slots, but objects created is 1 and distinct objects is 1. The list is five long, holding a single object. The fourth row produces the same result through the syntax itself: [single] * 5 creates nothing — 0 — and all five slots go to the same object. Multiplication duplicates slots, not objects.

The last two lines give identity tests. product[0] is product[4] is True: the slots multiplication produced share the same object. lst[0] is lst[1] is False: in the thousand-item list, every slot goes to a distinct object, because each one came from a separate Item(i) call. Both lists are five or a thousand long; what determines the difference is not length, it is where the slots point.

Forms of Growing

There is more than one way to write growing a list, and they do not all give the same length or the same container. In the Python Fundamentals course, the n + m versus n += m distinction was measured by which method they call: the first __add__, the second __iadd__. What’s measured here is how many containers the same distinction creates. The second measurement lines up eight forms side by side and asks each three questions: how many new items were created, did the result stay the same container, and how many slots go to an already existing object.

• CO6 — All eight forms start from a freshly built list of the same five-item pool; the pool’s items are created before the measurement, and the counter resets before each form.
• CO7 — The “same container” column is an is comparison between the reference held before the operation and the result; container count is not printed, only sameness is tested.
• CO8 — The “slots to old objects” column is found by testing each slot in the result with is against an object in the pool or the extra list.
• CO9 — The sort measurement is done with a key function; no comparison method is added to the item class, so the counting order does not change. How many comparisons the sort does is not measured in this lesson.

"""Forms of growing a list: which build a new container, which grow the existing one."""

COUNTER = {"created": 0}


class Item:
    def __init__(self, value):
        COUNTER["created"] += 1
        self.value = value

    def __repr__(self):
        return f"Item({self.value})"


def reset():
    COUNTER["created"] = 0


def created():
    return COUNTER["created"]


def value(o):
    return o.value


POOL = [Item(i) for i in (3, 1, 4, 1, 5)]
EXTRA = [Item(i) for i in (9, 2, 6)]
OLD = POOL + EXTRA


def append_end(a):
    a.append(Item(0))
    return a


def insert_start(a):
    a.insert(0, Item(0))
    return a


def extend_list(a):
    a.extend(EXTRA)
    return a


def concat(a):
    return a + EXTRA


def inplace_concat(a):
    a += EXTRA
    return a


def multiply(a):
    return a * 2


def sort_new(a):
    return sorted(a, key=value)


def sort_inplace(a):
    a.sort(key=value)
    return a


FORMS = (("a.append(new)", append_end), ("a.insert(0, new)", insert_start),
         ("a.extend(b)", extend_list), ("a = a + b", concat),
         ("a += b", inplace_concat), ("a = a * 2", multiply),
         ("a = sorted(a, ...)", sort_new), ("a.sort(...)", sort_inplace))

print(f"{'form':<20s}{'new items':>10s}{'same container':>16s}{'slots':>7s}"
      f"{'slots to old objects':>22s}")
for label, op in FORMS:
    a = list(POOL)
    before = a
    reset()
    result = op(a)
    old_count = sum(1 for x in result if any(x is y for y in OLD))
    print(f"{label:<20s}{created():>10d}{str(result is before):>16s}"
          f"{len(result):>7d}{old_count:>22d}")

form                 new items  same container  slots  slots to old objects
a.append(new)                1            True      6                     5
a.insert(0, new)             1            True      6                     5
a.extend(b)                  0            True      8                     8
a = a + b                    0           False      8                     8
a += b                       0            True      8                     8
a = a * 2                    0           False     10                    10
a = sorted(a, ...)           0           False      5                     5
a.sort(...)                  0            True      5                     5

Same Length, Different Cost

The “new items” column is 0 in six of the eight rows. Only append and insert create one object each, from the Item(0) call written to be appended. The remaining six forms do not produce a single item: all of them open new slots pointing to existing objects, or rearrange existing slots. The last column confirms this row by row — every slot, except the freshly appended item, goes to an object created before the measurement.

The real distinction is in the “same container” column. a.extend(b) and a = a + b give the same eight-item result, but one grows the existing container, the other builds a new container and binds the name to it. a += b, despite its name, does not add, it extends: the result is the same container. In the Python Fundamentals course, these two were counted as calling separate special methods; the number here is that call’s result. For the difference to be observable, another name bound to the list is enough: written as a += b, that name sees the lengthened list too; written as a = a + b, it stays on the old five-item list.

sorted and sort repeat the same pair on the sorting side. Both produce 0 new items, and both results have 5 slots; the difference is that one returns a new container while the other rearranges the existing one in place. sort does not return a list, it returns None — because there is no new container to return.

One thing is outside this table and cannot be found by looking at it: append and insert(0, ...) give the same numbers, yet what they do is not the same. Inserting at the front requires shifting every slot after it, appending at the end does not. This difference does not show up in the object count, because shifting does not create objects — it only rewrites slots. The growth class of shifting was built in the Algorithms course and is not repeated here; on the axis this lesson measures, the two forms really are equal.

What Deleting Releases

The insertion side showed that a container does not create objects. The deletion side shows the flip side: a container does not destroy objects either. Deletion operations only close a slot; whether the object keeps living is decided by other names and other slots still bound to it. The third measurement empties a list with four separate forms and checks, at every step, a second container bound to the same item.

• CO10 — The measurement proceeds sequentially on a single list; every row continues from the state the previous one left, so slot counts go down as a result.
• CO11 — The second container is built at the start of the measurement and is never touched throughout it; any change to it could only have come from the first container.
• CO12 — Deletion that looks at equality falls back to identity, since the item class defines no equality; this lesson does not measure with an item that defines equality.

"""Deleting does not destroy an object, it breaks a link. A shared item stays in the other container."""

COUNTER = {"created": 0}


class Item:
    def __init__(self, value):
        COUNTER["created"] += 1
        self.value = value

    def __repr__(self):
        return f"Item({self.value})"


def reset():
    COUNTER["created"] = 0


def created():
    return COUNTER["created"]


reset()
a = [Item(i) for i in range(5)]
held = a[2]
c = [a[0], a[2]]
setup_count = created()

print(f"{'operation':<26s}{'created':>9s}{'a slots':>9s}{'c slots':>9s}"
      f"{'c[1] is held':>14s}")
print(f"{'building with five items':<26s}{setup_count:>9d}{len(a):>9d}{len(c):>9d}"
      f"{str(c[1] is held):>14s}")


def pop_end():
    a.pop()


def del_start():
    del a[0]


def remove_eq():
    a.remove(held)


def clear_all():
    a.clear()


for label, op in (("a.pop()", pop_end), ("del a[0]", del_start),
                  ("a.remove(held)", remove_eq), ("a.clear()", clear_all)):
    reset()
    op()
    print(f"{label:<26s}{created():>9d}{len(a):>9d}{len(c):>9d}"
          f"{str(c[1] is held):>14s}")

print()
print(f"item still held after a is empty: {held} | c: {c}")

operation                   created  a slots  c slots  c[1] is held
building with five items          5        5        2          True
a.pop()                           0        4        2          True
del a[0]                          0        3        2          True
a.remove(held)                    0        2        2          True
a.clear()                         0        0        2          True

item still held after a is empty: Item(2) | c: [Item(0), Item(2)]

All four deletion forms create 0 objects — that was expected. What they actually say is in the two right columns. While the first container’s slot count drops from five to zero, the second container’s stays fixed at 2, and c[1] is held is True in every row. Even after the first list is completely empty, the shared item can still be read: the last row prints Item(2).

The rule that follows: deleting from a container breaks that container’s link to the object; not the object itself. The object stays as long as another name or another slot remains bound to it. Emptying a thousand-item list does not mean those thousand objects become free — if some of the items sit in another container, they keep sitting there. What a container “holds” is therefore one of the three numbers measured: objects created says who did the work, slots held says the container’s size, and sharing says what deleting actually released.

Deletion that looks at equality adds one detail. remove finds a slot not by identity but by equality; since the item class in this measurement defines no equality, equality falls back to identity here, and the two criteria give the same result. With an item that defines equality, the two would diverge: remove would delete the first slot that looked equal, not the object actually held.

Summary

• A list does not contain its items; every slot is a link to an object. Putting in a thousand items creates 1000 objects, binding the list to a second name creates 0.
• Slot count and object count are separate numbers: appending the same item five times gives 5 slots and 1 distinct object, while [single] * 5 creates 0 objects and binds five slots to the same object.
• Of the eight forms of growing, only append and insert create a new item; the remaining six only open slots, and all those slots go to already existing objects.
• a = a + b, a = a * 2, and sorted build a new container; extend, a += b, and sort mutate the existing container in place — same length, different container.
• Object count does not show every difference: append and insert(0, ...) are equal on this axis, because shifting slots does not create objects.

Next Step

Every measurement in this lesson rested on the list being mutable: a slot could be added, deleted, rearranged. What, then, does a container gain if it allows none of these? The next lesson repeats the same measurements on an immutable ordered container and asks two questions: which operation does immutability actually make impossible, and what capability does the container gain in exchange for that impossibility? One end of the answer will show up in something a list cannot do — being another container’s key.