【Java源码】基于链表实现的LinkedList
众所周知，LinkedList是基于链表实现的。
目录
基本属性
transient int size = 0;
transient Node<E> first;
transient Node<E> last; 基本属性中给出了长度，头结点和尾结点，都是transient，即 不可序列化。Node类如下：
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;
}
} 由定义可以看出，每个结点都包含指向其前一个和后一个结点的两个结点，还包含一个“数据”，类型为泛型 E
好吧，明摆着双向链表嘛。
构造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
} 两个构造方法，无参构造和根据已有Collection构造LinkedList;
根据已有Collection构造LinkedList先是无参构造，再将c全部add进去，既然这里用到了add，那咱就先看LinkedList元素的增加方法
增加元素(插入元素)
public boolean add(E e) {
linkLast(e);
return true;
}
// 头插
public void addFirst(E e) {
linkFirst(e);
}
// 尾插
public void addLast(E e) {
linkLast(e);
} boolean add(E e)
返回值为boolean类型，增加成功返回true；add方法是在其最后加入待加元素。
void linkLast(E e) 在list最后插入元素
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++;
} 一句话：原list为空，则参数做新头；若不为空，则参数加到末节点后。具体如下：
这个方法先拿出原末节点l，根据末节点l和参数创建新节点，更新新末节点last
判断原末节点是否为空，若是，则证明原先list无元素，新节点为list首节点；若非空，将新节点加到原末节点l后。更新size和modCount，根据上次ArrayList的经验，modCound应该是在迭代器中做判断的。
void linkFirst(E e) 在list头插入元素
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
} 思想如上说过的尾插法，因为LinkList基于双向链表实现，所以插入操作只需改变结点两个指针指向就行，这点比ArrayList的增加插入要简便的多！
void add(int index, E element)
在下标位置处插入元素
参数：一个下标，一个元素。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
首先检查下标合法性checkPositionIndex(index)
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
} 当然进行判断，判断该下标是不是最后。来决定如何插入。
说说 linkBefore(element, node(index)
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 = newNode;
else
pred.next = newNode;
size++;
modCount++;
} 传入参数为一个元素，和一个结点（通过下标得到的）、
取出参数结点的前驱结点，以新元素创造一个新节点，连接至前驱结点后参数结点前
再更新各结点指向关系完成操作！
boolean addAll(Collection<? extends E> c)
返回值boolean，参数为一个集合
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
} 调用
boolean addAll(int index, Collection<? extends E> c)
另外传入一个index下标。即插入到该下标位置
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
// 将参数转化为数组，若次数组长度为0.则直接返回false
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// 准备两个结点
// 可以理解为：这两个结点就是参数c的头和尾
// 头list连接待插元素，尾list连接原list下标及之后元素
// 判断插入的位置是否在原list最后（判断尾的位置）
// 因为在尾部直接加和在中间插入一段的操作完全不同
// 这里用到了node(index)方法。取出下标结点，尾list，这个方法我一会说。
// 头list当然就是尾之前的一个喽
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
// 思路很简单了：将参数转化的数组，依次插入到头list后；
// 再将尾list接到头list之后 （当然这里肯定要分null和非null情况）
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;
} 首先检查下标合法性checkPositionIndex(index)。上面说过这个方法
代码如上，因为比较长，以注释形式写出了。
这是刚才说到的取下标结点的方法 Node<E> node(int index)
Node<E> node(int index) {
// assert isElementIndex(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;
}
} 很简单，就是遍历，但增加了一个判断。用来决定从头开始还是从尾开始。
删除元素
1.删除头或尾元素
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
} E removeFirst() 和 E removeLast() 两个方法，字面意思，移除并返回头或尾的元素。返回为泛型E，调用E unlinkLast(Node<E> node)方法和E unlinkFirst(Node<E> node)方法
E unlinkFirst(Node<E> node) 断开传入头结点的连接并返回该结点元素，移除该结点
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;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
} 根据传入结点的得到其元素，以后返回的就是他。
得到传入结点的下一个元素，目的是更新头结点。旧头结点的各“指针”和 元素 也要更新为null。为什么？方便GC（垃圾回收装置）回收，释放内存。
同时新头结点的信息（前驱结点）也要更新为null；接着就是更新List的各属性。
E unlinkLast(Node<E> node) 断开传入尾结点的连接并返回该结点元素，移除该结点
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;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
} 看，思路同unlinkFirst(Node<E> node)，主要操作：更新结点信息！置空！方便GC回收！
2.删除List元素（根据下标）
E remove(int index)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
} 参数：下标
检查下标合法，不多说了，要删除就要先找到这个下标结点，Node<E> node(int index)取结点啊，这个方法上面说过！
（回顾一下：根据下标和List的size比较，决定从头还是尾开始遍历！）
Node<E> node(int index) {
// assert isElementIndex(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;
}
} 主要在于E unlink(Node<E> 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 = 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;
}
思路：得到结点元素，更新传入结点的指向关系，这个很好理解。此方法兼具删除头尾结点的功能，注意判断！
3.删除List元素（根据元素（对象object））
boolean remove(Object o)
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
源码给出的方法很好理解：判断参数是否为null，再分别从头至尾遍历，找出包含此元素的结点，用unlink(Node<E> x)删除之。
我们发现源码中还有一个boolean removeLastOccurrence(Object o)
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
} 同上，不过是逆向遍历，另！删除逆向找到的第一个元素立刻就返回了，达到删除最后一个参数元素的目的！
其他方法
clean() 清空List
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
} 从头开始遍历List，置空，以方便GC回收
E get(int index) 根据下标获取下标结点元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
} 无容置疑，一旦涉及下标，就要判断下标合法性，然后通过node(int index)得到下标结点，进而得到结点内的元素
E set(int index，E element) 根据下标获取并设置下标结点元素
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
} 当然，检查下标，通过node(int index)方法获得下标结点，进而得到其更改前元素，设置新元素，返回旧元素
另外，源码中还有，peek，push，pop等一系列简单的方法，就是基于上面链表的增加，和删除操作完成的。
迭代器
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
迭代器采用了以内部类方式实现了Iterator接口
lastReturned;
next;
nextIndex;
用以上三个来更新位置
expectedModCount = modCount;
前面好多方法都有modCount++的原因了 是一个标识，用来检查在使用迭代器的同时，LInkedList有没有被外面修改，如果在使用迭代器的时候对List进行修改，就会抛出异常
hasNext() 只需检查游标有没有到size，返回true或者false
如果仍有元素可以迭代或有多个元素，则返回 true。
next() 返回迭代的下一个元素。
remove() 从迭代器指向的 collection 中移除迭代器返回的最后一个元素，并将游标移动到此处，证明此处是有元素的，这也就 同时解释了没有用 == null判断了
checkForComodification() 用来检查在使用迭代器的同时，List有没有被外面修改的方法
迭代器的实现，不管实在ArrayList还是LinkedList中实现的思路都是一样的。我认为，其核心还是在于为保证安全对modCount的判断。
总结：
LinkedList是基于双向链表实现的
LinkedList也不是线程安全的
在增加，删除，查找，设置指定下标元素的时候，都要先判断以决定从头or从尾开始遍历
相比于ArrayList，LinkedList在增删方面更为出色，ArrayList则需要大量元素的移动，甚至list的复制和扩容，但在取方面，推荐ArrayList。这就是为什么LinkList中有堆栈的pop和push方法，而ArrayList没有了。可见，在Java源码中，堆栈和队列也是用LinkedList实现的。
