Java LinkedList addFirst()-Methode ausführlich erklärt

Java LinkedList Java LinkedList

addFirst()JaLinkedListEine wichtige Methode in der Klasse, die verwendet wird, um das angegebene Element am Anfang der verknüpften Liste einzufügen.

Methodensyntax

public void addFirst(E e)

Parameterbeschreibung

E e: Das Element, das am Anfang der verknüpften Liste hinzugefügt werden soll

Rückgabewert

Diese Methode hat keinen Rückgabewert (void).

Wie die addFirst()-Methode funktioniert

addFirst()Das Funktionsprinzip der Methode lässt sich kurz wie folgt beschreiben:

  1. Erstelle ein neues Knotenobjekt (Node)
  2. Richte den Zeiger des neuen Knotensnextauf den aktuellen Kopfknoten
  3. Richte den Zeiger des aktuellen Kopfknotensprevauf den neuen Knoten
  4. Aktualisiere die verkettete Listeheadauf den neuen Knoten
  5. Wenn die verkettete Liste zuvor leer war, richte auch den Zeiger des Endknotens auf den neuen Knoten
  6. Erhöhe den Größenzähler der verketteten Liste (size++)

Zeitkomplexität

Die Zeitkomplexität der Methode addFirst() ist O(1), denn egal wie groß die verkettete Liste ist, muss sie nur eine feste Anzahl von Operationen ausführen.

Anwendungsbeispiele

Sehen wir uns die konkrete Verwendung der Methode anhand einiger Beispiele an.addFirst()Beispiel 1: Grundlegende Verwendung

Beispiel 1: Grundlegende Verwendung

Beispiel

import java.util.LinkedList;

public class AddFirstExample {
    public static void main(String[] args) {
        // Anfangswerte hinzufügen
        LinkedList<String> fruits = new LinkedList<>();
       
        "Ursprüngliche verkettete Liste: "
        fruits.add("Banane");
        fruits.add("Orange");
       
        System.out.println(// Ausgabe: [Banane, Orange] + fruits);  // Verwende addFirst(), um ein Element am Anfang hinzuzufügen
       
        "Verkettete Liste nach dem Hinzufügen: "
        fruits.addFirst("Apfel");
       
        System.out.println(// Ausgabe: [Apfel, Banane, Orange] + fruits);  Beispiel 2: Aufeinanderfolgende Hinzufügungen
    }
}

Beispiel 2: Aufeinanderfolgende Hinzufügungen

Beispiel

import java.util.LinkedList;

public class ContinuousAddFirst {
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
       
        // Ausgabe: [1, 2, 3]
        numbers.addFirst(3);
        numbers.addFirst(2);
        numbers.addFirst(1);
       
        System.out.println(numbers);  // Beachte den Zusammenhang zwischen der Reihenfolge des Hinzufügens und dem Endergebnis
       
        Beispiel 3: Unterschied zur add()-Methode
    }
}

Beispiel 3: Unterschied zur add()-Methode

Beispiel

import java.util.LinkedList;

public class AddVsAddFirst {
    public static void main(String[] args) {
        LinkedList<String> list1 = new LinkedList<>();
        LinkedList<String> list2 = new LinkedList<>();
       
        // Verwende die addFirst()-Methode, um dieselben Elemente hinzuzufügen
        list1.add("A");
        list1.add("B");
        list1.add("C");
       
        "Mit add(): "
        list2.addFirst("C");
        list2.addFirst("B");
        list2.addFirst("A");
       
        System.out.println(// Ausgabe: [A, B, C] + list1);    "Mit addFirst(): "
        System.out.println(// Ausgabe: [A, B, C] + list2); // Obwohl das Endergebnis dasselbe ist, ist die Reihenfolge des Hinzufügens umgekehrt
       
        Hinweise
    }
}

Hinweise

1. Unterschied zur add()-MethodeaddFirst()Die Methode fügt Elemente standardmäßig am Ende der verketteten Liste hinzu

1. Unterschied zur add()-Methode

  • add()2. Unterschied zur offerFirst()-Methode
  • addFirst()Kann in einer kapazitätsbeschränkten Warteschlange eine Ausnahme auslösen

2. Unterschied zur offerFirst()-Methode

  • addFirst()anstatt eine Ausnahme auszulösen
  • offerFirst()3. Umgang mit Null-WertenfalseErmöglicht das Hinzufügen

3. Umgang mit Null-Werten

LinkedListist zulässig.null4. ThreadsicherheitaddFirst(null)ist nicht threadsicher; wenn sie in einer Multithread-Umgebung verwendet wird

4. Threadsicherheit

LinkedListPraktische AnwendungsszenarienaddFirst()Die Methode ist besonders nützlich in den folgenden Szenarien:

Praktische Anwendungsszenarien

addFirst()Da ein Stack eine "Last In, First Out"-(LIFO-)Struktur ist, können addFirst() und removeFirst() verwendet werden, um Stack-Operationen zu simulieren.

1. Implementierung einer Stack-Struktur

// Push auf den Stack

Beispiel

LinkedList<String> stack = new LinkedList<>();
stack.addFirst("Task1");  // Pop vom Stack, gibt "Task2" zurück
stack.addFirst("Task2");  2. Liste der zuletzt verwendeten Elemente
String top = stack.removeFirst();  Beim Implementieren einer Liste der zuletzt verwendeten Elemente (MRU) können neu zugegriffene Elemente am Anfang der Liste hinzugefügt werden.

2. Liste der zuletzt verwendeten Elemente

Durch das Hinzufügen von Elementen nacheinander zu einer neuen Liste mit addFirst() kann eine Listenumkehr erreicht werden.

3. Umkehroperation

// Ausgabe: [3, 2, 1]

Beispiel

LinkedList<Integer> original = new LinkedList<>(Arrays.asList(1, 2, 3));
LinkedList<Integer> reversed = new LinkedList<>();

for (Integer num : original) {
    reversed.addFirst(num);
}

System.out.println(reversed);  Die Methode hat eine sehr gute Performance in

Leistungsüberlegungen

addFirst()Erstellen eines neuen KnotensLinkedListEin paar Zeiger anpassen

  1. Egal, wie groß die verkettete Liste ist, die Zeit für diese Operationen ist konstant (O(1)-Zeitkomplexität). Das steht in scharfem Kontrast zu der
  2. Operation, die das Verschieben aller vorhandenen Elemente erfordert (O(n)-Zeitkomplexität).

Wenn Sie also häufig Elemente am Anfang einer Sammlung hinzufügen müssen,ArrayListvonadd(0, element)ist eine bessere Wahl als

.LinkedListHäufig gestellte FragenArrayListF1: Überschreibt addFirst() vorhandene Elemente?

Häufig gestellte Fragen

F1: Überschreibt addFirst() vorhandene Elemente?

F2: Wenn die verkettete Liste leer ist, funktioniert addFirst() dann trotzdem?addFirst()Ja, wenn die verkettete Liste leer ist,

F2: Wenn die verkettete Liste leer ist, funktioniert addFirst() dann trotzdem?

F3: Was ist der Unterschied zwischen addFirst() und push()?addFirst()In

F3: Was ist der Unterschied zwischen addFirst() und push()?

InLinkedListsind genau dieselbe Methode.addFirst()undpush()ist nurpush()ein anderer Name füraddFirst(), verwendet, um zu ermöglichen, dassLinkedListals Stapel verwendet wird.

Q4: Warum zeigt meine IDE an, dass addFirst() eine Methode von Deque ist?

WeilLinkedListimplementiert dieDequeSchnittstelle,addFirst()ist tatsächlichDequeeine in derLinkedListSchnittstelle definierte Methode, und

Zusammenfassung

LinkedListvonaddFirst()ZusammenfassungLinkedListDie Methode ist eine effiziente Operation, die es uns ermöglicht, Elemente am Anfang einer verketteten Liste einzufügen. Das Verständnis dieser Methode ist sehr wichtig für die effektive Verwendung von

, insbesondere in Szenarien, in denen Elemente häufig am Anfang einer Sammlung eingefügt werden müssen.

  • addFirst()Überprüfung der Kernpunkte:
  • Fügt Elemente am Anfang der verketteten Liste ein
  • undadd()Die Zeitkomplexität ist O(1)
  • Andere Einfügeposition als bei der add()-Methode
  • Wird häufig verwendet, um Stack-Strukturen und Listen der zuletzt verwendeten Elemente zu implementieren

Erfordert zusätzliche Synchronisation in Multithread-UmgebungenaddFirst()Durch die Verwendung derLinkedListMethode sinnvoll, die Leistungsvorteile von

Java LinkedList Java LinkedList

in bestimmten Szenarien voll ausgeschöpft werden können.