Реализует ли LinkedList Deque

LinkedList и Deque: иерархия интерфейсов в Java Collections

Прямой ответ

ДА, LinkedList реализует (implements) интерфейс Deque.

Полная иерархия:

LinkedList
    ↓ implements
    Deque<E>
        ↓ extends
        Queue<E>
            ↓ extends
            Collection<E>

Доказательство из исходного кода Java

// Из java.util.LinkedList
public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // ...
}

Как видишь, LinkedList явно implements Deque<E>.

Что такое Deque

Deque (Double-Ended Queue) — это очередь с двумя концами, где можно добавлять и удалять элементы с обоих сторон.

Обычный Queue (очередь):
add → [1, 2, 3, 4] → remove
       ↑ сзади        ↑ спереди
       (только сзади) (только спереди)

Deque (двусторонняя очередь):
    add/remove
        ↓        ↓
    ← [1, 2, 3, 4] →
        ↑        ↑
    add/remove
    (с обеих сторон)

Методы Deque, которые реализует LinkedList

public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        
        // Добавление элементов
        deque.addFirst(1);      // Добавить в начало
        deque.addLast(2);       // Добавить в конец
        deque.add(3);           // addLast по умолчанию
        // Deque: [1, 2, 3]
        
        // Удаление элементов
        int first = deque.removeFirst();  // Удалить первый → 1
        int last = deque.removeLast();    // Удалить последний → 3
        // Deque: [2]
        
        // Просмотр без удаления
        int head = deque.getFirst();      // 2
        int tail = deque.getLast();       // 2
        
        // Безопасные версии (return null вместо исключения)
        Integer first2 = deque.peekFirst();  // 2, null если пусто
        Integer last2 = deque.peekLast();    // 2, null если пусто
        
        // Удаление с возвратом null
        Integer f = deque.pollFirst();  // 2, null если пусто
        Integer l = deque.pollLast();   // null если пусто
    }
}

LinkedList как Stack (LIFO)

Так как LinkedList реализует Deque, его можно использовать как Stack (Last In, First Out):

// ✅ Правильное использование Stack
Deque<String> stack = new LinkedList<>();

stack.push("first");   // Добавить на вершину
stack.push("second");
stack.push("third");
// Stack: [third, second, first] (third на вершине)

String top = stack.pop();  // Снять с вершины → "third"
String peek = stack.peek();  // Посмотреть вершину → "second"

// ❌ Плохо — использовать эту архаичную класс Stack
// Stack<String> oldStack = new Stack<>();  // Не используй!

LinkedList как Queue (FIFO)

Как обычная Queue (First In, First Out):

// ✅ LinkedList как Queue
Queue<String> queue = new LinkedList<>();

queue.add("first");    // Добавить в конец
queue.add("second");
queue.add("third");
// Queue: [first, second, third]

String head = queue.remove();  // Снять с начала → "first"
String peek = queue.peek();    // Посмотреть начало → "second"

// Безопасные версии
String head2 = queue.poll();   // Снять с начала или null

Реальный пример: парсинг скобок (Stack)

public class BracketValidator {
    public static boolean isValidBrackets(String s) {
        Deque<Character> stack = new LinkedList<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);  // Открывающая скобка
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) return false;
                char open = stack.pop();  // Получить открывающую
                
                if ((c == ')' && open != '(') ||
                    (c == ']' && open != '[') ||
                    (c == '}' && open != '{')) {
                    return false;  // Несоответствие
                }
            }
        }
        
        return stack.isEmpty();  // Все скобки закрыты
    }
    
    public static void main(String[] args) {
        System.out.println(isValidBrackets("()[]{}"));    // true
        System.out.println(isValidBrackets("([)]"));      // false
        System.out.println(isValidBrackets("{[]}"));      // true
    }
}

Реальный пример: очередь задач (Queue)

public class TaskQueue {
    private Queue<Task> tasks = new LinkedList<>();
    
    public void enqueueTask(Task task) {
        tasks.add(task);  // Добавить в конец очереди
    }
    
    public Task dequeueTask() {
        return tasks.poll();  // Снять с начала (FIFO)
    }
    
    public int getPendingCount() {
        return tasks.size();
    }
}

// Использование
Queue<String> printQueue = new LinkedList<>();
printQueue.add("Document1.pdf");
printQueue.add("Document2.pdf");
printQueue.add("Document3.pdf");
// В очереди печати: Document1, затем Document2, затем Document3

while (!printQueue.isEmpty()) {
    String doc = printQueue.poll();  // FIFO
    System.out.println("Printing: " + doc);
}

Иерархия Collection Framework

Collection<E>
├── List<E>              (упорядоченная, с индексами)
│   ├── ArrayList
│   ├── LinkedList       ← Implements
│   └── Vector
├── Set<E>              (уникальные элементы)
│   ├── HashSet
│   ├── TreeSet
│   └── LinkedHashSet
├── Queue<E>            (очередь, FIFO)
│   ├── LinkedList       ← Implements
│   ├── PriorityQueue
│   └── ArrayDeque
└── Deque<E>            (двусторонняя очередь)
    ├── LinkedList       ← Implements
    └── ArrayDeque

Сравнение структур данных на базе LinkedList

// LinkedList implements: List, Deque, Queue

// Как List
List<String> list = new LinkedList<>();
list.add(0, "first");      // Добавить по индексу
String elem = list.get(0); // Получить по индексу

// Как Queue (FIFO)
Queue<String> queue = new LinkedList<>();
queue.add("first");        // Добавить в конец
queue.poll();              // Снять с начала

// Как Deque (с двумя концами)
Deque<String> deque = new LinkedList<>();
deque.addFirst("start");   // Добавить в начало
deque.addLast("end");      // Добавить в конец
deque.removeFirst();       // Снять с начала
deque.removeLast();        // Снять с конца

// Как Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("item");        // Поместить на вершину
stack.pop();               // Снять с вершины

Таблица: методы Queue, Deque, Stack

Почему LinkedList реализует несколько интерфейсов

1. List — для доступа по индексу (хоть и неэффективно O(n))
2. Queue — для работы как очередь FIFO
3. Deque — для работы с обоими концами
4. Cloneable — для копирования
5. Serializable — для сохранения

Это гибкое проектирование — один класс, много способов использования.

Производительность LinkedList для разных операций

Операция          | Сложность | Примечание
────────────────────────────────────────────
get(index)        | O(n)      | Нужно пройти по элементам
add(E)           | O(1)      | Добавить в конец
add(0, E)        | O(1)      | Добавить в начало
remove(0)        | O(1)      | Удалить с начала
remove(n)        | O(n)      | Удалить с конца
removeFirst()    | O(1)      | ← Из Deque
removeLast()     | O(1)      | ← Из Deque
addFirst()       | O(1)      | ← Из Deque
addLast()        | O(1)      | ← Из Deque

Вывод

Да, LinkedList реализует Deque — это ключевая особенность:

1. LinkedList can be used as:

   • List (с индексами)
   • Queue (FIFO)
   • Deque (двусторонняя)
   • Stack (LIFO)

2. Это правильный выбор для Stack/Queue в современной Java (вместо архаичного Stack класса)

3. О(1) операции с обоих концов — главное преимущество LinkedList для Deque

4. ArrayDeque — лучше для Deque, чем LinkedList (меньше памяти, лучше cache locality)