Analyse des Java-LinkedList-Quellcodeprinzips und Erstellen einer Warteschlange über LinkedList

Hier stellen wir die einfachste verknüpfte Liste vor, LinkedList;

Sehen Sie sich die Methode add() an:

public boolean add(E e) {
        linkLast(e);        return true;
    }

void linkLast(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++;
        modCount++;
    }

Das Prinzip von add ist:

1. Rufen Sie zuerst den letzten Knoten der verknüpften Liste ab.

2. Fügen Sie den neuen Knoten nach dem letzten Knoten ein.

3. Das letzte Attribut von linkedList leitet zum letzten Knoten weiter.

4. Wenn dieser Knoten der erste Knoten ist und es keinen vorherigen Knoten gibt, verweisen Sie mit dem ersten Attribut der verknüpften Liste auf den neuen Knoten. Wenn nicht, verweisen Sie mit dem nächsten Attribut des vorherigen Knotens auf den Knoten.

Verwenden Sie LinkedList, um eine First-in-First-out-Warteschlange zu erstellen:

offer()-Methode zum Einreihen in die Warteschlange: Verwenden Sie die add()-Methode, um Knoten am Ende einzufügen .

public boolean offer(E e) {
        return add(e);
    }

poll()-Methode zum Entfernen aus der Warteschlange: Entfernen Sie die Warteschlange vom Kopf der verknüpften Liste

public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

Verwenden Sie LinkedList, um eine Last-in-First-out-Warteschlange zu erstellen:

push()-Methode in die Warteschlange einreihen: Knoten zuerst einfügen

public void addFirst(E e) {
        linkFirst(e);
    }

private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

pop()-Methode aus der Warteschlange entfernen: Beginnend mit dem Kopf der verknüpften Liste aus der Warteschlange entfernen

public E pop() {
        return removeFirst();
    }

public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

Abschließend ist zu beachten, dass LinkedList threadunsicher ist. Ja, wenn Sie Thread-Sicherheit benötigen, verwenden Sie bitte synchronisierte Sperren oder Vektoren oder verwenden Sie das Paket java.util.concurrent.

Wenn Sie ConcurrentModificationException vermeiden müssen, wenn ein Thread die Liste durchläuft, gibt es drei Lösungen.

1. Verwenden Sie synchronisierte Sperren, wenn Sie die Liste durchlaufen.

2. Verwenden Sie CopyOnWriteArrayList unter dem Paket java.util.concurrent Liste.

3. Verwenden Sie die foreach-Methode in Jdk8, aber diese Methode akzeptiert nur Lambda-Ausdrücke

list.forEach(item -> {
                    System.out.println("遍历元素：" + item);
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                });