16.4    Doppelt verkettete Listen 

Betrachten wir einmal die beiden folgenden Varianten, eine Liste mit den Zahlen von 0 bis 9999 zu füllen. In der ersten Version werden die Zahlen einzeln jeweils am Ende der Liste angefügt:

l = []
for x in range(10000):
    l.append(x) 

In der zweiten Variante werden die Zahlen jeweils am Anfang der Liste eingefügt:

l = []
for x in range(9999, -1, -1):
    l.insert(0, x) 

Beide Beispiele erzeugen die gleiche Liste, doch es zeigt sich, dass die erste Variante um Größenordnungen schneller läuft als die zweite. Das liegt daran, dass der Basisdatentyp list im Hinblick auf den Zugriff über Indizes und das Anfügen neuer Elemente am Ende der Liste optimiert wurde. Beim Einfügen eines Wertes am Anfang einer Liste müssen alle in der Liste enthaltenen Elemente umkopiert – praktisch um eine Stelle nach rechts verschoben – werden.

Der Datentyp deque (für double-ended queue) des Moduls collections implementiert eine doppelt verkettete Liste, die das effiziente Einfügen von Elementen am Anfang oder am Ende unterstützt. Wenn in den oben genannten Beispielen eine deque-Instanz anstelle einer Liste verwendet würde, wäre kein Unterschied in der Laufzeit erkennbar.

Neben den Methoden append, copy, count, extend, index, insert, pop, remove und reverse sowie den Operatoren + und *, die vom Basisdatentyp list her bekannt sind, verfügt der Datentyp deque über die in Tabelle 16.2 aufgelisteten zusätzlichen Methoden.

Tabelle 16.2    Methoden des Datentyps deque

Das folgende Beispiel zeigt die Verwendung von deque-Instanzen:

>>> d = collections.deque([1,2,3,4])
>>> d.appendleft(0)
>>> d.append(5)
>>> d
deque([0, 1, 2, 3, 4, 5])
>>> d.extendleft([-2, -1])
>>> d
deque([-1, -2, 0, 1, 2, 3, 4, 5])
>>> d.rotate(4)
>>> d
deque([2, 3, 4, 5, -1, -2, 0, 1])

Darüber hinaus ist es möglich, bei der Instanziierung einer doppelt verketteten Liste eine Maximallänge festzulegen. Wenn in einer maximal langen Liste ein Element auf einer Seite angefügt wird, wird das letzte Element auf der anderen Seite entfernt.

>>> d = collections.deque([1,2,3,4], 4)
>>> d
deque([1, 2, 3, 4], maxlen=4)
>>> d.append(5)
>>> d
deque([2, 3, 4, 5], maxlen=4)
>>> d.appendleft(1)
>>> d
deque([1, 2, 3, 4], maxlen=4) 

Auf die Maximallänge einer deque-Instanz kann über das Attribut maxlen zugegriffen werden.