Ответ
LinkedList — это реализация интерфейсов List и Deque в Java, основанная на структуре данных двусвязного списка. Каждый элемент (узел) хранит данные и две ссылки: на предыдущий и следующий узел.
Ключевые характеристики и сложность операций:
| Операция | Сложность | Причина |
|---|---|---|
| Вставка/удаление в начале/конце | O(1) | Доступ к голове/хвосту списка по ссылке. |
| Вставка/удаление по индексу (в середине) | O(n) | Требуется линейный поиск нужной позиции. |
| Получение элемента по индексу (get) | O(n) | Требуется последовательный обход с начала или конца. |
| Поиск элемента по значению | O(n) | Необходим последовательный обход. |
Когда использовать LinkedList?
- Когда частые операции — это добавление/удаление элементов в начале или конце списка.
- Когда не требуется частый произвольный доступ по индексу.
- Когда нужна реализация очереди (
Queue) или двусторонней очереди (Deque).
Пример использования:
LinkedList<String> cities = new LinkedList<>();
// Эффективные операции с концами списка
cities.addFirst("Berlin"); // O(1)
cities.addLast("Tokyo"); // O(1)
cities.add("Paris"); // O(1) - добавляет в конец
String first = cities.pollFirst(); // O(1) - удаляет и возвращает первый
// Медленный доступ по индексу
String city = cities.get(1); // O(n) - обход от начала спискаПамять: Каждый элемент потребляет больше памяти, чем ArrayList, из-за хранения двух дополнительных ссылок.