Entfernen Sie das erste Element aus einer Liste

1. Übersicht

In diesem superschnellen Tutorial zeigen wir, wie Sie das erste Element aus einer Liste entfernen .

Wir werden diese Operation für zwei gängige Implementierungen der List- Schnittstelle ausführen - ArrayList und LinkedList .

2. Erstellen einer Liste

Lassen Sie uns zunächst unsere Liste s füllen:

@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

Zweitens entfernen wir das erste Element aus der ArrayList und stellen sicher, dass unsere Liste es nicht mehr enthält:

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

Wie oben gezeigt, verwenden wir die Methode remove (index) , um das erste Element zu entfernen. Dies funktioniert auch für jede Implementierung der List- Schnittstelle.

4. LinkedList

LinkedList implementiert auch die Methode remove (index) (auf seine eigene Weise), verfügt jedoch auch über die Methode removeFirst () .

Stellen wir sicher, dass es wie erwartet funktioniert:

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

5. Zeitkomplexität

Obwohl die Methoden ähnlich aussehen, unterscheidet sich ihre Effizienz. Die remove () -Methode von ArrayList benötigt O (n) -Zeit , während die removeFirst () -Methode von LinkedList O (1) -Zeit benötigt.

Dies liegt daran, dass ArrayList ein Array unter der Haube verwendet und für den Vorgang remove () der Rest des Arrays an den Anfang kopiert werden muss. Je größer das Array ist, desto mehr Elemente müssen verschoben werden.

Im Gegensatz dazu verwendet LinkedList Zeiger, was bedeutet, dass jedes Element auf das nächste und das vorherige zeigt.

Das Entfernen des ersten Elements bedeutet daher, nur den Zeiger auf das erste Element zu ändern. Dieser Vorgang erfordert immer dieselbe Zeit, unabhängig von der Größe einer Liste.

6. Fazit

In diesem Artikel haben wir uns mit dem Entfernen des ersten Elements aus einer Liste befasst und die Effizienz dieser Operation für ArrayList- und LinkedList- Implementierungen verglichen .

Wie üblich ist der vollständige Quellcode auf GitHub verfügbar.