链表
- 由一系列节点组成的有序集合。
- 分为单向链表, 双向链表，循环链表
- 单向链表: 每一个节点都有一个指针指向下一个节点，最后一个节点的指针指向null
- 双向链表: 每一个节点都有两个指针(这里用p, n代表两个指针)，p指向前一个节点，n指向下一个节点。但第一个节点的p指向null, 最后一个节点的n指向null
- 循环链表: 每一个节点都有两个指针(这里用p, n代表两个指针), 第一个节点的p指向最后一个节点, 最后一个节点的n指向第一个节点。这样就形成了循环
java的LinkedList - 双向链表
这里以java的LinkedList的源码学习，不多说，先看源码
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;
}
}
上面代码定义了一个类，代表一个节点的实体类，里面有3个成员变量，next用于指向下一个节点，prev用于指向前一个节点，item则是该节点承载的元素。
接下来，看一下它的一些添加元素的方法
public boolean add(E e) {
linkLast(e);
return true;
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
添加元素主要有4个方法，
- add和addLast其实是同一方法，都是在后面添加一个元素，所有都调用了linkLast(e)；
- addFirst则调用linkFirst(e)；
- add(index, element)这个方法是把元素添加某个位置，先调用checkPositionIndex(index)检查index是否在[0，size]之间, 接着判断想添加到index是否等于size,
因为位置是0开始，如果index == size，直接调用linkLast()放到最后一个位置即可。否则调用linkBefore方法
继续看linkLast，linkFirst，linkBefore这三个方法 ....
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++;
}
这个方法目的是把元素放到最前面，first和last是两个Node<E>的成员变量，可以理解为用来记录第一个和最后一个的来临时变量。
先创建一个节点new Node<>(null, e, f)，要把元素放到最前面，此时newNode就是第一个节点，之前的第一个节点就成为newNode的下一个节点。
接着判断 f == null, 这里的f是指没添加之前的第一个节点，如果f为null, 那么当前添加就是第一个节点，也是最后一个节点，所以newNode赋值为last;
如果f不为null, 那么f的p指针就应该指向newNode。最后记录节点的变量+1。
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++;
}
linkLast方法目的是把元素放到最后面，思路跟linkFirst差不多， 临时变量l记录最后一个节点，然后创建一个新的节点，该节点p指向l, n指向null，
如果l为null, 没添加元素前为空集合，所以当前也是第一个节点，赋值为first;如果l不为null, 那么 l 的n应该指向新的节点。最后节点数+1.
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++;
}
linkBefore方法的目的是将元素e放到一个指定的节点之前。 succ是这个指定的节点。首先用临时变量pred记录succ的前一个节点,
接着创建一个新的节点，p指向pred, n指向succ, succ的p指针就指向这个新的节点newNode。如果pred 为null, succ的前一个节点为null,
那么newNode就是第一个节点;如果pred不为null, pred的n指针应该指向newNode。最后节点数+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);
}
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;
}
removeFirst, removeLast 分别调用unlinkFirst(f), unlinkLast(l);
看remove方法，遍历链表，从first开始, 找到和o相等的元素，调用unlink方法完成移除。
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;
}
f是第一个节点，f.item和f.next分别临时赋值给element和next，接着f.item和f.next都设为null,就意味着移除了第一个节点,
那么next这个节点就是第一节点了，赋值给first; 如果next为null, 那么last为null,说明现在链表整个为空啦;如果next不为null,将next的p指针指向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;
}
l是最后一个节点，l.item和l.prev分别临时赋值给element和prev,接着l.item和l.prev都设为null,就意味着移除了最后一个节点了,
那么prev这个节点就是最后一个节点了,赋值给last; 如果prev为null, 那么first也为null,说明现在链表整个为空啦;如果prev不为null,将prev的n指针指向null。
E unlink(Node<E> x) {
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;
}
移除某个节点： x.item， x.next, x.prev分别临时赋值给element, next和prev; 重新调整next 和prev节点,
如果prev为null, 那么next节点就是第一个节点;如果prev不为null, prev的n指向next, x的p设为null;
如果next为null, 那么prev节点就是最后一个节点; 如果next不为null, next的p指向prev, x的next设为null；
最后把x.item设为null,移除当前, size--代表节点数减1, modCount记录的是链表的操作次数，所以怎么都是加1。
到此， 双向链表的实现就基本完成啦。如果要实现循环链表，在双向链表的基础上，把第一个节点的p指向最后一个, 把最后一个节点的n指向第一个节点。
