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