В чем разница между ArrayDeque и LinkedList?

В чем разница между ArrayDeque и LinkedList

Это популярный вопрос на Java интервью. Оба класса реализуют Deque (Double Ended Queue), но имеют существенные различия в производительности и использовании памяти.

Таблица сравнения

Структуры данных

ArrayDeque

Это динамический циклический буфер на базе массива:

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

     head         tail
      |            |
  [A][B][C][D][E][ ][ ]
   0  1  2  3  4  5  6

Когда добавляем в начало или конец:
- Если конец не полон: O(1)
- Если конец полон: расширяем массив (амортизировано O(1))

Циклический буфер:
  head = 4, tail = 2 (tail обогнул начало)
  
  [ ][B][C][ ][E][F][A]
   0  1  2  3  4  5  6

Внутренняя реализация:

public class ArrayDeque<E> extends AbstractCollection<E> 
    implements Deque<E>, Cloneable, Serializable {
    
    transient Object[] elements;  // Циклический буфер
    transient int head;            // Индекс первого элемента
    transient int tail;            // Индекс после последнего
}

LinkedList

Это двусвязный список:

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

  null <-> [Node: A] <-> [Node: B] <-> [Node: C] <-> null
  head                                              tail
  
Каждый Node:
public class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

Внутренняя реализация:

public class LinkedList<E> extends AbstractSequentialList<E> 
    implements List<E>, Deque<E>, Cloneable, Serializable {
    
    transient int size = 0;
    transient Node<E> first;  // Ссылка на первый элемент
    transient Node<E> last;   // Ссылка на последний элемент
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    }
}

Различия в производительности

1. Доступ по индексу

// ArrayDeque: O(1)
ArrayDeque<Integer> aq = new ArrayDeque<>();
for (int i = 0; i < 1000; i++) aq.add(i);
int element = aq.get(500);  // Быстро!

// LinkedList: O(n)
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 1000; i++) ll.add(i);
int element = ll.get(500);  // Медленно (проходит 500 узлов)

2. Итерация

// ArrayDeque: быстро (cache-friendly)
for (int x : deque) {
    // Элементы рядом в памяти - L1/L2 cache hit
}

// LinkedList: медленнее (cache-unfriendly)
for (int x : linkedList) {
    // Узлы разбросаны в памяти - много cache misses
}

3. Память

// ArrayDeque: компактнее
ArrayDeque<String> aq = new ArrayDeque<>();
aq.add("A");
// Память: Object[] массив + int head/tail

// LinkedList: больше памяти
LinkedList<String> ll = new LinkedList<>();
ll.add("A");
// Память: Node (E item + Node next + Node prev) x N
// На каждый элемент 2 дополнительных ссылки (24 байта на 64-бит Java)

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

ArrayDeque хорошо для:

// 1. Очередь (Queue)
Deque<Task> queue = new ArrayDeque<>();
queue.addLast(task1);
queue.addLast(task2);
Task t = queue.removeFirst();  // Быстро

// 2. Стек (Stack)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
int top = stack.pop();  // Быстро

// 3. Алгоритмы со скользящим окном
ArrayDeque<Integer> window = new ArrayDeque<>();
// ... максимум в окне размера K

// 4. Поиск в ширину (BFS)
Deque<TreeNode> bfs = new ArrayDeque<>();
bfs.addLast(root);
while (!bfs.isEmpty()) {
    TreeNode node = bfs.removeFirst();
    // ... обработка
}

LinkedList хорошо для:

// 1. Частые удаления/вставки в середину (если у вас есть итератор)
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");

ListIterator<String> it = list.listIterator(1);
it.next();  // B
it.add("X");  // Вставляет X между A и B - O(1)

// 2. Когда нужна реализация List (не только Deque)
List<String> list = new LinkedList<>();
list.get(0);  // Медленно, но возможно
list.add(0, "First");  // Вставка в начало

// 3. Очень редко используется сейчас

Бенчмарк

Реальные числа (примерные):

Операция: добавить 1 млн элементов и итерировать

ArrayDeque:
  - Память: ~4-8 MB
  - Время итерации: 5 ms
  - Скорость: 200 млн элементов/сек

LinkedList:
  - Память: ~40-80 MB (в 10 раз больше!)
  - Время итерации: 50 ms
  - Скорость: 20 млн элементов/сек

Из чего это следует?

// ArrayDeque использует grow() для расширения
private void doubleCapacity() {
    int n = elements.length;
    int r = n - (head - tail);  // Number of elements
    int newCapacity = n << 1;   // Удваиваем размер
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, head, a, 0, r);
    System.arraycopy(elements, 0, a, r, head);
    elements = a;
    head = 0;
    tail = r;
}

// LinkedList просто создаёт новый Node
private Node<E> linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(null, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    return newNode;
}

Правило большого пальца

Используй ArrayDeque по умолчанию для очередей и стеков!

// ✓ Правильно
Queue<Task> queue = new ArrayDeque<>();  // Быстро и эффективно

// ✗ Неправильно
Queue<Task> queue = new LinkedList<>();  // Медленнее и больше памяти

Исключения:

• Если нужны операции с индексом (get/set) - всё равно ArrayDeque
• Если нужна реализация List с частыми вставками в середину (редко)
• Если нужно хранить null'ы (LinkedList позволяет, ArrayDeque нет)

Итог

ArrayDeque почти всегда лучше LinkedList благодаря:

• Лучшей производительности (O(1) vs O(n) для индекса)
• Меньшему потреблению памяти
• Лучшей локальности кеша

LinkedList существует в основном для истории и edge cases. В современной Java ArrayDeque - стандартный выбор для очередей и стеков.