從列表中刪除第一個元素

1.概述

在這個超級快速的教程中,我們將展示如何從List刪除第一個元素。

我們將對List接口的兩個常見實現執行此操作ArrayListLinkedList

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

其次,讓我們從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)時間。

這是因為ArrayListArrayList使用數組,而remove()操作需要將數組的其餘部分複製到開頭。數組越大,需要移動的元素越多。

與此不同, LinkedList使用指針,這意味著每個元素都指向下一個和上一個。

因此,刪除第一個元素意味著只更改指向第一個元素的指針。此操作總是需要相同的時間,而不取決於列表的大小。

六,結論

在本文中,我們介紹瞭如何從List,刪除第一個元素List,並比較了ArrayListLinkedList實現的此操作的效率。

像往常一樣,完整的源代碼可以在GitHub上找到

0 條評論,你可以發表評論,我們會進行改進
Comment author placeholder