LinkedList 作为队列和栈

一句话概括

LinkedList 同时实现了 List、Queue、Deque 三个接口，可以当作队列和栈使用。但推荐用 ArrayDeque。

---

LinkedList 的多重身份

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

// 作为 List
list.add(1);
list.get(0);

// 作为 Queue（队列 FIFO）
Queue<Integer> queue = list;
queue.offer(1);  // 入队
queue.poll();       // 出队

// 作为 Deque（双端队列）
Deque<Integer> deque = list;
deque.offerFirst(1);  // 队头入
deque.offerLast(2);    // 队尾入
deque.pollFirst();      // 队头出
deque.pollLast();       // 队尾出

---

队列操作（FIFO）

import java.util.*;

public class QueueDemo {

    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        // 入队（队尾）
        queue.offer("任务1");
        queue.offer("任务2");
        queue.offer("任务3");
        System.out.println("队列: " + queue);

        // 查看队首（不出队）
        System.out.println("队首: " + queue.peek());

        // 出队（队首）
        System.out.println("出队: " + queue.poll());
        System.out.println("出队: " + queue.poll());
        System.out.println("剩余: " + queue);
    }
}

输出：

队列: [任务1, 任务2, 任务3]
队首: 任务1
出队: 任务1
出队: 任务2
剩余: [任务3]

---

栈操作（LIFO）

import java.util.*;

public class StackDemo {

    public static void main(String[] args) {
        Deque<Integer> stack = new LinkedList<>();

        // 入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("栈: " + stack);

        // 查看栈顶（不出栈）
        System.out.println("栈顶: " + stack.peek());

        // 出栈
        System.out.println("出栈: " + stack.pop());
        System.out.println("出栈: " + stack.pop());
        System.out.println("剩余: " + stack);
    }
}

输出：

栈: [3, 2, 1]
栈顶: 3
出栈: 3
出栈: 2
剩余: [1]

---

双端队列操作

import java.util.*;

public class DequeDemo {

    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();

        // 两端入队
        deque.offerFirst("A");  // 头部
        deque.offerLast("D");    // 尾部
        deque.offerFirst("B");
        deque.offerLast("C");
        System.out.println("双端队列: " + deque);

        // 两端出队
        System.out.println("队头出: " + deque.pollFirst());
        System.out.println("队尾出: " + deque.pollLast());
        System.out.println("剩余: " + deque);
    }
}

输出：

双端队列: [B, A, D, C]
队头出: B
队尾出: C
剩余: [A, D]

---

ArrayDeque vs LinkedList：为什么推荐 ArrayDeque

指标	ArrayDeque	LinkedList
头尾操作	O(1)	O(1)
内存占用	连续，节省	每个节点多 2 个引用
CPU 缓存	友好	不友好
尾部追加性能	极快	快
按索引访问	❌	✅

性能对比

import java.util.*;

public class DequePerformanceDemo {

    public static void main(String[] args) {
        int size = 100_000;

        // ArrayDeque
        long start = System.nanoTime();
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < size; i++) {
            deque.addLast(i);
        }
        System.out.println("ArrayDeque 尾部追加: " + (System.nanoTime() - start) / 1_000_000 + " ms");

        // LinkedList
        start = System.nanoTime();
        Deque<Integer> list = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            ((LinkedList<Integer>) list).addLast(i);
        }
        System.out.println("LinkedList 尾部追加: " + (System.nanoTime() - start) / 1_000_000 + " ms");
    }
}

典型结果：

ArrayDeque 尾部追加: ~8 ms
LinkedList 尾部追加: ~25 ms

ArrayDeque 快 3 倍，且内存占用更少。

---

实际应用：任务调度器

import java.util.*;

public class TaskScheduler {

    private final Deque<Task> pendingTasks = new LinkedList<>();
    private final Deque<Task> completedTasks = new LinkedList<>();

    // 添加任务到队列
    public void submit(Task task) {
        pendingTasks.offerLast(task);
        System.out.println("已提交: " + task);
    }

    // 取出下一个任务
    public Task next() {
        return pendingTasks.pollFirst();
    }

    // 完成任务
    public void complete(Task task) {
        completedTasks.offerFirst(task); // 最近完成的放头部
        System.out.println("已完成: " + task);
    }

    // 查看最近完成的任务
    public Task recentCompleted() {
        return completedTasks.peekFirst();
    }

    public static void main(String[] args) {
        TaskScheduler scheduler = new TaskScheduler();
        scheduler.submit(new Task("用户下单"));
        scheduler.submit(new Task("库存扣减"));
        scheduler.submit(new Task("发送通知"));

        Task task = scheduler.next();
        task.run();
        scheduler.complete(task);
    }
}

class Task {
    String name;
    Task(String name) { this.name = name; }
    void run() { System.out.println("执行: " + name); }
    @Override public String toString() { return name; }
}

---

避坑指南

误区	正确做法
「LinkedList 做栈/队列最快」	ArrayDeque 比 LinkedList 快 3 倍
「Stack 是栈的标准实现」	Stack 继承 Vector，已过时，用 ArrayDeque
「LinkedList 比 ArrayList 增删快」	只有迭代器增删或头尾操作时才快
「LinkedList 适合做普通 List」	大多数场景用 ArrayList 更合适

---

总结

需求	推荐
普通 List	ArrayList
队列/栈	ArrayDeque
需要 List + Queue + Deque	LinkedList
迭代器遍历中增删	LinkedList
栈（过时）	Stack（不要用）

---

相关链接

• LinkedList 底层实现
• LinkedList 性能分析
• ArrayList vs LinkedList