- 推荐阅读：
- <strong>
- <strong>
- <strong>
前言
LinkedList由于实现了Deque这个接口，所以可以当栈和队列使用。不过一般要用栈或队列的时候推荐使用ArrayDeque,所以这里就不讲LinkedList的栈和队列功能了。还是和上篇ArrayList一样，讲些常用的方法。
LinkedList内部是由双链表组成的，里面存放着一个个Node，每个Node又包含三个元素(prev,item,next):
- prev:指向前一个Node
- item:存放存入的数据
- next:指向下一个Node
链表的第一个Node的prev为null，最后个Node的next为null
我简单的画了一张图，可以看下
这个prev和next并不是指向null，因为内存中没有为null分配空间，这边是表示是prev和next为null；
本文内容
01 内部变量
相比于Arraylist，LinkedList内部变量就少得多，就只有三个，size存这当前元素的个数，first指向链表的第一个，last指向列表的最后一个
02 构造方法
2.1 无参构造方法
（1）代码实现
<code>List<string>list=newLinkedList<>();/<string>/<code>
（2）源码分析
无参构造只是初始化了数据，并未做任何操作(初始化 size=0 first=null last=null)
2.2 有参构造方法
（1）代码实现
<code>List<string>oldList=newLinkedList<>();List<string>newList=newLinkedList<>(oldList);/<string>/<string>/<code>
（2）源码分析
由于篇幅有限，addAll()方法这边就不讲了，后面另写文章再讲，里面的操作就相当于把集合里的元素复制到新集合里面。
03 get方法
3.1 get(int index)
这里先讲get()方法，然后再讲add()方法，原因是插入方法里用到的调用的方法个get()方法里是一样的
（1）代码实现
<code>List<string>list=newLinkedList<>();list.add("hui");list.add("灰");list.add("灰2");list.add("灰3");list.get(2);/<string>/<code>（2）源码分析
- checkElementIndex(int index)检查越界
- node(int index)查找Node
04 add方法
4.1 add(E e)
（1）代码实现
<code>List<string>list=newLinkedList<>();list.add("hui");/<string>/<code>（2）源码分析
- linkLast(E e)连接最后一个元素
- Node
内部类
就像开头说的，每个Node里有三个，prev:指向前一个Node，item:存放存入的数据，next:指向下一个Node
<code>privatestaticclassNode{Eitem;Node /<code>next;Node prev;Node(Node prev,Eelement,Node next){this.item=element;this.next=next;this.prev=prev;}}
（3）流程图
- 第一次添加时的流程示意图
第一次添加时的流程示意图
- 不是第一次添加
不是第一次添加
4.2 add(int index, E element)
（1）代码实现
<code>List<string>list=newLinkedList<>();list.add("hui");list.add("灰");list.add(1,"hk");/<string>/<code>（2）源码分析
这边插入元素时，先判断插入的位置是不是尾部，如果不尾部的话，先调用和get()那个一样的方法，来查找要插入位置的当前元素，然后进行插入操作
- checkPositionIndex(int index)检查是否越界
这个检查越界的方法个get()检查越界的方法有点不同，它是可以等于size的，因为linkedList的索引设计也是从0开始的，
所以size永远比索引大1
- linkBefore(E e, Node
succ) 插入元素操作
（3）流程图
上面说的可能有点绕，看看流程图就明白了，哈哈
- 添加的位置为第一个
添加的位置为第一个
- 添加的位置为中间
添加的位置为中间
05 set方法
5.1 set(int index, E element)
（1）代码实现
<code>List<string>list=newLinkedList<>();list.add("hui");list.set(0,"灰");/<string>/<code>（2）源码解析
这里大多调用的是和get()里一样的方法
06 remove方法
6.1 remove(int index)
按索引删除，先找到被删除的Node，然后解除相关链接，设置Node里三大元素为null，删除后返回被删除Node里的item
（1）代码实现
<code>List<string>list=newLinkedList<>();list.add("hui");list.add("灰");list.remove(1);/<string>/<code>（2）源码解析
- unlink(Node
x) 解除Node的连接，然后返回被解除链接的item
（3）流程图
- 删除的是链表里的第一个元素
删除的是链表里的第一个元素
- 删除的是链表里的中间元素
- 删除的是链表里的最后一个元素
6.2 remove(Object o)
这个删除就比较慢了，它内部没有用二分查找算法，而是从头开始一一对比，时间复杂度为O(n)，这个删除也是
只删除最早添加的数据（1）代码实现
<code>List<string>list=newLinkedList<>();list.add("hui");list.remove("hui");/<string>/<code>（2）源码解析
unlink()方法就是上面讲的那个
07 clear方法
7.1 clear()
（1）代码实现
<code>List<string>list=newLinkedList<>();list.add("hui");list.clear();/<string>/<code>（2）源码解析
总结
LinkedList里删除，添加操作一般就两个步骤，变换前后Node指向的地址，删除操作把对应Node里的三个变量都设置为null，方便GC回收。
如果要删除元素时，最好选择传入索引删除，他比直接传入要删除的对象的方法要快很多
作者：灰灰H_K
原文链接：https://juejin.im/post/5e12861b6fb9a0481d28b510
閱讀更多 追逐仰望星空 的文章
