响应式旅游网站模板下载,做网站推广送什么,网页设计师培训费用预算图,建设购物网站需要多少费用LinkedList 的数据结构 实现List、Deque 接口#xff0c;基于 双向链表实现的列表。与基于数组的 ArrayList 不同#xff0c;基于链表的LinkedList 允许在列表的任何位置快速地插入和删除元素。 Java中LinkedList实现了Deque#xff0c;它提供了 add, offer, remove, poll, …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添加元素时默认插入到尾部所以不需要查找后更新|添加实现复杂度是O1。 注意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不会出现环形链表
- 常见的方法是使用 Floyds Cycle-Finding Algorithm 或者称为龟兔赛跑算法通过两个不同速度的指针来检测循环的存在。
5.如何反转一个 LinkedList
- 反转 LinkedList 的一种方法是从头节点开始逐个交换每个节点的前后指针直到到达最后一个节点。 推荐资料 https://www.hello-algo.com/
