[java基础-聚集篇]LinkedList源码粗析
LinkedList 的数据结构实现List、Deque 接口，基于双向链表实现的列表。与基于数组的 ArrayList 不同，基于链表的LinkedList 答应在列表的任何位置快速地插入和删除元素。 Java中LinkedList实现了Deque，它提供了 add, offer, remove, poll, element, peek 等方法，因此可以视LinkedList为一个基于链表的双向队列。 双向链表的高效删除、添加元素，相较低的查询效率LinkedList也具备。 https://i-blog.csdnimg.cn/direct/ccaf641393bc44f58064ec264f5ea21a.png https://i-blog.csdnimg.cn/direct/80fc99745b7442f5bfe024b9b9fb6c65.png https://i-blog.csdnimg.cn/direct/5183556e7d6c4c6496b1bd0a3445771f.png LinkedList 的每个元素都包罗三个部门：
[*]数据本身
[*]指向前一个元素的引用（前驱）
[*]指向后一个元素的引用（后继）
这种双向链接使得 LinkedList 可以很容易地向前或向后遍历，并且可以在 O(1) 时间内完成插入和删除操纵。 LinkedList方法
get(int index)方法
https://i-blog.csdnimg.cn/direct/b23c652fc27b40969d2cd1145ada3ddb.png 调用node(int index)方法遍历链表返回指定index元素 https://i-blog.csdnimg.cn/direct/2a5cc9fb00684b3995c154eb2f545a5e.pngadd(E e)方法
使用add添加元素时，默认插入到尾部，以是不需要查找后更新|添加，实现复杂度是O（1）。 留意：LinkedList不需要扩容 https://i-blog.csdnimg.cn/direct/f521958550c3400686d67dc3df805a45.png 由构造方法可以看出来，LinkedList是答应null值的，且null值数量不做限制 https://i-blog.csdnimg.cn/direct/d46fb6b8590c4dd786ca307008a95910.png add(int index, E element)方法
找到原来的Index位置的元素，然后插入。插入操纵=创建一个新的节点+并将其连接到原index处节点前 https://i-blog.csdnimg.cn/direct/9c0fb0facd7446a187ee68db1564a85d.png https://i-blog.csdnimg.cn/direct/61b2af61b95c4b30a5921f621433756e.pngremove()方法
这个方法是实现自Deque接口，具有队列性质，移除first节点 https://i-blog.csdnimg.cn/direct/60ca97485e4a4658964850eef97bea4a.pngremove(int index)
这个是List的实现，遍历找出指定index的节点后然后移除 https://i-blog.csdnimg.cn/direct/022921dfa2234db4b1d0ee37585e127a.pngremove(Object o)方法
留意，方法只会移除LinkedList链表中第一个匹配对象，假如返回false表现没有次对象。 https://i-blog.csdnimg.cn/direct/e00bf11a77034ac79b072d470b9c3e0b.png 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/
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]