Java 集合系列（三）—— LinkedList - 好文

以脑图的形式来展示Java集合知识，让零碎知识点形成体系

LinkedList

LinkedList是一种可以在任何位置进行高效地插入和删除操作的有序序列。
它的最基本存储结构是一个节点：每个节点将存储对象，以及前后节点的引用。

结构图
LinkedList 结构体
从上面的结构图中，我们可以了解到 ListedList 底层是基于双向链表实现的。
围起来的可以看成 LinkedList 类，它定义了三个 transient 成员变量：first、last、size。这三个变量是整个
LinkedList 类的关键点。

* 由于是双向链表（每个node都有保存前后节点的引用），因此我们不管是由 first 还是 last 节点开始迭代，都可以将整个链表的数据找出来；
* 在查询、随机插入以及set等操作都有涉及 size 判断；
* 由于 LinkedList 是双向链表，类中只存储了首尾两个节点，因此查询第n个元素都要从头遍历进行查找。
源码分析

　　add(E e) 源码分析
1 /** 2 * Appends the specified element to the end of this list. 3 * 4
* <p>This method is equivalent to {@link #addLast}. 5 * 6 * @param e
element to be appended to this list 7 * @return {@code true} (as specified by {
@link Collection#add}) 8 */ 9 public boolean add(E e) { 10 linkLast(e); 11
return true; 12 } 13 14 /** 15 * Links e as last element. 16 */ 17 void
linkLast(E e) {18 final Node<E> l = last; // 将当前最后一个元素寄存在 l 19 final Node<E>
newNode =new Node<>(l, e, null); // new 一个新节点：pre的引用为l；存储元素为e；next的引用为null 20
last = newNode;// 将新节点引用覆盖成员变量 last 21 if (l == null) 22 first = newNode; //
若l为null，说明之前链表为空，此时新节点为首个元素 23 else 24 l.next = newNode; // 否则，更新l的next引用 25
size++;// size+1 26 modCount++; // 非查询操作 modCount 都会 +1 27 }
　　add(int index, E element) 方法分析
1 /** 2 * Inserts the specified element at the specified position in this
list. 3 * Shifts the element currently at that position (if any) and any 4 *
subsequent elements to the right (adds one to their indices). 5 * 6 * @param
index index at which the specified element is to be inserted 7 * @param
element element to be inserted 8 * @throws IndexOutOfBoundsException {
@inheritDoc} 9 */ 10 public void add(int index, E element) { 11
checkPositionIndex(index);// 检查 index 是否大于 size 12 13 if (index == size) 14
linkLast(element);// 直接在链表末尾追加 15 else 16 linkBefore(element, node(index)); //
插入index 节点前面 17 } 18 19 20 // 检查 index 是否超出范围超出则抛出 IndexOutOfBoundsException
21 private void checkPositionIndex(int index) { 22 if (!isPositionIndex(index))
23 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 24 } 25 26 /**
27 * Tells if the argument is the index of a valid position for an 28 *
iterator or an add operation.29 */ 30 private boolean isPositionIndex(int
index) {31 return index >= 0 && index <= size; 32 } 33 34 35 36 /** 37 * 根据
index 查找 node38 * 该方法利用了双向链表的特性，index 距离哪个链表头近就从哪边开始开始遍历 39 * 时间复杂度为 O(n/2)；
40 * 当 index 接近 size 的中间值时，效率最低 41 * Returns the (non-null) Node at the
specified element index.42 */ 43 Node<E> node(int index) { 44 // assert
isElementIndex(index); 45 46 if (index < (size >> 1)) { // size 右移一位（除以2） 47
Node<E> x = first; 48 for (int i = 0; i < index; i++) 49 x = x.next; 50 return
x;51 } else { 52 Node<E> x = last; 53 for (int i = size - 1; i > index; i--) 54
x = x.prev; 55 return x; 56 } 57 }

优缺点

优点

* 增删元素效率高（只需要更新节点附近的引用即可）
缺点

* 由于查询需要进行遍历，因此效率低

知识脑图

From Java Core Knowledge Tree
<https://links.jianshu.com/go?to=https%3A%2F%2Fgithub.com%2Fsuifeng412%2FJCKTree>
LinkedList 脑图
　　在 github 上建了一个 repository ，Java Core Knowledge Tree
<https://github.com/suifeng412/JCKTree>，各位看官若是喜欢请给个star，以示鼓励，谢谢。
https://github.com/suifeng412/JCKTree
<https://links.jianshu.com/go?to=https%3A%2F%2Fgithub.com%2Fsuifeng412%2FJCKTree>

（以上是自己的一些见解，若有不足或者错误的地方请各位指出）

作者：那一叶随风 <http://www.cnblogs.com/phpstudy2015-6/>
http://www.cnblogs.com/phpstudy2015-6/ <http://www.cnblogs.com/phpstudy2015-6/>

原文地址： https://www.cnblogs.com/phpstudy2015-6/p/10626564.html
<https://www.cnblogs.com/phpstudy2015-6/p/10626564.html>

<https://www.cnblogs.com/phpstudy2015-6/p/%20https://www.cnblogs.com/phpstudy2015-6/p/6732784.html>

声明：本博客文章为原创，只代表本人在工作学习中某一时间内总结的观点或结论。转载时请在文章页面明显位置给出原文链接

热门工具换一换