Как хранятся объекты в LinkedList

Как хранятся объекты в LinkedList

LinkedList — одна из важнейших структур данных в Java. Рассскажу о её внутреннем устройстве, преимуществах и недостатках по сравнению с ArrayList.

Структура LinkedList: Узлы и ссылки

Базовая структура Node

// Внутренняя структура LinkedList (упрощённо)
private static class Node<E> {
    E item;           // Данные
    Node<E> next;     // Ссылка на следующий узел
    Node<E> prev;     // Ссылка на предыдущий узел (двусвязный список)
}

Визуализация:

LinkedList: 10 -> 20 -> 30 -> null

┌──────────────┐     ┌──────────────┐     ┌──────────────┐
│ Node<Integer>│     │ Node<Integer>│     │ Node<Integer>│
├──────────────┤     ├──────────────┤     ├──────────────┤
│ item: 10     │     │ item: 20     │     │ item: 30     │
│ prev: null   │     │ prev: ●──────┼────→│ prev: ●      │
│ next: ●──────┼────→│ next: ●──────┼────→│ next: null   │
└──────────────┘     └──────────────┘     └──────────────┘
  (first)                                    (last)

Память LinkedList

Где хранятся узлы?

LinkedList<String> list = new LinkedList<>();
list.add("A");  // Создаётся новый Node на heap
list.add("B");  // Создаётся новый Node на heap
list.add("C");  // Создаётся новый Node на heap

На Heap (куче):

• Сами Node объекты (с item, next, prev ссылками)
• String объекты ("A", "B", "C")

На Stack:

• Ссылка на first Node (голова списка)
• Ссылка на last Node (хвост списка)
• Локальная переменная list

Размер в памяти

ArrayList<Integer> с 1000 элементов:
Окупаемая память ≈ 4000 байт (1000 * 4 byte на int)

LinkedList<Integer> с 1000 элементов:
Окупаемая память ≈ 40000 байт (1000 * (4 int + 8 prev + 8 next))
= 20x БОЛЬШЕ памяти! (каждый Node требует extra overhead)

Пример: Как объекты добавляются

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        
        list.add(10);  // 1️⃣  Создаётся первый Node
        list.add(20);  // 2️⃣  Создаётся второй Node
        list.add(30);  // 3️⃣  Создаётся третий Node
    }
}

Пошагово в памяти:

1️⃣ После list.add(10):
first → [Node: 10, prev=null, next=null]
last  → [Node: 10, prev=null, next=null]

2️⃣ После list.add(20):
first → [Node: 10, prev=null, next=●] ──→ [Node: 20, prev=●, next=null] ← last

3️⃣ После list.add(30):
first → [Node: 10] ──→ [Node: 20] ──→ [Node: 30] ← last

Доступ к элементам

get(index) — ДОРОГО!

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.add(30);

int element = list.get(2);  // Ищет от начала или конца

Что происходит внутри:

public E get(int index) {
    return getNode(index).item;  // Проходит от начала до индекса
}

private Node<E> getNode(int index) {
    Node<E> x;
    if (index < (size >> 1)) {
        x = first;                    // Если index < size/2
        for (int i = 0; i < index; i++) {
            x = x.next;               // Проход вперёд
        }
    } else {
        x = last;                     // Если index >= size/2
        for (int i = size; i > index; i--) {
            x = x.prev;               // Проход назад
        }
    }
    return x;
}

Сложность: O(n) — линейный поиск!

Для сравнения ArrayList:

ArrayList<Integer> array = new ArrayList<>();
array.add(10);
array.add(20);
array.add(30);

int element = array.get(2);  // Мгновенно по индексу

Сложность: O(1) — прямой доступ

Добавление элементов

add(E e) — Добавление в конец

linkedList.add(40);  // O(1) — добавляет в хвост (last node)

add(int index, E element) — Добавление в позицию

linkedList.add(1, 25);  // O(n) — сначала ищет позицию!

Процесс:

До:  10 ──→ 20 ──→ 30
После add(1, 25):
10 ──→ 25 ──→ 20 ──→ 30

Удаление элементов

remove(int index) — Удаление по индексу

linkedList.remove(1);  // O(n) — ищет элемент, затем удаляет

Процесс:

До:  10 ──→ 20 ──→ 30
После remove(1):
10 ──→ 30

Как работает удаление:

// Разрываются ссылки
Node<E> node = getNode(index);  // Ищет Node по индексу
Node<E> prev = node.prev;
// Перенаправляем ссылки
prev.next = node.next;
if (node.next != null) {
    node.next.prev = prev;
}

Итерация по LinkedList

✅ БЫСТРО: использование Iterator

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.add(30);

// Правильный способ: O(n)
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

// Или for-each (также использует Iterator)
for (Integer item : list) {
    System.out.println(item);
}

❌ МЕДЛЕННО: используя get()

// Неправильный способ: O(n²)
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));  // Каждый get() = O(n)
}
// Итого: 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²)

Сравнение: LinkedList vs ArrayList

Когда использовать LinkedList

✓ Используй LinkedList:

• Много операций add/remove в начало или конец
• Навигация через Iterator
• Реализация очередей (Queue, Deque)
• Стеков (Stack)

✗ Избегай LinkedList:

• Частый доступ по индексу (get())
• Много памяти (overhead на Node)
• Нужна локальность в памяти (cache efficiency)

Практический пример

public class LinkedListVsArrayList {
    public static void main(String[] args) {
        // ✅ LinkedList хорош для операций с очередью
        LinkedList<String> queue = new LinkedList<>();
        queue.add("task1");
        queue.add("task2");
        String first = queue.remove();  // O(1)
        
        // ✅ ArrayList хорош для доступа по индексу
        ArrayList<String> data = new ArrayList<>();
        data.add("item1");
        data.add("item2");
        String item = data.get(1);  // O(1)
        
        // ❌ LinkedList плохо для индексирования
        LinkedList<Integer> bad = new LinkedList<>();
        for (int i = 0; i < 1000; i++) {
            bad.add(i);
        }
        for (int i = 0; i < bad.size(); i++) {
            int val = bad.get(i);  // O(n) * n раз = O(n²)
        }
    }
}

Выводы

LinkedList хранит объекты:

1. ✓ Через Node объекты (item + ссылки prev/next)
2. ✓ На heap (куче), каждый Node отдельно
3. ✓ С быстрым добавлением/удалением в начало/конец
4. ✓ С медленным доступом по индексу (O(n))
5. ✓ Требует больше памяти из-за overhead на ссылки