リストから最初の要素を削除する

投稿日: 2019-10-18 2022-10-26
タグ: Java

1. 概要

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

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

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. 時間計算量

方法は似ていますが、効率は異なります。 ArrayListのremove（）メソッドにはO（n）時間が必要ですが、 LinkedListのremoveFirst（）メソッドにはO（1）が必要です。）時間。

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

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

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

6. 結論

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

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

getdocs

13036