Внутреннее устройство LinkedList
Изучите структуру двусвязных узлов LinkedList и характеристики его временной сложности.
«Внутреннее устройство LinkedList» — бесплатный урок Java Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Java Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Java Academy содержит 4 уроков всего.
Внутреннее устройство LinkedList
LinkedList в Java — это двусвязный список: каждый узел хранит ссылку на предыдущий и следующий узел, а также значение элемента. В отличие от ArrayList, резервного массива нет — память выделяется для каждого узла отдельно.
class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) { this.data = data; }
}Профиль временной сложности
Характеристики производительности LinkedList значительно отличаются от ArrayList:
- addFirst / addLast: O(1)
- get(index): O(n) — необходимо пройти от начала или конца списка
- remove(index): O(n) для поиска, затем O(1) для отсоединения
- Обход с помощью итератора: O(n)
Используйте LinkedList, когда вам часто требуется добавлять элементы в начало или конец, а не обращаться к ним по произвольному индексу.
Создание и обход LinkedList
Создание LinkedList и итерация выполняются через тот же интерфейс List, который вы уже знаете. Различие заключается во внутренней структуре.
import java.util.LinkedList;
LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");
for (String name : list) {
System.out.println(name);
}
System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: " + list.getLast()); // CaroladdFirst, addLast, removeFirst, removeLast
LinkedList предоставляет операции с началом и концом списка, которые ArrayList не поддерживает эффективно:
LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10); // [10]
nums.addLast(20); // [10, 20]
nums.addFirst(5); // [5, 10, 20]
System.out.println(nums.removeFirst()); // 5 → [10, 20]
System.out.println(nums.removeLast()); // 20 → [10]Отсоединение Node: удаление O(1) после поиска
Если у вас уже есть ссылка на узел (через итератор), удаление выполняется за O(1), поскольку нужно обновить только указатели next и prev — сдвигать элементы, как в ArrayList, не требуется.
import java.util.*;
LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
String t = it.next();
if (t.equals("B") || t.equals("D")) {
it.remove(); // O(1) unlink
}
}
System.out.println(tasks); // [A, C]Накладные расходы на память по сравнению с ArrayList
Каждый узел LinkedList содержит две дополнительные ссылки (prev, next) и ссылку на элемент — около 48 байт на запись в 64-разрядной JVM. ArrayList хранит только ссылку на элемент (8 байт) в непрерывном массиве.
Для больших наборов данных, ориентированных преимущественно на чтение, ArrayList обычно лучше использует кэш и требует меньше памяти.
Операции двусторонней очереди: стек и очередь
LinkedList реализует интерфейс Deque, поэтому его можно использовать и как стек, и как очередь.
import java.util.LinkedList;
import java.util.Deque;
// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first
// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // topОбзор PriorityQueue
PriorityQueue — это очередь на основе кучи, в которой наименьший элемент (в естественном порядке или согласно компаратору) всегда извлекается первым. Она NOT основана на связанном списке — вместо этого используется массив двоичной кучи.
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);
System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40PriorityQueue с пользовательским компаратором
Передайте Comparator, чтобы изменить порядок или сортировать по пользовательскому полю:
import java.util.*;
record Task(String name, int priority) {}
PriorityQueue<Task> tasks = new PriorityQueue<>(
Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));
while (!tasks.isEmpty()) {
System.out.println(tasks.poll().name());
}
// High, Med, LowВыбор между LinkedList и ArrayList
Общее правило:
- Используйте ArrayList для произвольного доступа, итерации и большинства сценариев.
- Используйте LinkedList, когда вам часто требуется добавлять и удалять элементы с обоих концов за O(1) и не нужен доступ по индексу.
- Используйте PriorityQueue, когда требуется обработка в упорядоченном виде (планирование задач, алгоритм Дейкстры).
Распространенные ошибки
Не вызывайте get(i) в цикле для LinkedList — общая сложность составит O(n²):
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);
// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
int val = list.get(i); // slow!
}
// GOOD: O(n) — use iterator
for (int val : list) {
// process val
}Быстрая проверка
Какая операция LinkedList выполняется за O(1) независимо от размера списка?
Итоги: LinkedList и двусторонняя очередь
Основные выводы:
- LinkedList — двусвязный список с операциями с началом и концом за O(1)
- Произвольный доступ (get/set по индексу) выполняется за O(n)
- Реализует Deque — можно использовать как стек или очередь
- PriorityQueue обеспечивает обработку элементов в порядке кучи
- В большинстве случаев выбирайте ArrayList; LinkedList особенно полезен при частых изменениях начала и конца списка
Часто задаваемые вопросы
Урок «Внутреннее устройство LinkedList» бесплатный?
Да — полный текст урока «Внутреннее устройство LinkedList» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Java Academy, подпишись на CoddyKit PRO. Курс Java Academy содержит 4 уроков всего.
Чему я научусь в уроке «Внутреннее устройство LinkedList»?
Изучите структуру двусвязных узлов LinkedList и характеристики его временной сложности. Ты практикуешь Java Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Java Academy?
Предыдущий опыт не требуется. Java Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Внутреннее устройство LinkedList»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Java Academy?
Да. Каждый урок Java Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Внутреннее устройство LinkedList
- Операции Deque: стек и очередь
- Компромиссы LinkedList и ArrayList
- PriorityQueue для упорядоченной обработки