ArrayList基于数组实现，LinkedList则是基于链表实现。
先看头节点和尾节点
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first; //要么头尾都是空，或者first不为空first之前为空
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
构造方法有两个
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
addAll（c）代码如下：
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);//检查index是否正确
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) { //插入位置为size，也就是在最后插入
succ = null; //succ为空节点
pred = last; //pred为原链表的末节点
} 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; //pred为null时，新节点指向头节点
else
pred.next = newNode; //否则，新节点就是pred.next
pred = newNode; 新节点给pred
}
if (succ == null) {
last = pred; 此时的pred指向末节点
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
放入头节点和尾节点
private void linkFirst(E e) {
final Node<E> f = first; 头节点赋给f
final Node<E> newNode = new Node<>(null, e, f);
first = newNode; 新节点给头节点
if (f == null)
last = newNode; 如果头节点是空，链表为空，链表中只有头节点
else
f.prev = newNode; 不然的话，新节点next指向原来的头节点
size++;
modCount++;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
在一个非空节点succ前插入节点，其实就是常规的节点插入链表，记得判断是否succ是头节点
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev; //pred为succ前节点
final Node<E> newNode = new Node<>(pred, e, succ); //构造待插入的新节点
succ.prev = newNode; //新节点next指向succ
if (pred == null)
first = newNode; //新节点充当头节点
else
pred.next = newNode; //正常插入
size++;
modCount++;
}
断开某个节点
//断开头节点
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next; 将头节点的next变成头节点
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
// 断开尾节点
/**
* Unlinks non-null last node l.
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev; 尾节点的prev弄成尾节点
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
//断开普通节点
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) { //此时该节点就是first
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;
}
