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

我是你爹

- `LinkedList<>` 和 `ArrayDeque<>` 的区别
- Queue接口和 Deque接口
- - 区别
  - `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