What is list of arrays in python?

Question

I read in the Python time complexity page:

A deque (double-ended queue) is represented internally as a doubly linked list. (Well, a list of arrays rather than objects, for greater efficiency.) Both ends are accessible, but even looking at the middle is slow, and adding to or removing from the middle is slower still.

I don't understand the meaning of, 'list of arrays rather than objects', how it is related to a doubly linked list? Is the implementation of deque exactly like a doubly linked list, it will be useful if any more detail can be provided on its implementation.

Answer 1

You can read the source code of CPython (the Python reference implementation). The deque type is implemented in C (→ source code), but the code contains many comments that also discuss your question right at the top:

Textbook implementations of doubly-linked lists store one datum per link, but that gives them a 200% memory overhead (a prev and next link for each datum) and it costs one malloc() call per data element. By using fixed-length blocks, the link to data ratio is significantly improved and there are proportionally fewer calls to malloc() and free().

I.e. by using a doubly linked list of blocks (small arrays) the deque is more efficient in every respect than an ordinary doubly linked list.

The memory layout is something like:

NULL <- [ | | | | | | | ] <-> [ | | | | | | | ] -> NULL

i.e. the blocks are linked with each other. If we prepend or append an element but the firs/last block is already full, we can add another block.

This is not the only way to improve efficiency. E.g. instead of malloc() a custom arena allocator could be used, since every link in the linked list has the same size. However, using blocks of contiguous memory has better cache locality and reduces the overhead of the prev/next pointers.

There is an alternative data structure for queues with similar properties: a resizable circular buffer. However, circular buffers can be tricky to implement.

Answer 2

For each individual node to have a link to the one ahead and behind is costly, memory-wise, so sometimes you'll see an implementation which uses arrays to hold several items at once. The interface presented to the caller should remain transparent (in other words, it behaves exactly the same).

This incidentally was how memory management was done in C, as allocating memory in chunks too large was sometimes not possible to acquire, so you'd allocate smaller chunks and combine in a linked list.