1概要

この超クイックチュートリアルでは、

List

から最初の要素を削除する方法を説明します。


List

インターフェイスの2つの一般的な実装(

ArrayList



LinkedList

)に対してこの操作を実行します。


2

List


を作成する

まず、

__List

__を作成しましょう。

@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から最初の要素を削除し、

リストに含まれなくなったことを確認します。

@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

`s

remove()

メソッドにはO(n)時間が必要ですが、

LinkedList

`s

removeFirst()

メソッドにはO(1)時間が必要です。

これは、

ArrayList

が内部で配列を使用しており、

remove()

操作では残りの配列を先頭にコピーする必要があるためです。配列が大きければ大きいほど、より多くの要素をシフトする必要があります。

それとは異なり、

LinkedList

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

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


6. 結論

この記事では、

List、

から最初の要素を削除する方法を説明し、

ArrayList

と____LinkedListの実装の効率性を比較しました。

いつものように、完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/core-java-collections[over on GitHub]から入手できます。