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 and utilization, compactness (low memory use), and . 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 -friendly . 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 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 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 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.
