1.说明
LinkedList是对链表的扩展，其底层使用链表实现，不是线程安全的集合类。其继承AbstractSequentialList，实现了List, Deque, Cloneable,Serializable各个接口，其中AbstractSequentialList继承了AbstractList抽象类，AbstractList是对支持随机读取的List的部分功能的抽象，AbstractSequentialList是对不支持随机读取的List的一部分功能的抽象。并且LinkedList实现了Deque接口，代表其支持双端队列的所有功能。
2.优缺点
LinkedList首先是链表的扩展，并且实现了双端队列的接口，所以其特点如下：
- 随机存储，优点是不需要提前申请空间
- 具有双端队列的所有功能，可以简单地实现先进先出和后进先出
- 新增和删除时间复杂度比较少
3.重要变量
//元素的个数
transient int size = 0;
//首节点
transient Node<E> first;
//尾节点
transient Node<E> last;
4.节点数据结构
在此之前，先介绍一下双端链表的数据结构
private static class Node<E> {
//节点的值
E item;
//下一个节点，如果为尾节点，则此值为null
Node<E> next;
//前一个节点，如果为首节点，则此值为null
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
5.重要方法
//向链表头添加元素
private void linkFirst(E e) {
final Node<E> f = first;
//设置新节点，令首节点等于新节点，并将新节点的next指向原来的首节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
//如果原来首节点为空，代表为空链表，则令尾节点也为新节点
，否则，令原来首节点的前一个节点为新节点
if (f == null)
last = newNode;
else
f.prev = newNode;
//元素个数与修改次数进行增加
size++;
modCount++;
}
//向链表尾添加元素
void linkLast(E e) {
final Node<E> l = last;
//设置新节点，令尾节点指向新节点，并且将新节点的prev指向原来的尾节点
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
//如果原来尾节点为空，代表为空链表，则令首节点也为新节点
，否则，令原来尾节点的下一个节点为新节点
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//在给定节点之前插入对应节点
void linkBefore(E e, Node<E> succ) {
//获取给定节点的前一个节点，设为pred
final Node<E> pred = succ.prev;
//设置新节点，令其prev为给定节点的前一个节点，next为给定节点
final Node<E> newNode = new Node<>(pred, e, succ);
//同时设置给定节点的前一个节点为新节点
succ.prev = newNode;
//判断pred是否为空，如果是，那么新节点就是首节点
，否则，直接令pred的下一个节点为新节点
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
//删除首节点
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
//将首节点中相关引用置空，防止内存泄漏
f.item = null;
f.next = null;
//令首节点为首节点的下一个节点
first = next;
//如果首节点为空，那么直接将尾节点也置空，
否则，将当前首节点的prev置为null
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
//删除尾节点
private E unlinkLast(Node<E> l) {
final E element = l.item;
final Node<E> prev = l.prev;
//将尾节点中相关引用置空，防止内存泄漏
l.item = null;
l.prev = null;
//令尾节点为尾节点的前一个节点
last = prev;
//如果尾节点为空，那么直接将首节点也置空，
否则，将当前尾节点的next置为null
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
//删除指定元素
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//如果指定节点的前一个节点为空，代表制定节点为首节点
，令首节点为指定节点的下一个节点，否则，指定节点
的prev的next节点为其自身的next节点，并且令指定节点
的prev节点为null
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
//同理，如果指定节点的下一个节点为null，代表指定节点为尾节点，令
尾节点等于指定节点的上一个节点，否则，指定节点的next节点的prev节点
等于其自身的prev节点，且令自身的next节点等于null
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//最后，将指定节点的item也置为null，防止内存泄漏
x.item = null;
size--;
modCount++;
return element;
}
//按照索引值与对应集合类进行批量添加
public boolean addAll(int index, Collection<? extends E> c) {
//检验index是否合法，就是检查其是否在[0,size]范围内，如果index为size，就是尾节点
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
//如果集合类长度为0，那么直接返回失败
if (numNew == 0)
return false;
//如果index与size大小相等，直接设置插入位置为尾节点
，否则，进行遍历查找节点，设置查找到的节点的前一个节点为插入节点
Node<E> pred, succ;
if (index == size) {
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);
//如果pred==null，代表index=0，此时直接插入首节点，令
首节点等于新节点，否则，直接令pred的下一个节点为新节点，然后依序插入
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//如果，succ==null，代表index==size，则是直接从
尾部进行插入，所以，直接令尾节点指向插入的最后一个节点即可
，否则，令最后一个插入节点的next等于succ，
令succ的prev等于最后一个插入节点即可（其实就是进行了一个衔接）
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
//对元素数量进行增加
size += numNew;
modCount++;
return true;
}
//根据索引查找对应的节点（调用这个方法的方法已经判断过index，所以直接使用）
Node<E> node(int index) {
//如果index靠近左边，从first开始遍历，否则，从last开始遍历
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;
}
}
网友评论