Java中 LinkedList＜＞，ArrayDeque＜＞的区别 || Queue和Deque的区别

LinkedList<> 和 ArrayDeque<> 的区别

1. 数据结构实现方式：

• LinkedList：
  • 基于链表结构，是一个双向链表。
  • 每个元素都是节点，包含值和指向前一个和后一个节点的指针。
• ArrayDeque：
  • 基于动态数组实现，内部维护了一个循环数组。
  • 当容量不足时，会重新分配更大的数组并复制元素。

2. 性能差异：

• 插入和删除操作：
  • LinkedList：在链表的头部和尾部进行插入和删除的时间复杂度是 (O(1))。但是，链表的中间插入和删除需要遍历，时间复杂度为 (O(n))。
  • ArrayDeque：在队列的头部和尾部进行插入和删除的时间复杂度是 (O(1))，因为它是一个双端队列，但在动态扩展数组容量时会有额外的开销。
• 随机访问：
  • LinkedList：不支持随机访问。要访问中间的某个元素，需要遍历整个链表，时间复杂度为 (O(n))。
  • ArrayDeque：不提供随机访问，但由于其基于数组实现，整体的内存布局更加紧凑，缓存命中率高。

3. 内存开销：

• LinkedList：由于每个节点都有前向和后向指针，因此在存储元素时存在较大的内存开销。
• ArrayDeque：内存使用效率较高，但当数组扩容时，需要占用更多的内存空间来存储新数组和复制元素。

4. 允许存储 null 元素：

• LinkedList：允许存储 null 值。
• ArrayDeque：不允许存储 null 值，因为 null 通常用来指示队列为空的状态，避免引起歧义。

5. 使用场景：

• LinkedList：适合需要频繁在链表中间插入或删除的场景，或者需要作为双端链表（如实现 Deque 时）。
• ArrayDeque：性能一般比 LinkedList 更好，适合用作栈、队列和双端队列。通常 ArrayDeque 被认为是栈和队列的更好的选择，因为它的性能更稳定、效率更高。

Queue 和 Deque 是 Java 中的接口，分别用于定义队列（FIFO）和双端队列（可作为栈或队列）。它们的用法有所不同，下面为你详细介绍 Queue 和 Deque 的常见用法以及它们支持的方法。

Queue接口 和 Deque接口

区别

特性	Queue 接口	Deque 接口
插入位置	只能在尾部插入	可以在头部和尾部插入
删除位置	只能从头部删除	可以从头部和尾部删除
数据结构	先进先出（FIFO）	支持先进先出（FIFO）和后进先出（LIFO）
常见实现类	LinkedList、PriorityQueue	LinkedList、ArrayDeque
常用方法	add()、offer()、poll()、peek()	addFirst()、addLast()、removeFirst()、removeLast()
典型应用场景	任务排队，消息队列	栈实现，双端队列，缓存机制

• Queue 主要用于实现简单的先进先出（FIFO）队列，只能在尾部插入、头部移除，适合任务调度和消息处理。
• Deque 更加灵活，可以在两端进行操作，既可以用作队列，也可以用作栈，适合需要双端操作的场景。

Queue 的用法

Queue 是一个单端队列接口，遵循 先进先出（FIFO） 的原则。常见的实现类包括 LinkedList 和 PriorityQueue。Queue 接口主要用于任务排队、消息队列等应用场景。

常见实现

Queue<Integer> queue = new LinkedList<>();
// 或
Queue<Integer> queue = new ArrayDeque<>();

主要方法

• add(E e)：将元素 e 添加到队列尾部，如果队列已满则抛出异常。
• offer(E e)：将元素 e 添加到队列尾部，返回 true 表示成功，false 表示失败。
• remove()：移除并返回队列头部的元素，如果队列为空，则抛出 NoSuchElementException。
• poll()：移除并返回队列头部的元素，如果队列为空，则返回 null。
• element()：返回队列头部的元素，但不移除，如果队列为空，则抛出 NoSuchElementException。
• peek()：返回队列头部的元素，但不移除，如果队列为空，则返回 null。

示例代码

Queue<Integer> queue = new LinkedList<>();// 添加元素
queue.add(1);
queue.offer(2);// 获取队列头部元素
System.out.println(queue.peek()); // 输出：1// 移除队列头部元素
System.out.println(queue.poll()); // 输出：1// 获取并移除头部元素
System.out.println(queue.remove()); // 输出：2// 检查队列是否为空
System.out.println(queue.isEmpty()); // 输出：true

使用场景

• 任务排队：适用于管理任务的执行顺序，确保按顺序进行处理。
• 消息队列：用于消息的排队和处理。

Deque 的用法

Deque（Double-Ended Queue，双端队列）是一个接口，允许在队列的两端插入和删除元素，支持既作为**队列（FIFO）使用，也可以作为栈（LIFO）**使用。常见的实现类有 LinkedList 和 ArrayDeque。

常见实现

Deque<Integer> deque = new LinkedList<>();
// 或
Deque<Integer> deque = new ArrayDeque<>();

主要方法

• 在队首操作：

  • addFirst(E e)：将元素 e 添加到队列的头部，如果失败则抛出异常。
  • offerFirst(E e)：将元素 e 添加到队列的头部，返回 true 表示成功，false 表示失败。
  • removeFirst()：移除并返回队列头部的元素，如果队列为空则抛出 NoSuchElementException。
  • pollFirst()：移除并返回队列头部的元素，如果队列为空则返回 null。
  • getFirst()：返回队列头部的元素，但不移除，如果队列为空则抛出 NoSuchElementException。
  • peekFirst()：返回队列头部的元素，但不移除，如果队列为空则返回 null。

• 在队尾操作：

  • addLast(E e)：将元素 e 添加到队列的尾部，如果失败则抛出异常。
  • offerLast(E e)：将元素 e 添加到队列的尾部，返回 true 表示成功，false 表示失败。
  • removeLast()：移除并返回队列尾部的元素，如果队列为空则抛出 NoSuchElementException。
  • pollLast()：移除并返回队列尾部的元素，如果队列为空则返回 null。
  • getLast()：返回队列尾部的元素，但不移除，如果队列为空则抛出 NoSuchElementException。
  • peekLast()：返回队列尾部的元素，但不移除，如果队列为空则返回 null。

作为栈使用的方法

• push(E e)：将元素 e 压入栈（等同于 addFirst()）。
• pop()：移除并返回栈顶元素（等同于 removeFirst()）。

示例代码

Deque<Integer> deque = new ArrayDeque<>();// 在头部和尾部插入元素
deque.addFirst(1);   // 头部插入 1
deque.addLast(2);    // 尾部插入 2// 获取头部和尾部元素
System.out.println(deque.getFirst()); // 输出：1
System.out.println(deque.getLast());  // 输出：2// 在头部和尾部移除元素
deque.removeFirst(); // 移除头部元素
deque.removeLast();  // 移除尾部元素// 作为栈使用
deque.push(3);       // 压入栈顶（头部）
System.out.println(deque.pop());  // 弹出栈顶，输出：3

使用场景

• 双端操作：需要在两端进行插入和删除的场景。
• 栈和队列：Deque 可以既当作栈使用，也可以当作队列使用，灵活性更高。
• 实现复杂的数据结构：例如支持同时在两端操作的缓存机制、滑动窗口等。