Verkettete Liste in Java

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:

List<String> emails = new ArrayList<>();
emails.add("Rechnung");
emails.add("Newsletter");
emails.add("Bericht");
emails.add(0, "Passwort");
String next = emails.remove(0);
System.out.println("Sende: " + next);
System.out.println("Übrig: " + 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 null. 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 {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;

    int size() {
        return size;
    }

    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }

    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("die Liste ist leer");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(value)) {
            prev = n;
            n = n.next;
        }
        if (n == null) {
            return false;
        }
        if (prev == null) {
            head = n.next;
        } else {
            prev.next = n.next;
        }
        if (n == tail) {
            tail = prev;
        }
        size--;
        return true;
    }

    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }

    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}

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

class Node {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

private Node head;
private Node tail;
private int size;

String removeFirst() {
    if (head == null) {
        throw new NoSuchElementException("die Liste ist leer");
    }
    String value = head.value;
    head = head.next;
    if (head == null) {
        tail = null;
    }
    size--;
    return value;
}

boolean remove(String value) {
    Node prev = null;
    Node n = head;
    while (n != null && !n.value.equals(value)) {
        prev = n;
        n = n.next;
    }
    if (n == null) {
        return false;
    }
    if (prev == null) {
        head = n.next;
    } else {
        prev.next = n.next;
    }
    if (n == tail) {
        tail = prev;
    }
    size--;
    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.
addFirst(„Passwort“): ein neuer Knoten, sein next zeigt auf den alten ersten, und head springt auf ihn. Zwei Pfeile, nichts wird verschoben: O(1).
addLast(„Einladung“): tail kennt den letzten schon, also wird nichts durchlaufen. Sein next zeigt auf den neuen Knoten, und tail wandert weiter: O(1).
removeFirst(): 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).

SimpleLinkedList emails = new SimpleLinkedList();
emails.addLast("Rechnung");
emails.addLast("Newsletter");
emails.addLast("Bericht");
emails.addFirst("Passwort");
emails.addLast("Einladung");
System.out.println(emails);
System.out.println("Sende: " + emails.removeFirst());
emails.remove("Newsletter");
System.out.println(emails);
System.out.println("Position von Bericht: " + emails.find("Bericht"));
System.out.println("E-Mails: " + emails.size());

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

removeFirst auf einer leeren Liste wirft NoSuchElementException, wie LinkedList.removeFirst. Die Methode toString mit @Override ist das, was System.out.println(emails) ausgibt.

Probier es aus

Sag die Ausgabe voraus

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

class Node {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;

    int size() {
        return size;
    }

    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }

    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("die Liste ist leer");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(value)) {
            prev = n;
            n = n.next;
        }
        if (n == null) {
            return false;
        }
        if (prev == null) {
            head = n.next;
        } else {
            prev.next = n.next;
        }
        if (n == tail) {
            tail = prev;
        }
        size--;
        return true;
    }

    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }

    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}

SimpleLinkedList emails = new SimpleLinkedList();
emails.addFirst("Bericht");
emails.addFirst("Rechnung");
emails.addLast("Einladung");
emails.removeFirst();
emails.addFirst("Passwort");
emails.remove("Einladung");
emails.addLast("Newsletter");
System.out.println(emails);
System.out.println("E-Mails: " + emails.size());

Antwort

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

Passwort → Bericht → Newsletter
E-Mails: 3

Passwort → Bericht
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 {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;

    int size() {
        return size;
    }

    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }

    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("die Liste ist leer");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(value)) {
            prev = n;
            n = n.next;
        }
        if (n == null) {
            return false;
        }
        if (prev == null) {
            head = n.next;
        } else {
            prev.next = n.next;
        }
        if (n == tail) {
            tail = prev;
        }
        size--;
        return true;
    }

    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }

    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.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 {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;

    int size() {
        return size;
    }

    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }

    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("die Liste ist leer");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(value)) {
            prev = n;
            n = n.next;
        }
        if (n == null) {
            return false;
        }
        if (prev == null) {
            head = n.next;
        } else {
            prev.next = n.next;
        }
        if (n == tail) {
            tail = prev;
        }
        size--;
        return true;
    }

    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }

    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.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 toString tut: Das ist O(n).

Genauer, für Neugierige

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

class Node {
    String value;
    Node next;

    Node(String value) {
        this.value = value;
    }
}

class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;
    long writes = 0;
    long steps = 0;

    int size() {
        return size;
    }

    void addFirst(String value) {
        Node node = new Node(value);
        writes++;
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }

    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }

    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("die Liste ist leer");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(value)) {
            prev = n;
            n = n.next;
        }
        if (n == null) {
            return false;
        }
        if (prev == null) {
            head = n.next;
        } else {
            prev.next = n.next;
        }
        if (n == tail) {
            tail = prev;
        }
        size--;
        return true;
    }

    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        steps++;
        for (int i = 0; i < index; i++) {
            n = n.next;
            steps++;
        }
        return n.value;
    }

    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}

for (int n : new int[] {10, 1000, 100000}) {
    SimpleLinkedList list = new SimpleLinkedList();
    for (int i = 0; i < n; i++) {
        list.addFirst(String.valueOf(1001 + i));
    }
    System.out.println("am Anfang, n = " + n + ": " + list.writes + " Schreibvorgänge");
}
for (int n : new int[] {10, 1000}) {
    SimpleLinkedList list = new SimpleLinkedList();
    for (int i = 0; i < n; i++) {
        list.addLast(String.valueOf(1001 + i));
    }
    for (int i = 0; i < n; i++) {
        list.get(i);
    }
    System.out.println("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 addLast geschrieben. Drei E-Mails hinten angefügt, und die Liste sieht so aus:

SimpleLinkedList emails = new SimpleLinkedList();
emails.addLast("Rechnung");
emails.addLast("Newsletter");
emails.addLast("Bericht");
System.out.println(emails);
System.out.println("E-Mails: " + emails.size());

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?

boolean remove(String value) {
    Node prev = null;
    Node n = head;
    while (n != null && !n.value.equals(value)) {
        prev = n;
        n = n.next;
    }
    if (n == null) {
        return false;
    }
    if (prev == null) {
        head = n.next;
    } else {
        prev.next = ;
    }
    if (n == tail) {
        tail = prev;
    }
    size--;
    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.

LinkedList in Java ist doppelt verkettet. Sie hat addFirst, addLast, removeFirst, removeLast, und get(i) läuft vom näheren Ende aus.

Die Idee

Wo die verkettete Liste wirklich gewinnt

Für eine gewöhnliche Warteschlange ist die eingebaute besser. ArrayDeque ist ein Array, das beide Enden ohne Verschieben hält. 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:

class Recent {
    private final int limit;
    private final LinkedHashSet<String> items = new LinkedHashSet<>();

    Recent(int limit) {
        this.limit = limit;
    }

    void open(String product) {
        if (items.contains(product)) {
            items.remove(product);
        } else if (items.size() == limit) {
            items.removeFirst();
        }
        items.add(product);
    }

    @Override
    public String toString() {
        return String.join(", ", items);
    }
}

Recent recent = new Recent(3);
for (String product : new String[] {"Laptop", "Maus", "Monitor", "Laptop", "Tastatur"}) {
    recent.open(product);
    System.out.println(recent);
}

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

LinkedHashSet ist genau eine Hashtabelle plus eine doppelt verkettete Liste durch die Elemente, darum behält sie die Reihenfolge des Hinzufügens. remove und add schieben das Produkt nach hinten, und removeFirst 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 addFirst, addLast, removeFirst und removeLast, alle in O(1). Halte beide Enden richtig: Wird die Liste leer, sind head und tail beide null.

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. removeAll(String 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 HashMap 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