Какая структура данных имплементируется в LinkedList?

LinkedList: структура данных и реализация

LinkedList имплементирует Doubly Linked List (двусвязный список) — структуру данных где каждый элемент содержит данные и две ссылки: на предыдущий и следующий элемент.

Визуализация структуры

Null <- [Node 1] <-> [Node 2] <-> [Node 3] -> Null
         ^data1       ^data2       ^data3
         |prev|       |prev|       |prev|
         |next|-----> |next|-----> |next|
              |----<  |----<  |----<

Каждый узел содержит:

• data — сохранённое значение
• prev — ссылка на предыдущий узел
• next — ссылка на следующий узел

Внутренняя структура в Java

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;
    }
}

public class LinkedList<E> implements List<E>, Deque<E> {
    transient int size = 0;          // Количество элементов
    transient Node<E> first;         // Ссылка на первый узел
    transient Node<E> last;          // Ссылка на последний узел
}

Основные операции и их сложность

1. Добавление элемента (O(1))

// Добавление в конец
public boolean add(E e) {
    linkLast(e);
    return true;
}

private void linkLast(E e) {
    final Node<E> l = last;          // O(1) — просто берём ссылку
    final Node<E> newNode = new Node<>(l, e, null);  // O(1) — создаём узел
    last = newNode;                   // O(1) — устанавливаем новый last
    if (l == null)                    // Первый элемент?
        first = newNode;
    else
        l.next = newNode;             // O(1) — обновляем ссылку
    size++;
}

// Добавление в начало
public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;          // O(1)
    final Node<E> newNode = new Node<>(null, e, f);  // O(1)
    first = newNode;                  // O(1)
    if (f == null)                    // Первый элемент?
        last = newNode;
    else
        f.prev = newNode;             // O(1)
    size++;
}

2. Удаление элемента (O(1) если известна позиция)

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));  // O(n) для поиска, O(1) для удаления
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;      // O(1) — берём следующий
    final Node<E> prev = x.prev;      // O(1) — берём предыдущий
    
    if (prev == null) {
        first = next;                 // O(1) — удаляем первый
    } else {
        prev.next = next;             // O(1) — перенаправляем ссылку
        x.prev = null;                // O(1) — помогаем GC
    }
    
    if (next == null) {
        last = prev;                  // O(1) — удаляем последний
    } else {
        next.prev = prev;             // O(1) — перенаправляем ссылку
        x.next = null;                // O(1) — помогаем GC
    }
    
    x.item = null;                    // O(1) — помогаем GC
    size--;
    return element;
}

3. Доступ по индексу (O(n))

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;          // O(n) — нужно пройти от начала или конца
}

// Оптимизация: ищет с ближайшего конца
Node<E> node(int index) {
    if (index < (size >> 1)) {        // index < size/2?
        Node<E> x = first;             // Ищем с начала
        for (int i = 0; i < index; i++)
            x = x.next;                // O(n) в худшем случае
        return x;
    } else {
        Node<E> x = last;              // Ищем с конца
        for (int i = size - 1; i > index; i--)
            x = x.prev;                // O(n) в худшем случае
        return x;
    }
}

Сравнение с ArrayList

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

Пример 1: LinkedList как Queue (FIFO)

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

// Добавить в конец
queue.add("task1");          // O(1)
queue.add("task2");          // O(1)
queue.add("task3");          // O(1)

// Удалить с начала
String task = queue.remove();  // O(1) — removeFirst
// result: "task1"

// Это очень эффективно!
// ArrayList был бы медленнее: O(n) на каждое удаление

Пример 2: LinkedList как Stack (LIFO)

LinkedList<Integer> stack = new LinkedList<>();

// Положить в начало
stack.addFirst(1);           // O(1)
stack.addFirst(2);           // O(1)
stack.addFirst(3);           // O(1)

// Забрать с начала
int val = stack.removeFirst();  // O(1)
// result: 3

Пример 3: Добавление в начало (LinkedList быстрее!)

// ❌ ArrayList — медленно O(n)
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    list.add(0, "item" + i);  // O(n) на каждое добавление!
}  // Общая сложность: O(n²)

// ✅ LinkedList — быстро O(1)
LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 1000; i++) {
    list.addFirst("item" + i);  // O(1) на каждое добавление
}  // Общая сложность: O(n)

Итератор в LinkedList

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5));

// Прямой итератор: O(n) для полного обхода
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());  // O(1) на элемент
}

// Обратный итератор: O(n) для полного обхода
Iterator<Integer> rit = list.descendingIterator();
while (rit.hasNext()) {
    System.out.println(rit.next());  // O(1) на элемент
}

// ❌ Не делай так — O(n²)!
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));  // O(n) * size = O(n²)!
}

ListIterator для эффективного изменения во время итерации

LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c", "d", "e"));

// Удаление элементов эффективно
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    String str = it.next();
    if (str.equals("b")) {
        it.remove();  // O(1) удаление
    }
}

// Добавление элементов эффективно
it = list.listIterator();
while (it.hasNext()) {
    String str = it.next();
    if (str.equals("c")) {
        it.add("c+");  // O(1) добавление
    }
}

Использование Deque методов

LinkedList имплементирует Deque (Double Ended Queue):

LinkedList<Integer> deque = new LinkedList<>();

// Добавление
deque.addFirst(1);    // O(1) в начало
deque.addLast(2);     // O(1) в конец
deque.push(0);        // O(1) в начало (как Stack)

// Удаление
int first = deque.removeFirst();  // O(1) с начала
int last = deque.removeLast();    // O(1) с конца
int top = deque.pop();            // O(1) с начала (как Stack)

// Просмотр
int f = deque.peekFirst();        // O(1) первый
int l = deque.peekLast();         // O(1) последний
int t = deque.peek();             // O(1) первый (как Queue)

Проблемы с памятью

Проблема 1: Memory overhead

ArrayList<Integer>[100]:
- Массив: 100 * 8 bytes = 800 bytes
- Total: 800 bytes

LinkedList<Integer>[100]:
- 100 узлов * (8 + 8 + 4) = 100 * 20 = 2000 bytes
  (next ref + prev ref + Integer value)
- Plus: 16 bytes на List object
- Total: 2016 bytes

LinkedList использует в 2.5 раза больше памяти!

Проблема 2: Cache locality

ArrayList элементы идут подряд в памяти:

[Integer 1][Integer 2][Integer 3][Integer 4]...

Процессор кэширует соседние элементы — быстро!

LinkedList элементы разбросаны в памяти:

Heap: [Node1 in address 0x100]
      [Node2 in address 0x5000]
      [Node3 in address 0x200]
      [Node4 in address 0x8000]

Процессор не может кэшировать — медленнее!

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

✅ Используй LinkedList когда:

1. Часто добавляешь/удаляешь в начало: addFirst(), removeFirst()
2. Нужна очередь (Queue): добавление в конец, удаление с начала
3. Нужен стек (Stack): добавление в начало, удаление с начала
4. Часто используешь Iterator с remove() во время итерации

❌ НЕ используй LinkedList когда:

1. Часто обращаешься по индексу: get(index)
2. Нужен быстрый случайный доступ
3. Критична память
4. Критична скорость (cache locality matters)
5. ArrayList будет быстрее в большинстве случаев!

Заключение

LinkedList имплементирует двусвязный список с характеристиками:

• O(1) добавление/удаление на концах
• O(n) доступ по индексу
• O(n) поиск
• Высокий overhead памяти
• Плохая cache locality

В реальности ArrayList используется чаще потому что:

• Кэширование в процессоре важнее
• Памяти обычно хватает
• Array operations в JVM сильно оптимизированы

А LinkedList — отличный выбор когда специфично нужна O(1) операция на концах и используется как Queue/Stack.