«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

Во-вторых, давайте удалим первый элемент из 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. Сложность времени

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

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

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

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

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

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

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