Explication détaillée de la méthode addFirst() de Java LinkedList

Java LinkedList Java LinkedList

addFirst()OuiLinkedListUne méthode importante de la classe, utilisée pour insérer l'élément spécifié au début de la liste chaînée.

Syntaxe de la méthode

public void addFirst(E e)

Description du paramètre

E e: L'élément à ajouter au début de la liste chaînée

Valeur de retour

Cette méthode ne renvoie aucune valeur (void).

Fonctionnement de la méthode addFirst()

addFirst()Le principe de fonctionnement de la méthode peut être brièvement décrit comme suit :

  1. Créer un nouvel objet nœud (Node)
  2. Faire pointer lenextpointeur du nouveau nœud vers le nœud de tête actuel
  3. Faire pointer leprevpointeur du nœud de tête actuel vers le nouveau nœud
  4. Mettre à jour leheadpointeur du nœud de tête actuel vers le nouveau nœud
  5. Si la liste chaînée était précédemment vide, faire également pointer le nœud de queue vers le nouveau nœud
  6. Incrémenter le compteur de taille de la liste chaînée (size++)

Complexité temporelle

La complexité temporelle de la méthode addFirst() est O(1), car quelle que soit la taille de la liste chaînée, elle ne nécessite qu'un nombre fixe d'opérations.

Exemples d'utilisation

Regardons l'utilisation spécifique de la méthode à travers quelques exemples.addFirst()Exemple 1 : Utilisation de base

Exemple 1 : Utilisation de base

Exemple

import java.util.LinkedList;

public class AddFirstExample {
    public static void main(String[] args) {
        // Ajouter les éléments initiaux
        LinkedList<String> fruits = new LinkedList<>();
       
        "Liste chaînée originale : "
        fruits.add("Banane");
        fruits.add("Orange");
       
        System.out.println(// Sortie : [Banana, Orange] + fruits);  // Utilisez addFirst() pour ajouter un élément au début
       
        "Liste chaînée après ajout : "
        fruits.addFirst("Apple");
       
        System.out.println(// Sortie : [Apple, Banana, Orange] + fruits);  Exemple 2 : Ajouts consécutifs
    }
}

Exemple 2 : Ajouts consécutifs

Exemple

import java.util.LinkedList;

public class ContinuousAddFirst {
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
       
        // Sortie : [1, 2, 3]
        numbers.addFirst(3);
        numbers.addFirst(2);
        numbers.addFirst(1);
       
        System.out.println(numbers);  // Remarquez la relation entre l'ordre d'ajout et le résultat final
       
        Exemple 3 : Différence par rapport à la méthode add()
    }
}

Exemple 3 : Différence par rapport à la méthode add()

Exemple

import java.util.LinkedList;

public class AddVsAddFirst {
    public static void main(String[] args) {
        LinkedList<String> list1 = new LinkedList<>();
        LinkedList<String> list2 = new LinkedList<>();
       
        // Utiliser la méthode addFirst() pour ajouter les mêmes éléments
        list1.add("A");
        list1.add("B");
        list1.add("C");
       
        "Utilisation de add() : "
        list2.addFirst("C");
        list2.addFirst("B");
        list2.addFirst("A");
       
        System.out.println(// Sortie : [A, B, C] + list1);    "Utilisation de addFirst() : "
        System.out.println(// Sortie : [A, B, C] + list2); // Bien que le résultat final soit le même, l'ordre d'ajout est inversé
       
        Notes
    }
}

Notes

1. Différence par rapport à la méthode add()addFirst()La méthode ajoute des éléments à la fin de la liste chaînée par défaut

1. Différence par rapport à la méthode add()

  • add()2. Différence avec la méthode offerFirst()
  • addFirst()Peut lever une exception dans une file à capacité limitée

2. Différence avec la méthode offerFirst()

  • addFirst()au lieu de lever une exception
  • offerFirst()3. Gestion des valeurs nullfalsePermet d'ajouter

3. Gestion des valeurs null

LinkedListest autorisé.null4. Sécurité des threadsaddFirst(null)n'est pas sûr pour les threads ; s'il est utilisé dans un environnement multithread

4. Sécurité des threads

LinkedListScénarios d'application pratiquesaddFirst()La méthode est particulièrement utile dans les scénarios suivants :

Scénarios d'application pratiques

addFirst()Comme une pile est une structure « dernier entré, premier sorti » (LIFO), addFirst() et removeFirst() peuvent être utilisés pour simuler des opérations de pile.

1. Implémentation d'une structure de pile

// Empiler dans la pile

Exemple

LinkedList<String> stack = new LinkedList<>();
stack.addFirst("Task1");  // Dépiler de la pile, renvoie "Task2"
stack.addFirst("Task2");  2. Liste des plus récemment utilisés
String top = stack.removeFirst();  Lors de l'implémentation d'une liste des plus récemment utilisés (MRU), les éléments nouvellement consultés peuvent être ajoutés au début de la liste.

2. Liste des plus récemment utilisés

En ajoutant des éléments un par un à une nouvelle liste avec addFirst(), l'inversion de liste peut être réalisée.

3. Opération d'inversion

// Sortie : [3, 2, 1]

Exemple

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);  La méthode a de très bonnes performances dans

Considérations de performance

addFirst()Création d'un nouveau nœudLinkedListAjuster quelques pointeurs

  1. Peu importe la taille de la liste chaînée, le temps nécessaire à ces opérations est constant (complexité temporelle O(1)). Cela contraste nettement avec l’
  2. opération, qui nécessite de déplacer tous les éléments existants (complexité temporelle O(n)).

Par conséquent, si vous devez fréquemment ajouter des éléments au début d’une collection,ArrayListdeadd(0, element)est un meilleur choix que

.LinkedListQuestions fréquentesArrayListQ1 : addFirst() écrasera-t-il les éléments existants ?

Questions fréquentes

Q1 : addFirst() écrasera-t-il les éléments existants ?

Q2 : Si la liste chaînée est vide, addFirst() fonctionne-t-il encore ?addFirst()Oui, si la liste chaînée est vide,

Q2 : Si la liste chaînée est vide, addFirst() fonctionne-t-il encore ?

Q3 : Quelle est la différence entre addFirst() et push() ?addFirst()Dans

Q3 : Quelle est la différence entre addFirst() et push() ?

DansLinkedListsont exactement la même méthode.addFirst()etpush()n’est qu’push()un autre nom pouraddFirst(), utilisé pour permettreLinkedListd'être utilisé comme une pile.

Q4 : Pourquoi mon IDE m'indique-t-il que addFirst() est une méthode de Deque ?

Parce queLinkedListimplémente l'Dequeinterface,addFirst()est en faitDequeune méthode définie dans l'LinkedListinterface, et

Résumé

LinkedListdeaddFirst()RésuméLinkedListLa méthode est une opération efficace qui nous permet d'insérer des éléments au début d'une liste chaînée. Comprendre cette méthode est très important pour utiliser efficacement

, en particulier dans les scénarios où des éléments doivent être fréquemment insérés au début d'une collection.

  • addFirst()Récapitulatif des points clés :
  • Insère des éléments au début de la liste chaînée
  • etadd()La complexité temporelle est O(1)
  • Position d'insertion différente de la méthode add()
  • Couramment utilisé pour implémenter des structures de pile et des listes des éléments les plus récemment utilisés

Nécessite une synchronisation supplémentaire dans les environnements multithreadaddFirst()En utilisant laLinkedListméthode de manière raisonnable, les avantages de performance de

Java LinkedList Java LinkedList

dans des scénarios spécifiques peuvent être pleinement exploités.