1. Обзор
В этом супер-быстром уроке мы покажем, как удалить первый элемент из списка /.
Мы выполним эту операцию для двух распространенных реализаций интерфейса List – ArrayList и LinkedList .
2. Создание списка
Во-первых, давайте заполним наш Список s:
@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 также реализует метод 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() требует копирования остальной части массива в начало. Чем больше массив, тем больше элементов необходимо сдвинуть.
В отличие от этого, Linked List использует указатели, означающие, что каждый элемент указывает на следующий и предыдущий.
Следовательно, удаление первого элемента означает просто изменение указателя на первый элемент. Эта операция всегда требует одного и того же времени, не зависящего от размера списка.
6. Заключение
В этой статье мы рассмотрели, как удалить первый элемент из списка , и сравнили эффективность этой операции для реализаций ArrayList и LinkedList .
Как обычно, полный исходный код доступен на GitHub .