# Is Python List a Linked List or Array

In Python, list is implemented as a **Dynamic Array**. Dynamic arrays benefit from many of the advantages of arrays, including good [locality of reference](https://en.wikipedia.org/wiki/Locality_of_reference) and [data cache](https://en.wikipedia.org/wiki/Data_cache) utilization, compactness (low memory use), and [random access](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Cache_\(computing\))-friendly [data structures](https://en.wikipedia.org/wiki/Data_structure). 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**](https://en.wikipedia.org/wiki/Reference_\(computer_science\)) **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](http://ironpython.codeplex.com/SourceControl/BrowseLatest) 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`](http://docs.python.org/library/collections.html#collections.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.

{% embed url="<https://stackoverflow.com/questions/12274060/does-python-use-linked-lists-for-lists-why-is-inserting-slow>" %}

{% embed url="<https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented>" %}

{% embed url="<https://docs.python.org/2/library/collections.html>" %}