1. 概要

この超高速チュートリアルでは、リストから最初の要素を削除する方法を示します。

この操作は、Listインターフェイスの2つの一般的な実装であるArrayListLinkedListに対して実行します。

2. リストの作成

まず、リストにデータを入力しましょう。

@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

次に、 ArrayList、から最初の要素を削除し、リストにそれが含まれていないことを確認します。

@Test
public void givenList_whenRemoveFirst_thenRemoved() {
    list.remove(0);

    assertThat(list, hasSize(4));
    assertThat(list, not(contains("cat")));
}

上に示したように、 remove(index)メソッドを使用して最初の要素を削除しています– これは、Listインターフェイスのすべての実装でも機能します。

4. LinkedList

LinkedList は、 remove(index)メソッドも(独自の方法で)実装しますが、 removeFirst()メソッドもあります。

期待どおりに機能することを確認しましょう。

@Test
public void givenLinkedList_whenRemoveFirst_thenRemoved() {
    linkedList.removeFirst();

    assertThat(linkedList, hasSize(4));
    assertThat(linkedList, not(contains("cat")));
}

5. 時間計算量

方法は似ていますが、効率は異なります。  ArrayListremove()メソッドにはO(n)時間が必要ですが、 LinkedListremoveFirst()メソッドにはO(1)が必要です。 ) 時間。

これは、 ArrayList が内部で配列を使用し、 remove()操作で残りの配列を先頭にコピーする必要があるためです。 配列が大きいほど、より多くの要素をシフトする必要があります。

それとは異なり、 LinkedList はポインターを使用します。これは、各要素が次の要素と前の要素を指すことを意味します。

したがって、最初の要素を削除するということは、ポインタを最初の要素に変更することを意味します。 この操作は、リストのサイズに関係なく、常に同じ時間を必要とします。

6. 結論

この記事では、リストから最初の要素を削除する方法について説明し、ArrayListLinkedListの実装でこの操作の効率を比較しました。

いつものように、完全なソースコードはGitHubから入手できます。