← Назад к вопросам
Как устроена внутренняя организация LinkedList в памяти с точки зрения хранения элементов?
1.0 Junior🔥 71 комментариев
#Коллекции
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Как устроена внутренняя организация LinkedList в памяти с точки зрения хранения элементов?
LinkedList в Java — это реализация двусвязного списка. Это важно понимать для правильного выбора структуры данных в конкретной ситуации. Расскажу о внутреннем устройстве.
Основная структура LinkedList
LinkedList состоит из узлов (Node). Каждый узел хранит:
- Значение (элемент)
- Ссылку на следующий узел (next)
- Ссылку на предыдущий узел (prev) — двусвязный список
// Внутренний класс Node в LinkedList (упрощённо)
private static class Node<E> {
E item; // Данные
Node<E> next; // Ссылка на следующий узел
Node<E> prev; // Ссылка на предыдущий узел
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Визуализация структуры LinkedList
LinkedList: [1, 2, 3]
┌─────────────────────────────────────────────────────┐
│ first──────┐ │
└─────────────┼────────────────────────────────────────┘
│
▼
┌──────────┐ ┌──────────┐ ┌──────────┐
│ Node 1 │◄───────▶│ Node 2 │◄───────▶│ Node 3 │
│ item=1 │ │ item=2 │ │ item=3 │
│ prev=null│ │ prev⬌next│ │next=null │
└──────────┘ └──────────┘ └──────────┘
▲ ▼
┌─────────────┼────────────────────────────────────────┐
│ └──────────────── last─────────────────── │
└────────────────────────────────────────────────────────┘
Состояние LinkedList в памяти
public class LinkedListMemory {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.add(30);
// Внутреннее состояние после добавления элементов:
// first → Node(prev=null, item=10, next→Node2)
// Node(prev←Node1, item=20, next→Node3)
// Node(prev←Node2, item=30, next=null) ← last
}
}
Операции в LinkedList
1. Добавление элемента (add)
public class LinkedListOperations {
// Добавление в конец списка: O(1)
public void addToEnd(LinkedList<Integer> list, int value) {
list.add(value);
// Создаётся новый Node, last.next указывает на него
}
// Добавление в начало: O(1)
public void addToStart(LinkedList<Integer> list, int value) {
list.addFirst(value);
// Создаётся новый Node, first указывает на него
}
// Добавление в середину: O(n)
public void addInMiddle(LinkedList<Integer> list, int index, int value) {
list.add(index, value);
// Нужно пройти до index, потом перестроить ссылки
}
// Внутренняя реализация (упрощённо)
private Node<Integer> node(int index) {
if (index < size / 2) {
// Проходим с начала
Node<Integer> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
// Проходим с конца (оптимизация!)
Node<Integer> x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}
}
2. Удаление элемента (remove)
// Удаление первого элемента: O(1)
list.removeFirst();
// first = first.next
// first.prev = null
// Удаление последнего элемента: O(1)
list.removeLast();
// last = last.prev
// last.next = null
// Удаление из середины по индексу: O(n)
list.remove(1); // Нужно найти элемент, потом перестроить ссылки
// Внутренняя реализация удаления
private E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next; // Удаляем первый элемент
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev; // Удаляем последний элемент
} else {
next.prev = prev;
x.next = null;
}
x.item = null; // Помощь сборщику мусора
size--;
return element;
}
3. Получение элемента (get)
// Получение элемента по индексу: O(n)
Integer value = list.get(1);
// Нужно пройти от first к элементу с индексом 1
// Но LinkedList оптимизирует этот процесс:
// Если индекс < size/2 → идём от first
// Если индекс >= size/2 → идём от last
Сравнение с ArrayList
ArrayList: [1, 2, 3]
В памяти — непрерывный массив:
┌──────┬──────┬──────┐
│ 1 │ 2 │ 3 │ (Адреса памяти идут подряд)
└──────┴──────┴──────┘
LinkedList: [1, 2, 3]
В памяти — разрозненные узлы:
┌──────┐ ┌──────┐ ┌──────┐
│ 1 │─────▶ │ 2 │─────▶ │ 3 │ (Адреса в разных местах!)
└──────┘ └──────┘ └──────┘
Сложность операций
// Таблица сложности
/*
Операция | ArrayList | LinkedList
─────────────────────────────────────────
add(E) | O(1) | O(1)
add(int, E) | O(n) | O(n)
get(int) | O(1) | O(n)
remove(int) | O(n) | O(n)
remove(Object) | O(n) | O(n)
contains(Object) | O(n) | O(n)
iterator() | O(1) | O(1)
ListIterator() | O(1) | O(n)
*/
public class ComplexityExample {
public static void demonstrateComplexity() {
LinkedList<Integer> linkedList = new LinkedList<>();
ArrayList<Integer> arrayList = new ArrayList<>();
// Добавление в конец: оба O(1)
linkedList.add(1); // Быстро
arrayList.add(1); // Быстро
// Доступ к элементу: совсем разные!
linkedList.get(1000); // O(n) — может быть медленно!
arrayList.get(1000); // O(1) — очень быстро
// Удаление из середины
linkedList.remove(500); // O(n)
arrayList.remove(500); // O(n)
}
}
Итератор LinkedList
public class LinkedListIterator {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
// Итератор работает эффективно: O(1) переход к следующему
for (String item : list) {
System.out.println(item); // Каждый next() — O(1)
}
// ListIterator — двусторонний итератор
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
String item = iterator.next(); // O(1)
System.out.println(item);
}
while (iterator.hasPrevious()) {
String item = iterator.previous(); // O(1) — благодаря двусвязности!
}
}
}
Утечка памяти в LinkedList
// Опасно: оставляем ссылки на Node'ы
public class MemoryLeakExample {
private Node<Integer> first; // Держим ссылку
public void addToLinkedList(LinkedList<Integer> list) {
list.add(100);
// Если somehow сохранить ссылку на Node через reflection,
// это может привести к утечке памяти
}
}
// Правильно: не держим ссылки на Node'ы
public void processLinkedList(LinkedList<Integer> list) {
for (Integer item : list) {
System.out.println(item);
}
// Когда list выходит из scope, все Node'ы удаляются сборщиком мусора
}
Когда использовать LinkedList
// ✅ Хорошо для LinkedList:
// 1. Частые добавления/удаления в начало или конец
Queue<Task> taskQueue = new LinkedList<>();
taskQueue.add(task); // O(1)
Task next = taskQueue.poll(); // O(1)
// 2. Реализация очередей (Queue, Deque)
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(10); // O(1)
deque.addLast(20); // O(1)
// 3. Когда нужна двусторонняя итерация
LinkedList<String> list = new LinkedList<>();
ListIterator<String> iterator = list.listIterator();
while (iterator.hasPrevious()) {
System.out.println(iterator.previous());
}
// ❌ Плохо для LinkedList:
// 1. Частый доступ по индексу
for (int i = 0; i < list.size(); i++) {
Integer value = list.get(i); // O(n) — очень медленно!
}
// 2. Поиск элементов
if (list.contains(100)) { // O(n)
// ...
}
// 3. Большой список с пассивным доступом
// Используй ArrayList вместо этого
Best Practices
- Используй LinkedList для Queue/Deque — идеально для этого
- Используй ArrayList для большинства случаев — быстрее в сухом остатке
- Не используй LinkedList если часто обращаешься по индексу — O(n) может быть узким местом
- Итератор LinkedList эффективен — используй iterator() вместо get(i)
- Оба списка НЕ потокобезопасны — используй Collections.synchronizedList() или CopyOnWriteArrayList
- Помни о GC pause'ах — LinkedList создаёт много Node объектов
В production коде я обычно использую ArrayList по умолчанию, и только для операций Queue/Deque или когда профилирование показывает узкое место, переходу на LinkedList.