# List [[Mutability|Mutable]] [[Seq - Sequence|sequence]] of [[Object|objects]]. Similar to [[Fields/Development/Programming Languages/Python/Glossary/Array|Python arrays]] but can contain heterogeneous [[Type|types]] of [[Object|objects]]. ## CPython-Specific ### Implementation of Lists Overview of a list in [[CPython]] prior to 3.12: ![[cpython_list_details_prior_312.jpg]] #### Overview of `ob_item` At the core of a [[Python]] list lies the `ob_item` field, which is a dynamic [[Fields/Development/Programming Languages/Glossary/Array|C array]] of [[Pointer|pointers]] to `PyObjects`. This field acts as a container for [[Reference|references]] to all the items within a list. Notably, list items are never stored in `ob_item` "as values"; instead, they are referenced by [[Pointer|pointers]]. #### Why Pointers Instead of Values? In [[Python]], everything is an [[object]]. Storing [[Object|objects]] as values in the `ob_item` [[Fields/Development/Programming Languages/Glossary/Array|C array]] would require copying or moving these [[Object|objects]] frequently, which would be inefficient, computationally expensive, and error-prone. By using [[Pointer|pointers]], [[CPython]] avoids these issues, allowing efficient management of the [[Object|objects]] in [[memory]]. #### Dynamic Growth of `ob_item` The `ob_item` [[Fields/Development/Programming Languages/Glossary/Array|C array]] grows dynamically to accommodate new items as they are appended to the list. When necessary, [[CPython]] reallocates [[memory]] for the `ob_item` [[Fields/Development/Programming Languages/Glossary/Array|C array]], often increasing its capacity by 12.5% (or more for smaller list sizes).[^1] This strategy minimizes the frequency of reallocations and improves performance for repeated append operations. This growing-on-demand behavior allows [[Python]] lists to be perceived as flexible, dynamically resizable [[Fields/Development/Programming Languages/Glossary/Array|C array]] of [[Pointer|pointers]] to [[Object|objects]]. When a list is mutated (e.g., items are added, removed, or replaced), the changes occur within the `ob_item` [[Fields/Development/Programming Languages/Glossary/Array|C array]] by altering the [[Pointer|pointers]]. #### Reference Counting in CPython Each [[Python]] [[object]], including the elements pointed to by `ob_item`, has an associated [[reference count]]. Historically, the [[reference count]] was stored as a `Py_ssize_t` value. However, starting from [[CPython]] 3.12, the [[reference count]] resides within a union structure. This change likely supports optimizations such as the use of [[Immortal Object]]. #### Immortal Objects and Reference Counting Optimizations [[Immortal Object]], like commonly used [[Singleton|singletons]] (e.g., `None`, `True`, `False`), benefit from this new union-based representation of the [[reference count]]. These objects do not require [[reference count]] updates during program execution, enhancing performance and reducing overhead for these ubiquitous objects. --- Bibliography: - [What causes [*a] to overallocate? - stackoverflow.com](https://stackoverflow.com/a/60551320/6251742) [^1]: See comment in CPython 3.13 source code: https://github.com/python/cpython/blob/3.13/Objects/listobject.c#L129