概述
在这个实例中,我们将会演示如何删除在 Java 中定义的 List 的第 1 个元素。
我们将会针对这个问题使用 List 接口的 2 个实现 ArrayList 和 LinkedList 来进行演示。
创建一个 List
首先,我们来创建一个我们需要的 List:
@BeforeAll
public void startup() {
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");
}
ArrayList
根据我们创建的 List,我们来演示在 ArrayList
中删除第一个元素,然后确定删除后的 List 不再包含有任何一句删除的元素了。
使用下面的测试方法来进行测试。
/**
* ArrayList remove first
*/
@Test
public void testGivenList_whenRemoveFirst_thenRemoved() {
list.remove(0);
assertThat(list, hasSize(4));
assertThat(list, not(contains("cat")));
}
通过上面的代码我们可以了解到,我们使用了 remove(index)
这个方法来删除我们需要处理的 List 中的第一个元素。
需要注意的是:remove 这个方法,针对 List 接口的所有实现都是可以使用的。
LinkedList
LinkedList 同时也实现了 remove(index) 这个方法,同时 LinkedList 还有一个自己的 removeFirst() 方法。
让我们考察下面的测试方法,来确定删除是否正确。
/**
* LinkedList remove first
*/
@Test
public void testGivenLinkedList_whenRemoveFirst_thenRemoved() {
linkedList.removeFirst();
assertThat(linkedList, hasSize(4));
assertThat(linkedList, not(contains("cat")));
}
时间复杂度
尽管上面的 remove 方法类似,但是这 2 个方法的时间复杂度是不同的:
ArrayList 的 remove()
方法的时间复杂度是 O(n) 。
LinkedList 的 removeFirst() 方法的时间复杂度是 O(1) 。
这是因为 ArrayList 在 List 中是使用 Array(数组)的,当我们使用删除方法的时候,ArrayList 将会重新将剩余的元素进行拷贝。如果你需要删除 List 越大,那么需要移动的元素越多。因此所需要的时间复杂度越高。
LinkedList 却是使用的是指针(points),这个指针的意思就是每一个元素使用指针来指向下一个元素,同时还使用一个指针来指向前一个元素。
因此,在 LinkedList 删除第一个元素的时候,需要进行的操作就只需要修改第一个元素的指针就可以了。
不管你的 List 有多大,这个修改指针的操作需要的时间是相同的。
结论
在本文中,我们对如何对 List 中的第一个元素进行删除进行了说明和讨论。
并且针对 List 接口的 2 个实现来分别了解了不同的时间复杂度。
上面的内容的源代码可以在 java-tutorials/RemoveFirstElementTest.java at master · cwiki-us-docs/java-tutorials · GitHub 中进行下载和编译。
需要注意的是 assertThat 断言使用的是 Hamcrest 。