LinkedList односвязный или двусвязный

LinkedList в Java: Двусвязный список

Ответ: LinkedList — это двусвязный (doubly linked) список

В Java класс LinkedList реализует структуру данных двусвязного списка (doubly linked list), а не односвязного (singly linked list).

Структура узла в LinkedList

Каждый узел в 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;
    }
}

Основная разница:

• Односвязный список: каждый узел хранит ссылку только на следующий узел
• Двусвязный список: каждый узел хранит ссылки и на следующий, и на предыдущий узел

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

Односвязный список:

Node1 -> Node2 -> Node3 -> null

Двусвязный список (LinkedList в Java):

null <- Node1 <-> Node2 <-> Node3 -> null

Преимущества двусвязного списка

// Проход вперёд
for (String element : list) {
    System.out.println(element);
}

// Проход назад (благодаря двусвязности)
ListIterator<String> iterator = list.listIterator(list.size());
while (iterator.hasPrevious()) {
    System.out.println(iterator.previous());
}

Операции в LinkedList

LinkedList<String> list = new LinkedList<>();
list.add("A");      // O(1) — добавление в конец
list.addFirst("B"); // O(1) — добавление в начало (только в двусвязном)
list.addLast("C");  // O(1) — добавление в конец

list.remove();      // O(1) — удаление первого элемента
list.removeFirst(); // O(1) — удалить первый
list.removeLast();  // O(1) — удалить последний

list.getFirst();    // O(1) — получить первый
list.getLast();     // O(1) — получить последний
list.get(0);        // O(n) — получить элемент по индексу

Благодаря двусвязности можно эффективно работать с обоими концами списка.

Сравнение с ArrayList

// ArrayList — массив
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");           // O(1) amortized
arrayList.remove(0);          // O(n) — нужно сдвинуть все элементы
arrayList.add(0, "B");        // O(n) — нужно расширить и сдвинуть

// LinkedList — двусвязный список
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");          // O(1)
linkedList.remove(0);         // O(n) — нужно пройти до элемента
linkedList.addFirst("B");     // O(1) — добавление в начало
linkedList.removeLast();      // O(1) — удаление с конца

Почему Java выбрал двусвязный список

1. Двусторонний обход: можно эффективно итерировать в оба направления
2. Операции с концами: добавление/удаление в начало и конец — O(1)
3. ListIterator: более мощный итератор с методами previous(), hasPrevious()
4. Гибкость: подходит для очередей (Deque интерфейс)

// LinkedList реализует интерфейс Deque
Deque<String> deque = new LinkedList<>();
deque.addFirst("First");  // O(1)
deque.addLast("Last");    // O(1)
deque.removeFirst();       // O(1)
deque.removeLast();        // O(1)

Память и производительность

// Двусвязный список использует больше памяти
// На каждый элемент: ссылка на данные + 2 ссылки (prev, next)
// ArrayList использует просто массив

// Быстрее для:
// - Добавления/удаления в начало или конец: O(1) vs O(n)
// - Двустороннего обхода

// Медленнее для:
// - Доступа по индексу: O(n) vs O(1)
// - Поиска элемента: O(n) vs O(n), но с худшей локальностью памяти

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

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

// Использование как очередь (FIFO)
queue.addLast(1);    // Добавить в конец: O(1)
queue.addLast(2);
queue.addLast(3);

int first = queue.removeFirst(); // Удалить с начала: O(1)
int second = queue.removeFirst();

// Использование как стек (LIFO)
LinkedList<String> stack = new LinkedList<>();
stack.addFirst("First");  // O(1) — в начало
stack.addFirst("Second");

String top = stack.removeFirst(); // O(1) — с начала

Итог

LinkedList в Java — это двусвязный список (doubly linked list). Это позволяет:

• Эффективно добавлять/удалять элементы в начало и конец
• Итерировать в обе стороны
• Реализовать интерфейсы Deque, Queue, Stack
• Работать с элементами на обоих концах списка

Для большинства случаев лучше использовать ArrayList, но LinkedList полезен, когда часто добавляют/удаляют элементы в начало или работают с обеими концами структуры.