--- title: Lists source: 'https://academia.sh/en/courses/python-data-structures/lists' course: 'Data Structures and Functional Tools' language: en updated: '2026-08-17T18:10:25+00:00' license: 'CC BY-SA 4.0' --- # Lists A list holds not the items but the links to them; putting a thousand items in creates 1000 objects but binding the list to a second name creates 0, appending the same item five times creates 1, and only three of eight growth forms build a new container. 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. ```python """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. ```python """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. ```python """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**.