# 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>" %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sisyphus.gitbook.io/project/python-notes/is-python-list-a-linked-list-or-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.