详解Java 集合系列(三)—— LinkedList
作者:那一叶随风 时间:2022-01-30 16:49:10
LinkedList
LinkedList是一种可以在任何位置进行高效地插入和删除操作的有序序列。
它的最基本存储结构是一个节点:每个节点将存储对象,以及前后节点的引用。
结构图
从上面的结构图中,我们可以了解到 ListedList 底层是基于双向链表实现的。
围起来的可以看成 LinkedList 类,它定义了三个 transient 成员变量:first、last、size。这三个变量是整个 LinkedList 类的关键点。
由于是双向链表(每个node都有保存前后节点的引用),因此我们不管是由 first 还是 last 节点开始迭代,都可以将整个链表的数据找出来;
在查询、随机插入以及set等操作都有涉及 size 判断;
由于 LinkedList 是双向链表,类中只存储了首尾两个节点,因此查询第n个元素都要从头遍历进行查找。
源码分析
add(E e) 源码分析
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last; // 将当前最后一个元素寄存在 l
final Node<E> newNode = new Node<>(l, e, null); // new 一个新节点:pre的引用为l;存储元素为e;next的引用为null
last = newNode; // 将新节点引用覆盖成员变量 last
if (l == null)
first = newNode; // 若l为null,说明之前链表为空,此时新节点为首个元素
else
l.next = newNode; // 否则,更新l的next引用
size++; // size+1
modCount++; // 非查询操作 modCount 都会 +1
}
add(int index, E element) 方法分析
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index); // 检查 index 是否大于 size
if (index == size)
linkLast(element); // 直接在链表末尾追加
else
linkBefore(element, node(index)); // 插入index 节点前面
}
// 检查 index 是否超出范围 超出则抛出 IndexOutOfBoundsException
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Tells if the argument is the index of a valid position for an
* iterator or an add operation.
*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
/**
* 根据 index 查找 node
* 该方法利用了双向链表的特性,index 距离哪个链表头近就从哪边开始开始遍历
* 时间复杂度为 O(n/2);
* 当 index 接近 size 的中间值时,效率最低
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { // size 右移一位(除以2)
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
优缺点
优点
增删元素效率高(只需要更新节点附近的引用即可)
缺点
由于查询需要进行遍历,因此效率低
知识脑图
以上所述是小编给大家介绍的Java 集合系列(三)—— LinkedList详解整合网站的支持!
来源:https://www.cnblogs.com/phpstudy2015-6/p/10626564.html#_label1
标签:Java,LinkedList
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Java特性队列和栈的堵塞原理解析
2023-10-13 14:15:55
Mybatis接口式编程的原理
2023-11-27 22:16:05
java Hibernate多对多映射详解及实例代码
2023-07-02 07:24:40
![](https://img.aspxhome.com/file/2023/2/61052_0s.png)
使用JAVA实现http通信详解
2023-11-12 12:21:12
![](https://img.aspxhome.com/file/2023/4/61924_0s.png)
Java实现走迷宫回溯算法
2022-06-02 05:11:29
![](https://img.aspxhome.com/file/2023/6/62976_0s.jpg)
聊聊Controller中RequestMapping的作用
2021-12-08 20:48:45
![](https://img.aspxhome.com/file/2023/9/63099_0s.png)
Java中如何动态创建接口的实现方法
2023-11-25 15:13:02
![](https://img.aspxhome.com/file/2023/9/60259_0s.png)
Android 如何实现动态申请权限
2023-07-30 00:51:31
Java 动态代理深入理解
2023-04-13 10:54:21
浅谈自定义校验注解ConstraintValidator
2023-07-06 03:10:53
![](https://img.aspxhome.com/file/2023/9/61529_0s.jpg)
spring中向一个单例bean中注入非单例bean的方法详解
2022-07-19 13:14:18
![](https://img.aspxhome.com/file/2023/7/62167_0s.png)
java实现文件夹解压和压缩
2022-06-07 03:00:39
JAVA WSIMPORT生成WEBSERVICE客户端401认证过程图解
2023-11-14 00:27:55
![](https://img.aspxhome.com/file/2023/5/58985_0s.png)
Java中去除字符串中所有空格的几种方法
2023-11-24 04:59:24
Java可变个数形参的方法实例代码
2023-01-15 18:35:56
![](https://img.aspxhome.com/file/2023/2/62372_0s.png)
Java Hibernate使用SessionFactory创建Session案例详解
2022-03-04 06:21:28
Java面向对象之抽象类,接口的那些事
2022-08-25 19:16:30
![](https://img.aspxhome.com/file/2023/0/61530_0s.jpg)
Java经典面试题最全汇总208道(二)
2023-11-09 08:13:39
![](https://img.aspxhome.com/file/2023/7/59067_0s.jpg)
Java编程中使用throw关键字抛出异常的用法简介
2023-08-27 17:04:19
![](https://img.aspxhome.com/file/2023/9/58209_0s.png)
C#中HttpWebRequest的用法详解
2023-06-18 22:39:27