LinkedList [ 小全能 ]

• LinkedList是双向链表实现的List
• LinkedList还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用 ```java

  下列两种定义 list 可调用的 API 是不同的

  List list = new LinkedList<>();

LinkedList list = new LinkedList<>();

<a name="o7wGh"></a>
## ArrayList
**ArrayList **底层是基于数组来实现容量大小动态变化的。
```java
List<Integer> list = new ArrayList<>();

Stack

 Stack<Integer> stack = new Stack<>();

HashMap

用来判断重复，并且在 O(1) 内查找出 key

Map<Integer,Integer> map=new HashMap<>();

Queue

普通队列常用来 BFS 搜索

Queue<Integer> queue = new LinkedList<>();

1. offer() 和 add() 的区别

都是向队列中添加一个元素。但是如果想在一个满的队列中加入一个新元素

  - 调用 **offer() **方法会返回 **false**。
  - 调用** add() **方法就会抛出一个 **unchecked 异常**，

1. peek() 和 element()的区别

都在不移除的情况下返回队头

  - 调用 **peek()** 方法在队列为空时返回 **null**
  - 调用 **element() **方法会抛出 **NoSuchElementException **异常。

1. poll() 和 remove() 的区别

都在移除的情况下返回队头

  - 但是在 **poll() **在队列为空时返回 **null**
  - 而 **remove() **会抛出 **NoSuchElementException **异常。

• √ 添加元素 ：queue.offer(元素);
• 添加元素 ：queue.add(元素);
• √ 删除队首元素：queue.poll()；
• 删除队首元素：queue.remove()；
• √ 查询队首元素：queue.peek()；
• 查询队首元素：queue.element()；

  PriorityQueue

  用优先队列创建大根堆，小根堆

  大根堆

  top 优先级： 9 8 7 6 5 4 3 2 1

  //1.定义优先队列,内部结构是堆,定义的 comparator 导致此处是大根堆 
  PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
  public int compare(Integer num1, Integer num2) {
     return num2 - num1;
  }
  });
  

  小根堆

  lamda 表达式简化版小根堆
  top 优先级： 1 2 3 4 5 6 7 8 9

  Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);