Verkettete Liste in Python

Problem

Die Warteschlange, die den Versand bremst

Der Server verschickt E-Mails aus einer Warteschlange. Neue kommen hinten hinein, dringende (ein Passwort-Reset) vorne, und der Worker nimmt immer die erste. Der Code benutzt die gewöhnliche Liste:

emails = []
emails.append("Rechnung")
emails.append("Newsletter")
emails.append("Bericht")
emails.insert(0, "Passwort")
next_email = emails.pop(0)
print("Sende: " + next_email)
print("Übrig: " + ", ".join(emails))

Sende: Passwort
Übrig: Rechnung, Newsletter, Bericht

Am Montagmorgen füllt der Newsletter an alle Kunden die Warteschlange mit 100.000 E-Mails. Der Worker verschickt langsamer als sonst, dann fast nichts mehr, und die Passwort-Reset-E-Mails kommen Minuten zu spät.

Der Grund: Die Liste ist ein dynamisches Array. Wer die erste nimmt, schiebt alle anderen einen Platz nach vorn, und eine dringende vorne schiebt alle zurück. 100.000 E-Mails nacheinander zu verschicken sind 99.999 + 99.998 + … + 1 = 4.999.950.000 Verschiebungen, nur um jedes Mal die erste zu nehmen.

Die Idee

Knoten, head und tail

Den Knoten und das Einfügen am Anfang hast du schon in der Lektion „Stack, Queue und verkettete Liste“ gesehen: Jedes Element ist ein eigenes Objekt mit einem Wert und einem Pfeil next zum nächsten. Hier schreibst du die ganze Klasse und rechnest aus, was jede Operation kostet.

Die Liste hält drei Dinge:

head: der erste Knoten. Von dort beginnt jedes Durchlaufen.
tail: der letzte Knoten. Mit ihm läuft das Hinzufügen am Ende nicht durch die ganze Liste.
die Größe, damit nicht jedes Mal gezählt werden muss.

Beide Enden müssen nach jeder Operation stimmen. Die leere Liste hat head und tail gleich None. Eine Liste mit einem Knoten hat head und tail, die auf denselben Knoten zeigen. Fast jeder Fehler in einer verketteten Liste ist ein vergessenes Ende: Du entfernst den letzten, und tail zeigt noch auf ihn.

Sieh es dir an

Deine eigene verkettete Liste

Hier ist die ganze Klasse. Die Knoten bewegen sich nie: Jede Operation ändert nur Pfeile.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def remove_first(self):
        if self.head is None:
            raise IndexError("die Liste ist leer")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value

    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)

Sieh dir an, welche Pfeile sich bei jeder Operation ändern:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def __init__(self):
    self.head = None
    self.tail = None
    self.size = 0

def remove_first(self):
    if self.head is None:
        raise IndexError("die Liste ist leer")
    value = self.head.value
    self.head = self.head.next
    if self.head is None:
        self.tail = None
    self.size -= 1
    return value

def remove(self, value):
    prev = None
    n = self.head
    while n is not None and n.value != value:
        prev = n
        n = n.next
    if n is None:
        return False
    if prev is None:
        self.head = n.next
    else:
        prev.next = n.next
    if n is self.tail:
        self.tail = prev
    self.size -= 1
    return True

Schritt für Schritt, in Worten

Drei E-Mails, jede in ihrem eigenen Knoten: der Wert und next, der Pfeil zum nächsten. head zeigt auf den ersten, tail auf den letzten.
add_first(„Passwort“): ein neuer Knoten, sein next zeigt auf den alten ersten, und head springt auf ihn. Zwei Pfeile, nichts wird verschoben: O(1).
add_last(„Einladung“): tail kennt den letzten schon, also wird nichts durchlaufen. Sein next zeigt auf den neuen Knoten, und tail wandert weiter: O(1).
remove_first(): head wandert zum nächsten Knoten. Auf „Passwort“ zeigt nichts mehr, und sein Speicher wird von selbst freigegeben.
remove(„Newsletter“): Knoten haben keinen Index. n startet bei head und läuft, bis er ihn findet; prev bleibt einen Knoten dahinter. Das ist O(n).
prev.next = n.next: Ein Pfeil führt um „Newsletter“ herum. „Bericht“ und „Einladung“ bewegen sich nicht.
An den Enden: zwei Pfeile, O(1). In der Mitte: ein Pfeil, aber zur Stelle kommst du Schritt für Schritt, O(n).

emails = SimpleLinkedList()
emails.add_last("Rechnung")
emails.add_last("Newsletter")
emails.add_last("Bericht")
emails.add_first("Passwort")
emails.add_last("Einladung")
print(emails)
print("Sende: " + str(emails.remove_first()))
emails.remove("Newsletter")
print(emails)
print("Position von Bericht: " + str(emails.find("Bericht")))
print("E-Mails: " + str(len(emails)))

Passwort → Rechnung → Newsletter → Bericht → Einladung
Sende: Passwort
Rechnung → Bericht → Einladung
Position von Bericht: 1
E-Mails: 3

remove_first auf einer leeren Liste wirft IndexError, wie deque.popleft. __str__ ist das, was print(emails) ausgibt. get ist eine Methode und kein [i]: So siehst du, dass sie das Element Schritt für Schritt erreicht.

Probier es aus

Sag die Ausgabe voraus

Sieben Operationen hintereinander. Achte darauf, welche nach dem Entfernen die letzte ist:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def remove_first(self):
        if self.head is None:
            raise IndexError("die Liste ist leer")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value

    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)


emails = SimpleLinkedList()
emails.add_first("Bericht")
emails.add_first("Rechnung")
emails.add_last("Einladung")
emails.remove_first()
emails.add_first("Passwort")
emails.remove("Einladung")
emails.add_last("Newsletter")
print(emails)
print("E-Mails: " + str(len(emails)))

Antwort

Passwort → Bericht → Einladung → Newsletter
E-Mails: 4

Passwort → Bericht
E-Mails: 3

Passwort → Bericht → Newsletter
E-Mails: 3

Die Idee

Was was kostet: Array gegen verkettete Liste

Operation	Dynamisches Array	Verkettete Liste
Lesen über den Index	O(1)	O(n)
vorne hinzufügen	O(n)	O(1)
hinten hinzufügen	O(1) amortisiert	O(1) mit tail
den ersten entfernen	O(n)	O(1)
den letzten entfernen	O(1)	O(n), doppelt verkettet: O(1)
in der Mitte	O(n): Verschieben	O(n): Laufen bis zur Stelle

Die letzte Zeile ist die Falle. Das Umhängen in der Mitte ist für sich genommen O(1), aber zur Stelle kommst du von head aus, Schritt für Schritt. Die verkettete Liste gewinnt in der Mitte nur, wenn du den Knoten schon hältst, zum Beispiel weil du ihn gerade mit einer Hashtabelle gefunden hast.

Es gibt auch einen Preis im Speicher. Das Array hält die Werte (oder die Referenzen) nebeneinander. Jeder Knoten ist ein eigenes Objekt: der Wert, der Pfeil und der Kopf, den die Laufzeitumgebung für jedes Objekt anlegt. Bei kleinen Werten braucht ein Knoten mehrfach so viel Speicher wie ein Platz im Array.

Sieh es dir an

Miss es nach

Einfügen am Anfang: das dynamische Array aus der vorherigen Lektion gegen die verkettete Liste. Wir zählen die Schreibvorgänge von Elementen: beim Array das neue und jedes Verschieben, bei der Liste nur den neuen Knoten. Die Pfeile, die sich ändern, sind zwei pro Einfügen und wachsen nicht mit n.

Vorne einfügen O(n²)
Verkettete Liste: vorne O(n)

Algorithmus	n = 10	n = 1.000	n = 10.000	n = 100.000
Vorne einfügen	63	501.516	50.021.376	≈ 5.002.137.600
Verkettete Liste: vorne	10	1.000	10.000	100.000

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def remove_first(self):
        if self.head is None:
            raise IndexError("die Liste ist leer")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value

    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)

Bei 10.000 E-Mails macht das Array 50.021.376 Schreibvorgänge und die verkettete Liste 10.000.

Jetzt umgekehrt: jedes Element über den Index lesen, get(0), get(1) und so weiter bis zum Ende. Wir zählen die Stellen, die du erreichst: Im Array ist get(i) ein Sprung, in der Liste durchläuft es i + 1 Knoten.

Array: get(i) für jedes i O(n)
Verkettete Liste: get(i) für jedes i O(n²)

Algorithmus	n = 10	n = 1.000	n = 10.000	n = 100.000
Array: get(i) für jedes i	10	1.000	10.000	100.000
Verkettete Liste: get(i) für jedes i	55	500.500	50.005.000	≈ 5.000.500.000

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def remove_first(self):
        if self.head is None:
            raise IndexError("die Liste ist leer")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value

    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)

Bei 10.000 Elementen macht das Array 10.000 Sprünge und die verkettete Liste 50.005.000 Schritte. Eine Schleife über den Index auf einer verketteten Liste ist O(n²). Lauf stattdessen mit der Schleife entlang der Pfeile (oder mit for-each) durch, wie es __str__ tut: Das ist O(n).

Genauer, für Neugierige

Dieselben Zahlen in deiner Sprache, mit Zählern in der Klasse:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
        self.writes = 0
        self.steps = 0

    def __len__(self):
        return self.size

    def add_first(self, value):
        node = Node(value)
        self.writes += 1
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def remove_first(self):
        if self.head is None:
            raise IndexError("die Liste ist leer")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        self.steps += 1
        for _ in range(index):
            n = n.next
            self.steps += 1
        return n.value

    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)


for n in [10, 1000, 100000]:
    list_ = SimpleLinkedList()
    for i in range(n):
        list_.add_first(str(1001 + i))
    print(f"am Anfang, n = {n}: {list_.writes} Schreibvorgänge")
for n in [10, 1000]:
    list_ = SimpleLinkedList()
    for i in range(n):
        list_.add_last(str(1001 + i))
    for i in range(n):
        list_.get(i)
    print(f"get(i) für jedes i, n = {n}: {list_.steps} Schritte")

am Anfang, n = 10: 10 Schreibvorgänge
am Anfang, n = 1000: 1000 Schreibvorgänge
am Anfang, n = 100000: 100000 Schreibvorgänge
get(i) für jedes i, n = 10: 55 Schritte
get(i) für jedes i, n = 1000: 500500 Schritte

Bench zählt Operationen, keine Zeit. Auf der Uhr ist der Unterschied beim Durchlaufen wegen des Caches noch größer zugunsten des Arrays: Das Array ist ein Block, die Knoten liegen verstreut, und der jeweils nächste ist vielleicht nicht im Cache. Das ist hier nicht gemessen, sondern nur erklärt, in der Lektion über das dynamische Array.

Probier es aus

Finde den Fehler

Ein Kollege hat add_last geschrieben. Drei E-Mails hinten angefügt, und die Liste sieht so aus:

emails = SimpleLinkedList()
emails.add_last("Rechnung")
emails.add_last("Newsletter")
emails.add_last("Bericht")
print(emails)
print("E-Mails: " + str(len(emails)))

Rechnung → Bericht
E-Mails: 3

Die Größe ist 3, und es sind zwei E-Mails. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Probier es aus

Ergänze

remove hat den Knoten n gefunden und den davor, prev. Worauf muss prev jetzt zeigen?

def remove(self, value):
    prev = None
    n = self.head
    while n is not None and n.value != value:
        prev = n
        n = n.next
    if n is None:
        return False
    if prev is None:
        self.head = n.next
    else:
        prev.next = 
    if n is self.tail:
        self.tail = prev
    self.size -= 1
    return True

Die Idee

Die doppelt verkettete Liste

Eine einfach verkettete Liste kann den letzten nicht schnell entfernen: Sie braucht den vorletzten, und auf den zeigt nichts zurück. Eine doppelt verkettete Liste hält in jedem Knoten zwei Pfeile, next und prev. Dann sind beide Enden O(1), und ein Knoten, den du schon hältst, wird mit vier Pfeilen entfernt, ohne den vorherigen zu suchen.

Der Preis ist ein weiterer Pfeil in jedem Knoten und mehr Umhängen bei jeder Operation.

collections.deque in Python ist doppelt verkettet, aber jeder Knoten ist ein Block aus 64 Elementen. So ist sie an beiden Enden schnell, und für die Pfeile wird weniger Speicher gebraucht.

Die Idee

Wo die verkettete Liste wirklich gewinnt

Für eine gewöhnliche Warteschlange ist die eingebaute besser. deque hält Blöcke von 64 Elementen und verschiebt nichts. Wie das funktioniert, steht in der Lektion Stapel und Warteschlange. Die verkettete Liste gewinnt, wenn du den Knoten schon hältst und ihn herausnehmen oder verschieben musst:

Ein LRU-Cache. Der Shop hält die zuletzt geöffneten Produkte im Speicher und wirft das am längsten nicht geöffnete hinaus. Eine Hashtabelle findet den Knoten des Produkts in O(1), und eine doppelt verkettete Liste schiebt ihn nach hinten. Der älteste steht immer vorne.
Verlauf mit Zurück und Vor. Browser und Editor halten die Schritte in einer doppelt verketteten Liste: Zurück und Vor sind ein Pfeil.
Die Listen im Kernel des Betriebssystems. Prozesse und Puffer tragen ihre Pfeile selbst und werden in O(1) aus der Liste genommen.

Hier ist ein LRU mit den eingebauten Mitteln, die letzten drei geöffneten Produkte:

from collections import OrderedDict


class Recent:
    def __init__(self, limit):
        self.limit = limit
        self.items = OrderedDict()

    def open(self, product):
        if product in self.items:
            self.items.move_to_end(product)
        else:
            if len(self.items) == self.limit:
                self.items.popitem(last=False)
            self.items[product] = True

    def __str__(self):
        return ", ".join(self.items)


recent = Recent(3)
for product in ["Laptop", "Maus", "Monitor", "Laptop", "Tastatur"]:
    recent.open(product)
    print(recent)

Laptop
Laptop, Maus
Laptop, Maus, Monitor
Maus, Monitor, Laptop
Monitor, Laptop, Tastatur

OrderedDict hält die Schlüssel in einer doppelt verketteten Liste. move_to_end schiebt das Produkt nach hinten, und popitem(last=False) wirft das älteste hinaus.

Übung

Eine doppelt verkettete Liste

Löse die Aufgabe in deinem Editor.

Von beiden Enden entfernen. Baue eine DoublyLinkedList: Der Knoten hat auch prev. Schreibe add_first, add_last, remove_first und remove_last, alle in O(1). Halte beide Enden richtig: Wird die Liste leer, sind head und tail beide None.

Füge die drei E-Mails hinten an und die mit dem Passwort vorne. Gib die Liste aus, entferne die letzte und die erste, gib sie wieder aus. Entferne zwei weitere von hinten, gib die Größe aus und füge dann die Einladung hinten an:

Passwort → Rechnung → Newsletter → Bericht
Letzte: Bericht
Erste: Passwort
Rechnung → Newsletter
E-Mails: 0
Einladung

Weitere Aufgaben

Die Mitte mit zwei Zeigern. Finde den mittleren Knoten in einem Durchlauf: Ein Zeiger geht einen Schritt, der andere zwei. Hat der schnelle das Ende erreicht, steht der langsame in der Mitte.
Ein Zyklus in der Liste. Ein Fehler hat den letzten Knoten an einen der vorherigen gehängt. Erkenne das mit denselben zwei Zeigern: Gibt es einen Zyklus, holt der schnelle den langsamen ein.
Alle Vorkommen entfernen. remove_all(self, value) entfernt in einem Durchlauf jeden Knoten mit diesem Wert und gibt zurück, wie viele es waren. Vergiss tail nicht.
LRU von Hand. Baue den LRU-Cache aus der Karte oben mit deiner eigenen doppelt verketteten Liste und einer dict vom Produkt zum Knoten.

Test

Teste dich

1. Eine verkettete Liste hat 1000 Knoten, und du behältst nur head. Wie viele Knoten durchläufst du, um das Element mit dem Index 999 zu lesen?Im Durchschnitt 500, egal bei welchem Index1: Die Adresse wird berechnet1000: von head den Pfeilen entlang bis dorthin

2. Wozu braucht man tail, wenn head schon die ganze Liste hält?Ohne tail läuft das Hinzufügen am Ende durch alle Knoten: O(n) statt O(1)Um die Größe zu kennenOhne tail kann man den ersten nicht entfernen

3. Was kostet in einer einfach verketteten Liste mit head und tail das Entfernen des letzten Knotens?O(n): Du brauchst den vorletzten, und zu dem kommst du von head ausO(1): tail kennt ihnO(log n)

4. Bench zeigt, dass das Einfügen am Anfang in einer verketteten Liste n Operationen macht und in einem dynamischen Array etwa n²/2. Warum ist das Array beim Durchlaufen trotzdem oft schneller?Das Array wird besser kompiliertDas Array ist ein Block im Speicher, und der Cache liest es zeilenweise; die Knoten liegen verstreutDie verkettete Liste macht mehr Vergleiche

5. Ein LRU-Cache behält die letzten 1000 geöffneten Produkte und wirft das am längsten nicht geöffnete hinaus. Was macht jedes Öffnen O(1)?Eine Hashtabelle alleinEin nach Zeit sortiertes ArrayEine Hashtabelle, die den Knoten findet, und eine doppelt verkettete Liste, in der der Knoten nach hinten wandert

Verkettete Liste

Cookies