Как элементы LinkedList содержатся в Heap

Как элементы LinkedList хранятся в Java Heap

LinkedList в Java — это реализация двусвязного списка. Элементы не хранятся в виде смежного массива, а представлены отдельными узлами (Node objects), распределёнными по памяти Heap.

Структура Node в LinkedList

Внутренне LinkedList использует приватный класс Node:

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<String> list = new LinkedList<>();
list.add("Apple");    // Node 1
list.add("Banana");   // Node 2
list.add("Cherry");   // Node 3

В Heap памяти это выглядит так:

Heap:
┌─────────────────────┐
│   LinkedList obj    │
│  first ──────────────┐
│  last  ──────────────┘──────────────┐
│  size = 3           │              │
└─────────────────────┘              │
                                      │
    ┌───────────────────────────────┐ │
    │         Node 1                │ │
    │  item = "Apple"    ┌──────────┼─┘
    │  prev = null       │          │
    │  next ─────────────┼──┐       │
    └───────────────────┼──┘       │
                        │          │
    ┌───────────────────▼────────┐ │
    │         Node 2             │ │
    │  item = "Banana"  ┌────────┼─┘
    │  prev ────────────┼────────┘
    │  next ────────────┼───┐
    └───────────────────┼───┘
                        │
    ┌───────────────────▼────────┐
    │         Node 3             │
    │  item = "Cherry"  ┌────────┘
    │  prev ────────────┘
    │  next = null
    └────────────────────────────┘

Пример с кодом

public class LinkedListMemoryExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(10);    // Создаёт Node(null, 10, null)
        list.add(20);    // Создаёт Node(prevNode, 20, null)
        list.add(30);    // Создаёт Node(prevNode, 30, null)
        
        // Каждый вызов add() создаёт новый объект Node в Heap
        // Узлы не обязательно идут подряд в памяти
        
        // Доступ к элементам требует обхода цепочки ссылок
        for (Integer num : list) {
            System.out.println(num);
        }
    }
}

Отличие от ArrayList

// ArrayList: все элементы в одном массиве подряд
// array[0] = 10, array[1] = 20, array[2] = 30 (смежная память)

// LinkedList: элементы разбросаны по Heap, связаны ссылками
// Node1.item = 10 → Node2.item = 20 → Node3.item = 30

Характеристики хранения

Преимущества:

• Быстрое добавление/удаление в начало/конец O(1)
• Нет необходимости в переаллокации как у ArrayList
• Эффективно для больших элементов

Недостатки:

• Больше памяти за счёт двух ссылок (prev, next) на каждый узел
• Медленный доступ по индексу O(n) — нужно обходить цепочку
• Плохая локальность кэша — узлы разбросаны по памяти

Сложность операций

LinkedList<String> list = new LinkedList<>();

list.add("X");              // O(1) — добавление в конец
list.addFirst("Y");         // O(1) — добавление в начало
list.get(0);                // O(n) — доступ по индексу
list.remove(0);             // O(n) — удаление по индексу
list.removeFirst();         // O(1) — удаление из начала

Итерация

// Эффективно: используется имеющиеся ссылки
for (String element : list) {
    System.out.println(element);  // O(n)
}

// Неэффективно: каждый раз обходит список с начала
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));  // O(n²)
}

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

• LinkedList: частые вставки/удаления в начало/конец, неизвестный размер
• ArrayList: быстрый доступ по индексу, предсказуемый размер

LinkedList хранит элементы как отдельные Node объекты в Heap, связанные ссылками prev/next, что обеспечивает гибкость, но требует больше памяти и медленнее для произвольного доступа.