02. LinkedList

LinkedList 是 List 和 Deque 接口的双向链表实现。它实现所有可选的 list作并允许所有元素（包括 null）。

1.特点

LinkedList 最重要的特点：

• 动态大小：链表的一个显著优点是其大小可以根据需要动态调整，不需要预先分配存储空间。
• 高效的插入和删除操作：在链表中插入或删除元素只需要改变相关节点的指针值，这使得这些操作比数组中的相应操作更高效。特别是在单链表中，如果知道要操作节点的前一个节点位置，就可以快速完成插入或删除。
• 顺序访问：与数组不同，链表不支持随机访问元素。要访问链表中的某个元素，必须从头节点开始，顺着链接依次访问直到找到目标节点。这意味着访问特定元素的时间复杂度为O(n)。
• 额外的内存开销：由于每个节点不仅要存储实际的数据，还要存储指向下一个节点的指针（对于双向链表，还有指向前一个节点的指针），因此链表相对于数组有更高的内存开销。
• 多种类型：根据链接的方式，链表可以分为单向链表、双向链表和循环链表等不同类型。每种类型都有其特定的应用场景和优缺点。
• 易于实现的简单性和灵活性：链表的实现相对简单，并且非常灵活，可以根据需求设计成不同的形式，如上面提到的不同类型的链表。

2.使用

LinkedList 的使用和 ArrayList 并无什么不同，不管是初始化的方式，还是 提供的API，并无差异。

3.队列

Deque 接口提供了类似队列的行为：

linkedList.poll();
linkedList.pop();

这些方法检索第一个元素并将其从列表中删除。

poll（） 和 pop（） 的区别在于 pop 会在空列表上抛出 NoSuchElementException（），而 poll 返回 null。API pollFirst（） 和 pollLast（） 也可用。

linkedList.push(Object o);

此方法将元素作为集合的头部插入。

4.总结

ArrayList 通常是默认的 List 实现。

但是，在某些场景中使用 LinkedList 会更合适，例如对恒定插入/删除时间（例如，频繁插入/删除/更新）、恒定访问时间和有效内存使用时。