從列表中刪除第一個元素
1.概述
在這個超級快速的教程中,我們將展示如何從List
刪除第一個元素。
我們將對List
接口的兩個常見實現執行此操作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
其次,讓我們從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
在ArrayList
使用數組,而remove()
操作需要將數組的其餘部分複製到開頭。數組越大,需要移動的元素越多。
與此不同, LinkedList
使用指針,這意味著每個元素都指向下一個和上一個。
因此,刪除第一個元素意味著只更改指向第一個元素的指針。此操作總是需要相同的時間,而不取決於列表的大小。
六,結論
在本文中,我們介紹瞭如何從List,
刪除第一個元素List,
並比較了ArrayList
和LinkedList
實現的此操作的效率。
像往常一樣,完整的源代碼可以在GitHub上找到。
0 條評論,你可以發表評論,我們會進行改進
