Menu
How are lists in python stored internally? Is it an array? A linked list? Something else?
Or does the interpreter guess at the right structure for each instance based on length, etc.
If the question is implementation dependent, what about the classic CPython?
389
Python lists are internally represented as arrays. The idea used is similar to implementation of vectors in C++ or ArrayList in Java. The costly operations are inserting and deleting items near the beginning (as everything has to be moved). Insert at the end also becomes costly if preallocated space becomes full.
Lists can contain any Python object, including lists (i.e., list of lists). Lists are indexed and sliced with square brackets (e.g., list[0] and list[2:9]), in the same way as strings and arrays. Lists are mutable (i.e., their values can be changed in place).
Lists, then, are stored in distinct chunks of memory which are linked together with pointers, which enables efficient use of memory generally and doesn't require resizing. It also allows for the easy and quick manipulation of pointers when transforming the list.
Although Python lists are not fixed-size and constrained like arrays in C++ or Java, they are still array type data structures where the items contained are stored in memory sequentially and accessed by an index number representing the memory block for a specific element. A list object can contain duplicate elements.
from Core Python Containers: Under the Hood
List Implementation:
Fixed-length array of pointers
* When the array grows or shrinks, calls realloc() and, if necessary, copies all of the items to the new space
source code: Include/listobject.h and Objects/listobject.c
btw: here is the video
53
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
