linkedlist 实现 deque 接口，基于双向链表支持 o(1) 首尾增删查，适用于滑动窗口等场景；而 arraylist 首部操作为 o(n)，不适用。
LinkedList 在 Java 中实现了 Deque 接口，因此它不仅能作为列表使用，还能天然支持双端队列的所有操作——既可从头也可从尾高效地添加、删除和查看元素。理解这一点，关键在于认清 LinkedList 的底层结构（双向链表）与 Deque 行为的天然契合：每个节点自带前驱和后继引用，使得两端操作都只需 O(1) 时间。
Deque 接口赋予 LinkedList 的核心能力
Deque（Double-Ended Queue）定义了在队列两端进行插入和移除的标准方法。LinkedList 实现这些方法时，不依赖额外封装，而是直接利用其双向链表特性：
- 头部操作：addFirst(e)、offerFirst(e)、removeFirst()、pollFirst()、getFirst()、peekFirst() —— 全部作用于链表头节点（header.next），常数时间完成
- 尾部操作：addLast(e)、offerLast(e)、removeLast()、pollLast()、getLast()、peekLast() —— 全部作用于链表尾节点（header.prev），同样 O(1)
- 兼容队列/栈语义：用 add()/offer() + remove()/poll() 模拟 FIFO 队列；用 push() + pop() + peek() 模拟 LIFO 栈 —— 这些方法内部其实分别调用了 *First 或 *Last 版本
为什么不用 ArrayList 实现 Deque？
ArrayList 虽然也能通过 Collections.asLifoQueue() 等方式“模拟”双端行为，但本质不支持高效两端操作：
- 在头部 add(0, e) 或 remove(0) 需要整体平移后续元素，平均时间复杂度为 O(n)
- 而 LinkedList 的 addFirst/removeFirst 不涉及数据搬移，仅修改头节点指针和相邻节点的链接关系
- 所以当业务明确需要频繁首尾增删（如滑动窗口、撤销栈、任务调度缓冲区），LinkedList 是更合适的选择
实际使用中的注意事项
尽管功能强大，但需注意几个易被忽略的细节：
- 空容器行为差异：getFirst()/getLast() 在空时抛 NoSuchElementException；peekFirst()/peekLast() 则返回 null —— 生产代码中优先使用 peek 系列避免崩溃
- 线程不安全：LinkedList 本身不是线程安全的，若多线程并发操作 Deque 方法，需手动同步或改用 ConcurrentLinkedDeque
- 内存开销略高：每个元素额外携带两个引用（prev/next），比 ArrayList 占用更多内存，大数据量时需权衡
- 随机访问代价高：get(int index) 是 O(n) 查找，不要把它当数组用 —— 若需频繁按索引访问，应换用 ArrayList
一个典型应用场景：实现滑动窗口最大值
用 LinkedList 作为 Deque 维护窗口内“可能成为最大值”的候选索引（单调递减双端队列），能将算法优化到 O(n)：
- 窗口右扩时，从尾部弹出所有小于新元素的值（保持递减性）
- 窗口左缩时，检查队首索引是否已滑出，是则 removeFirst()
- 队首始终是当前窗口最大值对应索引 —— 直接 peekFirst() 即得
这个例子凸显了 Deque 接口 + LinkedList 实现带来的结构性优势：两端可控、顺序敏感、无须预分配空间。
