È possibile leggere il codice sorgente di CPython (l'implementazione di riferimento Python). Il tipo deque è implementato in C ( → codice sorgente ), ma il codice contiene molti commenti che parlano anche della tua domanda in alto:
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().
vale a dire. utilizzando un elenco di blocchi doppiamente collegati (piccoli array) la deque è più efficiente sotto ogni aspetto rispetto a una normale lista doppiamente collegata.
Il layout della memoria è simile a:
NULL <- [ | | | | | | | ] <-> [ | | | | | | | ] -> NULL
vale a dire. i blocchi sono collegati tra loro. Se anteponiamo o aggiungiamo un elemento ma l'ultimo / ultimo blocco è già completo, possiamo aggiungere un altro blocco.
Questo non è l'unico modo per migliorare l'efficienza. Per esempio. invece di malloc () potrebbe essere usato un allocatore di arena personalizzato, poiché ogni collegamento nella lista collegata ha le stesse dimensioni. Tuttavia, l'utilizzo di blocchi di memoria contigua ha una migliore localizzazione della cache e riduce il sovraccarico dei puntatori prev / next.
Esiste una struttura dati alternativa per le code con proprietà simili: un buffer circolare ridimensionabile. Tuttavia, i buffer circolari possono essere difficili da implementare.