Подробное объяснение метода addFirst() в Java LinkedList

Java LinkedList Java LinkedList

addFirst()ДаLinkedListВажный метод в классе, используемый для вставки указанного элемента в начало связанного списка.

Синтаксис метода

public void addFirst(E e)

Описание параметра

E e: Элемент, добавляемый в начало связанного списка

Возвращаемое значение

Этот метод не возвращает значение (void).

Как работает метод addFirst()

addFirst()Принцип работы метода можно кратко описать так:

  1. Создайте новый объект узла (Node)
  2. Направьте указатель нового узлаnextна текущий головной узел
  3. Направьте указатель текущего головного узлаprevна новый узел
  4. Обновите у связного спискаheadна новый узел
  5. Если связный список был ранее пуст, также направьте указатель хвостового узла на новый узел
  6. Увеличьте счётчик размера связного списка (size++)

Временная сложность

Временная сложность метода addFirst() — O(1), потому что независимо от размера связного списка ему нужно выполнить фиксированное число операций.

Примеры использования

Давайте рассмотрим конкретное использование метода на нескольких примерах.addFirst()Пример 1: Базовое использование

Пример 1: Базовое использование

Пример

import java.util.LinkedList;

public class AddFirstExample {
    public static void main(String[] args) {
        // Добавить начальные элементы
        LinkedList<String> fruits = new LinkedList<>();
       
        "Исходный связный список: "
        fruits.add("Banana");
        fruits.add("Orange");
       
        System.out.println(// Вывод: [Banana, Orange] + fruits);  // Используйте addFirst(), чтобы добавить элемент в начало
       
        "Связный список после добавления: "
        fruits.addFirst("Apple");
       
        System.out.println(// Вывод: [Apple, Banana, Orange] + fruits);  Пример 2: Последовательные добавления
    }
}

Пример 2: Последовательные добавления

Пример

import java.util.LinkedList;

public class ContinuousAddFirst {
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();
       
        // Вывод: [1, 2, 3]
        numbers.addFirst(3);
        numbers.addFirst(2);
        numbers.addFirst(1);
       
        System.out.println(numbers);  // Обратите внимание на связь между порядком добавления и итоговым результатом
       
        Пример 3: Отличие от метода add()
    }
}

Пример 3: Отличие от метода add()

Пример

import java.util.LinkedList;

public class AddVsAddFirst {
    public static void main(String[] args) {
        LinkedList<String> list1 = new LinkedList<>();
        LinkedList<String> list2 = new LinkedList<>();
       
        // Используйте метод addFirst() для добавления тех же элементов
        list1.add("A");
        list1.add("B");
        list1.add("C");
       
        "Использование add(): "
        list2.addFirst("C");
        list2.addFirst("B");
        list2.addFirst("A");
       
        System.out.println(// Вывод: [A, B, C] + list1);    "Использование addFirst(): "
        System.out.println(// Вывод: [A, B, C] + list2); // Хотя итоговый результат тот же, порядок добавления обратный
       
        Примечания
    }
}

Примечания

1. Отличие от метода add()addFirst()Метод по умолчанию добавляет элементы в конец связного списка

1. Отличие от метода add()

  • add()2. Отличие от метода offerFirst()
  • addFirst()Может выбросить исключение в очереди с ограниченной ёмкостью

2. Отличие от метода offerFirst()

  • addFirst()вместо выброса исключения
  • offerFirst()3. Обработка значений nullfalseПозволяет добавлять

3. Обработка значений null

LinkedListдопустимо.null4. ПотокобезопасностьaddFirst(null)не является потокобезопасным; при использовании в многопоточной среде

4. Потокобезопасность

LinkedListПрактические сценарии примененияaddFirst()Метод особенно полезен в следующих сценариях:

Практические сценарии применения

addFirst()Поскольку стек — это структура «Last In, First Out» (LIFO), методы addFirst() и removeFirst() можно использовать для имитации операций стека.

1. Реализация структуры стека

// Поместить в стек

Пример

LinkedList<String> stack = new LinkedList<>();
stack.addFirst("Task1");  // Извлечь из стека, возвращает "Task2"
stack.addFirst("Task2");  2. Список недавно использованных
String top = stack.removeFirst();  При реализации списка наиболее недавно использованных (MRU) элементы, к которым недавно был доступ, можно добавлять в начало списка.

2. Список недавно использованных

Добавляя элементы один за другим в новый список с помощью addFirst(), можно добиться обращения списка.

3. Операция обращения

// Вывод: [3, 2, 1]

Пример

LinkedList<Integer> original = new LinkedList<>(Arrays.asList(1, 2, 3));
LinkedList<Integer> reversed = new LinkedList<>();

for (Integer num : original) {
    reversed.addFirst(num);
}

System.out.println(reversed);  Метод обладает очень хорошей производительностью в

Соображения производительности

addFirst()Создание нового узлаLinkedListКорректировка нескольких указателей

  1. Независимо от того, насколько большим является связный список, время выполнения этих операций постоянно (временная сложность O(1)). Это резко контрастирует с
  2. операцией, которая требует перемещения всех существующих элементов (временная сложность O(n)).

Поэтому, если вам нужно часто добавлять элементы в начало коллекции,ArrayListизadd(0, element)является лучшим выбором, чем

.LinkedListЧасто задаваемые вопросыArrayListВопрос 1: Перезапишет ли addFirst() существующие элементы?

Часто задаваемые вопросы

Вопрос 1: Перезапишет ли addFirst() существующие элементы?

Вопрос 2: Если связный список пуст, будет ли addFirst() всё ещё работать?addFirst()Да, если связный список пуст,

Вопрос 2: Если связный список пуст, будет ли addFirst() всё ещё работать?

Вопрос 3: В чём разница между addFirst() и push()?addFirst()В

Вопрос 3: В чём разница между addFirst() и push()?

ВLinkedListявляются абсолютно одним и тем же методом.addFirst()иpush()— это простоpush()другое название дляaddFirst(), используется, чтобы позволитьLinkedListиспользоваться в качестве стека.

Вопрос 4: Почему моя IDE подсказывает, что addFirst() — это метод Deque?

Потому чтоLinkedListреализуетDequeинтерфейс,addFirst()на самом деле являетсяDequeметодом, определённым вLinkedListинтерфейсе, и

Итог

LinkedListизaddFirst()ИтогLinkedListЭтот метод — эффективная операция, позволяющая вставлять элементы в начало связного списка. Понимание этого метода очень важно для эффективного использования

, особенно в сценариях, когда элементы нужно часто вставлять в начало коллекции.

  • addFirst()Обзор ключевых моментов:
  • Вставляет элементы в начало связного списка
  • иadd()Временная сложность — O(1)
  • Отличается позицией вставки от метода add()
  • Обычно используется для реализации стековых структур и списков недавно использованных элементов

Требует дополнительной синхронизации в многопоточных средахaddFirst()Используя этотLinkedListметод разумно, преимущества в производительности

Java LinkedList Java LinkedList

в конкретных сценариях могут быть полностью использованы.