马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
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/
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
