LinkedList源码分析(JDK1.8)
参考:https://www.cnblogs.com/gxl1995/p/7edbcaa403c9252b983dc8ef016f190a.html
参考:https://blog.csdn.net/fighterandknight/article/details/61476335
一、概述
LinkedList结构
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
1、LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
2、LinkedList 实现 List 接口,能对它进行队列操作。
3、LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
4、LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
5、LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
6、LinkedList 是非同步的。
transient关键字的作用
序列化:将对象信息转化为二进制信息,便于存储和网络传输
反序列化:将二进制信息恢复成对象信息
HashMap源,有个字段是用transient修饰的,确实没必要对这个modCount字段进行序列化,因为没有意义,modCount主要用于判断HashMap是否被修改
一个对象只要实现了Serilizable接口,这个对象就可以被序列化,添加了transient关键字的属性就不会被序列化
二 、源码分析
1、LinkedList属性
//元素的实际个数
transient int size = 0;
/**
指向第一个节点
* Pointer to first node.
* Invariant[ɪnˈveəriənt]: adj. 无变化的,不变的
(first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
指向最后一个节点
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
//内部类,用于实现链表
private static class Node<E> {
E item; //存储的元素
Node<E> next; //下一个节点,尾元素的next指向为null
Node<E> prev; //上一个节点,头元素的prev的指向为null
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
2、LinkedList构造方法
/**
* 默认构造方法,size为0,first和last的节点都为空
*/
public LinkedList() {
}
////通过一个集合初始化LinkedList,元素顺序有这个集合的迭代器返回顺序决定
public LinkedList(Collection<? extends E> c) {
this();//调用无参构造函数
addAll(c);//添加集合中的所有元素
}
////添加指定集合的元素到列表,默认从最后开始添加
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c); //传入当前的节点个数size=0,并将collection对象传递进去
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);//检查角标是否越界([0,size])
Object[] a = c.toArray(); //得到元素数组
int numNew = a.length;//要添加集合的长度
if (numNew == 0)//若没有元素要添加,直接返回false
return false;
//pred指定位置的前驱节点,succ指定位置的节点
Node<E> pred, succ;
if (index == size) {
//两种情况:1.要添加的list为空,2.添加到list的末尾
//这时:当前节点后一个节点初始化为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)
//如果list表为空
first = newNode;//若果前节点为null,则新加的节点为首节点
else
//如果存在前节点,前节点会向后指向新加的节点[-->]
pred.next = newNode;
//新加的节点成为前一个节点
pred = newNode;
}
//添加集合中的元素完成后,将指定位置后面的元素后移
if (succ == null) {
//如果list为空或者添加到list的末尾,最后添加的节点成为尾节点
last = pred;
} else {
//添加的位置是list中间,将指定位置和指定位置的元素后移
pred.next = succ;
succ.prev = pred;
}
//修改list大小
size += numNew;
modCount++;
return true;
}
3、方法分析
1、 add(E e)方法
该方法直接将新增的元素放置链表的最后面,然后链表的长度(size)加1,修改的次数(modCount)加1
/**
* 增加指定元素到list的末尾
*/
public boolean add(E e) {
linkLast(e);
return true;
}
//使用对应参数作为尾节点
void linkLast(E e) {
//将新加节点的前驱指向last节点(<--)
final Node<E> l = last;
//创建节点(前驱是last节点,元素为e,后继为null节点)
final Node<E> newNode = new Node<>(l, e, null);
//将last节点修改为指向新节点
last = newNode;
//判断新节点的前节点(就是以前的last节点)是不是为空
if (l == null)
//如果新节点的前节点为空,
// 说明这个list集合是一个空集合,这个新加节点是添加的第一个节点,
//将first节点修改为指向新节点
first = newNode;
else
//如果新节点的前节点不为空
//说明这个list集合有元素
//将前节点的后继修改为新节点(-->)
l.next = newNode;
size++;
modCount++;
}
add(E e)方法
在指定节点前插入节点
1、检查索引是否越界
2、如果指定位置是最后,则添加到链表最后
3、如果指定位置不是最后,则添加到指定位置之前
public void add(int index, E element) {
checkPositionIndex(index);//检查位置的角标,[0,size]
if (index == size) //如果指定位置为最后,则添加到链表最后
linkLast(element);
else
//如果指定位置不是最后,则添加到指定位置前
linkBefore(element, node(index));
}
//在指定节点前插入节点,节点succ不能为空
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;//取出指定节点的前驱节点
//新建一个以指定节点为后继节点,当指定节点的前驱节点为前驱节点的节点
final Node<E> newNode = new Node<>(pred, e, succ);
//修改指定节点的前驱为新节点
succ.prev = newNode;
if (pred == null)
//如果指定节点为first节点
first = newNode;//将first节点修改为新节点
else
//将指定节点的前节点指向新节点
pred.next = newNode;
size++;
modCount++;
}
2、remove()方法
remove方法本质调用的还是removeFirst方法
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//删除首节点并返回删除前首节点的值,首节点不为空,内部使用
private E unlinkFirst(Node<E> f) {
// 断言 f == first && f != null;
final E element = f.item;//取出首节点元素
final Node<E> next = f.next;//得到下一个节点
f.item = null;//将首节点元素置空
f.next = null; // 将节点后继置空,帮助回收
first = next;//首节点的下一个节点成为新的首节点
if (next == null)
//这判断,如果链表中就有一个节点,首节点和尾节点都指向这个节点的话
//首节点的下一个节点为空
last = null; //如果不存在下一个节点,则首尾都为null(空表)
else
next.prev = null;//如果存在下一个节点,那它向前指向null
size--;
modCount++;
return element;
}
removeLast方法
/**
* 删除和返回链表中的最后一个元素
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//删除尾节点并返回删除前尾节点的值,为节点不为空,内部使用
private E unlinkLast(Node<E> l) {
// 断言 l == last && l != null;
final E element = l.item;//获取值
final Node<E> prev = l.prev;//获取尾节点前一个节点
l.item = null;
l.prev = null; // 便于垃圾回收器清理
last = prev;//前一个节点成为新的尾节点
if (prev == null)
//这说明链表中只有一个节点(first和last都指向它)
first = null;//如果前一个节点不存在,则首尾都为null(空表)
else
prev.next = null;//如果前一个节点存在,先后指向null
size--;
modCount++;
return element;
}
remove(int index)方法
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* 返回指定索引的节点
*/
Node<E> node(int index) {
// 判断位置在链表前半段或者是后半段
if (index < (size >> 1)) {//如果index在链表的前半段
Node<E> x = first;//第一个节点
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//如果index在链表的后半段
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//删除不为空的节点x
E unlink(Node<E> x) {
// 断言 x != null;
final E element = x.item;//取出节点的元素
final Node<E> next = x.next;//取出节点的下一个节点
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--;
modCount++;
return element;
}