[java基础-集合篇]LinkedList源码粗析

LinkedList 的数据结构

实现List、Deque 接口，基于 双向链表实现的列表。与基于数组的 ArrayList 不同，基于链表的LinkedList 允许在列表的任何位置快速地插入和删除元素。

Java中LinkedList实现了Deque，它提供了 add, offer, remove, poll, element, peek 等方法，因此可以视LinkedList为一个基于链表的 双向队列。

双向链表的高效删除、添加元素，相较低的查询效率LinkedList也具备。

LinkedList 的每个元素都包含三个部分：

• 数据本身
• 指向前一个元素的引用（前驱）
• 指向后一个元素的引用（后继）

这种双向链接使得 LinkedList 可以很容易地向前或向后遍历，并且可以在 O(1) 时间内完成插入和删除操作。

LinkedList方法

get(int index)方法

调用node(int index)方法遍历链表返回指定index元素

add(E e)方法

使用add添加元素时，默认插入到尾部，所以不需要查找后更新|添加，实现复杂度是O（1）。

注意：LinkedList不需要扩容

由构造方法可以看出来，LinkedList是允许null值的，且null值数量不做限制

add(int index, E element)方法

找到原来的Index位置的元素，然后插入。 插入操作=创建一个新的节点+并将其连接到原index处节点前

remove()方法

这个方法是实现自Deque接口，具有队列性质，移除first节点

remove(int index)

这个是List的实现，遍历找出指定index的节点后然后移除

remove(Object o)方法

注意， 方法只会移除LinkedList链表中第一个匹配对象，如果返回false表示没有次对象。

LinkedList 的特点

• 插入和删除操作快：由于双向链表的特性，可以在 O(1) 时间内完成插入和删除。
• 不适合随机访问：相对于数组来说，链表的随机访问较慢，因为必须从头开始遍历链表直到找到所需的元素。
• 内存消耗较大：每个元素除了存储自身的数据外，还需要额外的空间来保存前后节点的引用，因此比数组占用更多的内存。
• 允许空值

优化点

remove(Object o)方法移除元素时，先进行空值 == null判断，然后item比较时使用 == null判断，这样比equals高效

LinkedList 相关的面试题

下面列出了一些与 LinkedList 相关的常见面试题：

1.解释什么是双向链表，并描述其优势。

- 双向链表是一种链表，其中每个节点包含对前一个节点和下一个节点的引用。这使得可以从前向后和从后向前遍历列表，也简化了插入和删除操作。

- 在 LinkedList 中，插入操作只需要修改相关节点的前后指针即可，因此时间复杂度为 O(1)。

2.LinkedList 和 ArrayList 之间的区别是什么？

- LinkedList 使用链表实现，适合频繁的插入和删除操作；ArrayList 使用数组实现，适合随机访问元素。

3.为什么 LinkedList 的 get(int index) 方法的时间复杂度是 O(n)?

- 因为 LinkedList 需要从头部或尾部开始遍历到指定索引的位置，最坏情况下可能需要遍历整个列表。

- LinkedList 提供了对 ListIterator 的支持，允许用户在迭代过程中添加、删除或修改元素。

4.如何检测 LinkedList 中是否存在环？（理论上标准的LinkedList不会出现环形链表）

- 常见的方法是使用 Floyd's Cycle-Finding Algorithm 或者称为龟兔赛跑算法，通过两个不同速度的指针来检测循环的存在。

5.如何反转一个 LinkedList？

- 反转 LinkedList 的一种方法是从头节点开始，逐个交换每个节点的前后指针，直到到达最后一个节点。

推荐资料

https://www.hello-algo.com/