Is Python List a Linked List or Array
Last updated
Last updated
In Python, list is implemented as a Dynamic Array. Dynamic arrays benefit from many of the advantages of arrays, including good locality of reference and data cache utilization, compactness (low memory use), and random access. They usually have only a small fixed additional overhead for storing information about the size and capacity. This makes dynamic arrays an attractive tool for building cache-friendly data structures. However, in languages like Python or Java that enforce reference semantics, the dynamic array generally will not store the actual data, but rather it will store references to the data that resides in other areas of memory. In this case, accessing items in the array sequentially will actually involve accessing multiple non-contiguous areas of memory, so the many advantages of the cache-friendliness of this data structure are lost
How to achieve it is implementation dependent, but IIRC (if I recall correctly):
CPython uses an array of pointers
Jython uses an ArrayList
IronPython apparently also uses an array. You can browse the source code to find out.
Thus they all have O(1) random access.
In Python, list object is optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.
Since list uses contiguous blocks of memory to make indexing fast. We can use a deque if we want the “frequent insert“ performance characteristics of a linked list. But even in linked list, middle insertion is also slow, but two-ends appends and pops are O(1) fast.
Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.
