リストから最初の要素を削除する
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]から入手できます。