[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 的一种方法是从头节点开始，逐个交换每个节点的前后指针，直到到达最后一个节点。