Удалить первый элемент из списка

1. Обзор

В этом сверхбыстром руководстве мы покажем, как удалить первый элемент из списка .

Мы выполним эту операцию для двух распространенных реализаций интерфейса List — 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 и убедимся, что наш список больше не содержит его:

@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. Временная сложность

Хотя методы выглядят одинаково, их эффективность различается. Метод remove() в ArrayList требует O(n) времени, тогда как метод removeFirst () в LinkedList требует O(1) времени. ``

Это связано с тем, что ArrayList использует массив под капотом, а операция remove() требует копирования остальной части массива в начало. Чем больше массив, тем больше элементов нужно сдвинуть.

В отличие от этого, LinkedList использует указатели, означающие, что каждый элемент указывает на следующий и предыдущий.

Следовательно, удаление первого элемента означает просто изменение указателя на первый элемент. Эта операция всегда требует одинакового времени, независимо от размера списка.

6. Заключение

В этой статье мы рассмотрели, как удалить первый элемент из списка, и сравнили эффективность этой операции для реализаций ArrayList и LinkedList .

Как обычно, полный исходный код доступен на GitHub .