JDK源码之LinkedList
1. 全局变量
// 列表容量
transient int size = 0;
// 指向第一个节点的指针
transient Node<E> first;
// 指向最后一个节点的指针
transient Node<E> last;
2. 构造器
// 构建一个空list
public LinkedList() {
}
// 构建一个包含c的list
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
tip:使用this关键字调用重载构造方法，避免相同的初始化代码，只能在构造方法中使用，必须位于构造方法的第一句。
3. 增删用到的双向链表的方法
双向链表是linkedList的基础。
// 将元素e作为linkedList最后一个元素；
void linkLast(E e) {final Node<E> l = last; //取原本的最后一个节点
final Node<E> newNode = new Node<>(l, e, null); // new一节点
last = newNode; // 将新节点赋值给last
if (l == null) // 前一个节点链接上新节点
first = newNode;
else
l.next = newNode;
size++; //更新size和修改次数
modCount++;}
// 将元素e作为linkedList第一个元素
private void linkFirst(E e) {final Node<E> f = first; //取原本的第一个节点
final Node<E> newNode = new Node<>(null, e, f); // new一个节点
first = newNode; //将新节点赋值给last
if (f == null)//后一个节点链接上新节点
last = newNode;
else
f.prev = newNode;
size++; //更新size和修改次数
modCount++;}
// 去掉链表中首个元素f
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;}
// succ节点前插入一个元素e
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;}
// 去掉非null的最后一个元素
private E unlinkLast(Node<E> l) {
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;}
// 去除某个非null元素
E unlink(Node<E> x) {
final E element = x.item;// 1. 保存x节点的元素，前后元素的指针
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) { // 2. x前一个元素链接x后一个元素
first = next;} else {
prev.next = next;
x.prev = null;}
if (next == null) { //3. x后一个元素链接x前一个元素
last = prev;} else {
next.prev = prev;
x.next = null;}
x.item = null;// 更新元素，容量和变更次数
size--;
modCount++;
return element;}
对于中间位置元素的增删，下面两个图可以很好的表示操作步骤：
插入操作示意图：（在c之前加入c1节点）
删除操作示意图：（删除c节点）
4. 方法
//在index位置插入c
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) {
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) //新链表
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) { //添加完后链接起来
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
5. 特性
LinkedList继承了Deque接口，具有队列的特性，同时作为双端队列，LinkedList还具有栈的特性。
队列方法：
栈：
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
6. ArrayList和LinkedList不同
- LinkedList不支持随机访问，因此访问非首尾元素效率较低，时间复杂度为O(n)，访问首尾时间复杂度为O(1)。
- 相比于ArrayList, LinkedList的优势在于插入、删除操作，只需要改变前后两个元素的指针，不需要移动后面的元素。
- LinkedList由双向链表实现，具有队列和栈的特性。ArrayList由数组实现。