一、前言：
在上一篇：深入ArrayList源码分析jdk1.8文末，我们提到了ArrayList与LinkedList的主要区别，这次将深入分析LinkedList的实现原理。
二、LinkedList的数据结构：双向链表
image.png
说明：如上图所示，LinkedList底层使用双向链表的数据结构，有头结点和尾结点，使用双向链表可以实现正反向遍历。
三、LinkedList源码分析：
1、LinkedList的继承关系：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList的类继承结构里，着重关注Deque<E>接口，该接口表示一个双向队列（jdk 1.5引入的，在java,util.concurrent包下），LinkedList实现该接口表示LinkedList本身是双端队列的一种实现，因此，基于双端队列的操作在LinkedList里面都可以生效。
2、LinkedList类的内部类:
private static class Node<E> {
E item; // 数据域
Node<E> next; // 后继
Node<E> prev; // 前驱
// 构造函数，赋值前驱后继
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
内部类Node即是实际结点，用于存放实际数据
3、LinkedList类的属性：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 实际元素个数
transient int size = 0;
// 头结点
transient Node<E> first;
// 尾结点
transient Node<E> last;
}
说明：LinkedList的属性不多，其中实际元素个数、头结点、尾结点均用transient关键字修饰，即意味着在序列化的时候该域不会被序列化
4、LinkedList类的构造函数：
//lLinkedList()型构造函数
public LinkedList() {
}
//LinkedList(Collection<?extends E>)型构造函数
public LinkedList(Collection<? extends E> c) {
// 调用无参构造函数
this();
// 添加集合中所有的元素
addAll(c);
}
5、LinkedList核心方法分析：
5.1、add()方法：
public boolean add(E e) {
// 添加到末尾
linkLast(e);
return true;
}
add()方法用于向LinkedList中添加一个元素，且添加在尾部，具体添加通过linkedLast()方法实现，其源码如下：
void linkLast(E e) {
// 保存尾结点，l为final类型，不可更改
final Node<E> l = last;
// 新生成结点的前驱为l,后继为null
final Node<E> newNode = new Node<>(l, e, null);
// 重新赋值尾结点
last = newNode;
if (l == null) // 尾结点为空
first = newNode; // 赋值头结点
else // 尾结点不为空
l.next = newNode; // 尾结点的后继为新生成的结点
// 大小加1
size++;
// 结构性修改加1
modCount++;
}
调用方向：add()--->linkLast()
5.2、addAll()方法：
addAll有两个重载函数，addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型，我们平时习惯调用的addAll(Collection<? extends E>)型会转化为addAll(int, Collection<? extends E>)型，所以我们着重分析此函数
// 添加一个集合
public boolean addAll(int index, Collection<? extends E> c) {
// 检查插入的的位置是否合法
checkPositionIndex(index);
// 将集合转化为数组
Object[] a = c.toArray();
// 保存集合大小
int numNew = a.length;
if (numNew == 0) // 集合为空，直接返回
return false;
Node<E> pred, succ; // 前驱，后继
if (index == size) { // 如果插入位置为链表末尾，则后继为null，前驱为尾结点
succ = null;
pred = last;
} else { // 插入位置为其他某个位置
succ = node(index); // 寻找到该结点
pred = succ.prev; // 保存该结点的前驱
}
for (Object o : a) { // 遍历数组
@SuppressWarnings("unchecked") E e = (E) o; // 向下转型
// 生成新结点
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null) // 表示在第一个元素之前插入(索引为0的结点)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) { // 表示在最后一个元素之后插入
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
// 修改实际元素个数
size += numNew;
// 结构性修改加1
modCount++;
return true;
}
参数中的index表示在索引下标为index的结点的前面插入，在addAll()方法中，addAll()方法还会调用node()方法,此方法是根据索引下标找到该结点后再返回，具体源码如下：
Node<E> node(int index) {
// 判断插入的位置在链表前半段或者是后半段
if (index < (size >> 1)) { // 插入位置在前半段
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; // 返回该结点
}
}
说明：在根据索引查找结点时，会有一个小优化，结点在前半段则从头开始遍历，在后半段则从尾开始遍历，这样就保证了只需要遍历最多一半结点就可以找到指定索引的结点。
5.3、unlink()方法：
在调用remove移除结点时，会调用unlink()方法，将指定结点从链表中断开，其具体实现如下：
E unlink(Node<E> x) {
// 保存结点的元素
final E element = x.item;
// 保存x的后继
final Node<E> next = x.next;
// 保存x的前驱
final Node<E> prev = x.prev;
if (prev == null) { // 前驱为空，表示删除的结点为头结点
first = next; // 重新赋值头结点
} else { // 删除的结点不为头结点
prev.next = next; // 赋值前驱结点的后继
x.prev = null; // 结点的前驱为空，切断结点的前驱指针
}
if (next == null) { // 后继为空，表示删除的结点为尾结点
last = prev; // 重新赋值尾结点
} else { // 删除的结点不为尾结点
next.prev = prev; // 赋值后继结点的前驱
x.next = null; // 结点的后继为空，切断结点的后继指针
}
x.item = null; // 结点元素赋值为空
// 减少元素实际个数
size--;
// 结构性修改加1
modCount++;
// 返回结点的旧元素
return element;
}
四、思考：
对addAll()方法的实现思考：
1、在addAll函数中，传入一个集合参数和插入位置，然后将集合转化为数组，然后再遍历数组，挨个添加数组的元素
2、但是问题来了，为什么要先转化为数组再进行遍历，而不是直接遍历集合呢？从效果上两者是完全等价的，都可以达到遍历的效果。
3、关于为什么要转化为数组的问题，个人思考如下：
3.1. 如果直接遍历集合的话，那么在遍历过程中需要插入元素，在堆上分
配内存空间，修改指针域，这个过程中就会一直占用着这个集合，考虑正确同步的话，其他线程只能一直等待。
3.2. 如果转化为数组，只需要遍历集合，而遍历集合过程中不需要额外的操作，所以占用的时间相对是较短的，这样就利于其他线程尽快的使用这个集合。即是说，就是有利于提高多线程访问该集合的效率，尽可能短时间的阻塞。
五、总结：
LinkedList的要点如下：
1、排列有序、可重复
2、底层使用双向链表实现
3、查询较慢、增删快、add和remove快
4、线程不安全
参考资料：
1、博客园
2、个人总结
网友评论