Supprimer le premier élément d'une liste

1. Vue d'ensemble

Dans ce didacticiel ultra-rapide, nous montrerons comment supprimer le premier élément d'une liste .

Nous allons effectuer cette opération pour deux implémentations courantes de l' interface List - ArrayList et LinkedList .

2. Créer une liste

Tout d'abord, remplissons nos listes :

@Before public void init() { list.add("cat"); list.add("dog"); list.add("pig"); list.add("cow"); list.add("goat"); linkedList.add("cat"); linkedList.add("dog"); linkedList.add("pig"); linkedList.add("cow"); linkedList.add("goat"); }

3. ArrayList

Deuxièmement, supprimons le premier élément de ArrayList, et assurez-vous que notre liste ne le contient plus:

@Test public void givenList_whenRemoveFirst_thenRemoved() { list.remove(0); assertThat(list, hasSize(4)); assertThat(list, not(contains("cat"))); }

Comme indiqué ci-dessus, nous utilisons la méthode remove (index) pour supprimer le premier élément - cela fonctionnera également pour toute implémentation de l' interface List .

4. LinkedList

LinkedList implémente également la méthode remove (index) (à sa manière) mais il a aussi la méthode removeFirst () .

Assurons-nous que cela fonctionne comme prévu:

@Test public void givenLinkedList_whenRemoveFirst_thenRemoved() { linkedList.removeFirst(); assertThat(linkedList, hasSize(4)); assertThat(linkedList, not(contains("cat"))); }

5. Complexité temporelle

Bien que les méthodes se ressemblent, leur efficacité diffère. ArrayList 's remove () méthode nécessite O (n), alors que LinkedList ' s removeFirst () méthode nécessite O (1) heure.

Cela est dû au fait qu'ArrayList utilise un tableau sous le capot et que l' opération remove () nécessite de copier le reste du tableau au début. Plus le tableau est grand, plus les éléments doivent être décalés.

Contrairement à cela, LinkedList utilise des pointeurs, ce qui signifie que chaque élément pointe vers le suivant et le précédent.

Par conséquent, supprimer le premier élément signifie simplement changer le pointeur vers le premier élément. Cette opération nécessite toujours le même temps sans dépendre de la taille d'une liste.

6. Conclusion

Dans cet article, nous avons expliqué comment supprimer le premier élément d'une liste et avons comparé l'efficacité de cette opération pour les implémentations ArrayList et LinkedList .

Comme d'habitude, le code source complet est disponible à l'adresse over sur GitHub.