Analyse des Java LinkedList-Quellcodes (Bild)

Allgemeine Einführung

LinkedList implementiert sowohl die ListSchnittstelle als auch die Deque-Schnittstelle, was bedeutet, dass es sowohl als sequenzieller Container als auch als Warteschlange (Warteschlange) betrachtet werden kann. und kann auch als Stapel (Stack) betrachtet werden. Aus dieser Sicht ist LinkedList einfach ein Allround-Champion. Wenn Sie einen Stapel oder eine Warteschlange verwenden müssen, sollten Sie als Erstes LinkedList in Betracht ziehen. Da Java offiziell erklärt hat, dass die Verwendung der Stack-Klasse nicht empfohlen wird, wird die Verwendung von LinkedList empfohlen. Noch bedauerlicher ist, dass es in Java keine Klasse namens Queue gibt (es ist ein Schnittstellenname).

Die zugrunde liegende Ebene von LinkedList wird durch eine doppelt verknüpfte Liste implementiert. Dieser Abschnitt konzentriert sich auf den Wartungsprozess einer doppelt verknüpften Liste beim Einfügen und Löschen Elemente, also die Lösung zwischen den -Funktionen im Zusammenhang mit der List-Schnittstelle und dem Wissen im Zusammenhang mit Queue, Stack und Deque, werden im nächsten Abschnitt besprochen. Jeder Knoten einer doppelt verknüpften Liste wird durch die innere Klasse Node repräsentiert. LinkedList-Referenzen first bis last und , um auf das erste bzw. letzte Element der verknüpften Liste zu verweisen. Beachten Sie, dass es hier kein sogenanntes Dummy-Element gibt. Wenn die verknüpfte Liste leer ist, verweisen sowohl first als auch last auf <a href="http://www.php.cn/wiki/62%20.html" target=" _blank">null<code><a href="http://www.php.cn/wiki/62.html" target="_blank">null</a>.

//Node内部类
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Die Implementierung von LinkedList bestimmt, dass alle tiefgestellten Vorgänge lineare Zeit erfordern und das Löschen von Elementen am Anfang oder Ende nur konstante Zeit erfordert. Aus Effizienzgründen implementiert LinkedList keine Synchronisierung (synchronized). Wenn ein gleichzeitiger Zugriff durch mehrere Threads erforderlich ist, können Sie ihn zuerst mit der Collections.synchronizedList()-Methode umschließen.

Methodenanalyse

add()

add()-Methode hat zwei Versionen, eine ist add(E e), diese Methode fügt Elemente am Ende von LinkedList ein, weil es < gibt 🎜>Zeigt auf das Ende der verknüpften Liste und das Einfügen von Elementen am Ende nimmt konstant Zeit in Anspruch. Sie müssen nur einige relevante Referenzen ändern. Die andere besteht darin, Elemente in die unten angegebene Tabelle einzufügen. Sie müssen zuerst die spezifische Position durch lineare Suche finden und dann die relevanten Referenzen ändern, um sie zu vervollständigen Einfügevorgang. lastadd(int index, E element)

In Kombination mit dem obigen Bild können wir sehen, dass die Logik von

sehr einfach ist. Die Logik von

add(E e)

//add(E e)
public boolean add(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;//原来链表为空，这是插入的第一个元素
    else
        l.next = newNode;
    size++;
    return true;
}

ist etwas kompliziert und kann in zwei Teile unterteilt werden: 1. Suchen Sie zunächst den einzufügenden Ort gemäß dem Index. 2. Ändern Sie die Referenz und schließen Sie den Einfügevorgang ab .

add(int index, E element)

Die Funktion

//add(int index, E element)
public void add(int index, E element) {
    checkPositionIndex(index);//index >= 0 && index <= size;
    if (index == size)//插入位置是末尾，包括列表为空的情况
        add(element);
    else{
        Node<E> succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用，完成插入操作。
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

im obigen Code ist etwas knifflig, da die verknüpfte Liste bidirektional ist und Sie vom Anfang nach hinten oder vom Ende nach vorne suchen können , es hängt davon ab, in welche Richtung Sie suchen möchten

, das heißt, ob sich der Index nahe am Front-End oder am Back-End befindet. Die Methode node(int index)index < (size >> 1)remove()

hat auch zwei Versionen. Eine besteht darin, das erste Element zu löschen, das dem angegebenen Element remove(<a href="http" entspricht :// www.php.cn/wiki/60.html" target="_blank">Object<p> o), das andere besteht darin, das Element remove() am angegebenen Index zu löschen. remove(<a href="http://www.php.cn/wiki/60.html" target="_blank">Object</a> o)remove(int index)

Beide Löschvorgänge erfordern 1. Zuerst das Finden der Referenz des zu löschenden Elements, 2. Ändern der relevanten Referenz, um den Löschvorgang abzuschließen. Bei der Suche nach der gelöschten Elementreferenz ruft

die Methode

des Elements auf, während remove(Object o) die Indexzählung verwendet. Beide Methoden haben eine lineare Zeitkomplexität. In Schritt 2 werden beide equals-Methoden über die remove(int index)-Methode vervollständigt. Hier müssen Sie den Grenzfall berücksichtigen, bei dem das gelöschte Element das erste oder letzte ist. revome()unlink(Node<E> x)

get()

//unlink(Node<E> x)，删除一个Node
E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {//删除的是第一个元素
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {//删除的是最后一个元素
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;//let GC work
    size--;
    return element;
}

Ruft den Verweis auf das Element am angegebenen Index ab, was durch Aufrufen der oben erwähnten

-Methode erreicht wird. Die Methode get(int index)node(int index)

set()

public E get(int index) {
    checkElementIndex(index);//index >= 0 && index < size;
    return node(index).item;
}

ändert das Element am angegebenen Index auf den angegebenen Wert. Außerdem findet sie zunächst die Referenz, die dem Element in der folgenden Tabelle entspricht

und ändert dann den Wert von set(int index, E element) in node(int index). Nodeitem

Das obige ist der detaillierte Inhalt vonAnalyse des Java LinkedList-Quellcodes (Bild). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!