概念
链表的插入，只需要上一个节点的指针指向这个新增的节点，新增的节点指向下一个节点。
删除类似操作。
链表当前节点只知道下个节点是谁，也并非连续存储，随机访问元素时需要将整个链表遍历来查找元素。
添加和删除时间复杂度：O(1)，随机查询时间复杂度：O(n)
单链表
单链表有头结点和尾结点。头结点用来记录链表的基地址，尾结点指向空地址null。
循环链表
跟单链表的区别就在于尾结点，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。
当要处理的数据具有环型结构特点时，就特别适合采用循环链表。
双向链表
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。
跳表
思路：升维思想，空间换时间
如果要插入一个值是4的新节点，就不用8，7，6，5，3这样的查询.可以7，5，3这样的查询。
这是一层节点，还可以继续扩充成多层节点，提取的极限就是同一层就有两个节点的时候。
这种方式随机访问的时间复杂度降到了O(logn)
空间复杂度O(n)
链表的优缺点
优点：
链表本身没有大小的限制，天然地支持动态扩容。
缺点：
链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。
对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，有可能会导致频繁的 GC。
链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。
不同链表比较
链表删除
- 删除结点中“值等于某个给定值”的结点；
- 删除给定指针指向的结点。
虽然单纯的删除时间复杂度是O(1)，但是要查找删除的元素是个比较麻烦的问题，链表的随机访问元素时间复杂度是O(n)。
第一种情况，需要从头开始遍历链表来找到值等于给定值的结点。
第二种情况，我们已经找到了要删除的结点，但是删除某个结点q需要知道其前驱结点，进行尾结点指向改变来控制删除操作。这种情况单链表不知道前驱节点，查询时间复杂度是O(n)，而对于双向链表时间复杂度是O(1)。
插入也是一致。
有序列表的查询
对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置p，每次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
如何选取用单向链表还是双向链表
当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
使用缓存就是空间换时间的设计思想。
如何写链表代码
理解指针或引用的含义
p->next=q。这行代码是说，p结点中的next指针存储了q结点的内存地址。
p->next=p->next->next。这行代码表示，p结点的next指针存储了p结点的下下一个结点的内存地址。
防止指针丢失的情况
指针p指向节点A，需求想要在节点A，B中插入节点X。
p->next = x; // 将p的next指针指向x结点；
x->next = p->next; // 将x的结点的next指针指向b结点；
这种写法是错误的，因为第一行代码，P节点下一个节点位置已经指向到x，不再指向B了。所以第二行变成了X节点指向了自己，链表从此断了。
正确写法是1和2颠倒过来，先把x的下一个节点指向B，再把A的下一个节点指向x。
如果是删除，注意C的话要释放内存，防止内存泄漏。
特殊节点的添加和删除
1.正常节点的添加
// 新建的节点尾节点指向p的下一个节点
new_node->next = p->next;
// p的尾节点指向新节点
p->next = new_node;
2.添加头节点
if (head == null) {
head = new_node;
}
3.正常节点的删除
p->next = p->next->next;
4.删除最后一个节点
if (head->next == null) {
head = null;
}
这种方式很容易出错，需要引入哨兵节点，在任何时候，不管链表是不是空，head指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。哨兵结点是不存储数据的。
// 在数组a中，查找key，返回key所在的位置
// 其中，n表示数组a的长度
// 我举2个例子，你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6} n=6 key = 7
// a = {4, 2, 3, 5, 9, 6} n=6 key = 6
int find(char* a, int n, char key) {
if(a == null || n <= 0) {
return -1;
}
// 这里因为要将a[n-1]的值替换成key，所以要特殊处理这个值
if (a[n-1] == key) {
return n-1;
}
// 把a[n-1]的值临时保存在变量tmp中，以便之后恢复。tmp=6。
// 之所以这样做的目的是：希望find()代码不要改变a数组中的内容
char tmp = a[n-1];
// 把key的值放到a[n-1]中，此时a = {4, 2, 3, 5, 9, 7}
a[n-1] = key;
int i = 0;
// while 循环比起代码一，少了i<n这个比较操作
while (a[i] != key) {
++i;
}
// 恢复a[n-1]原来的值,此时a= {4, 2, 3, 5, 9, 6}
a[n-1] = tmp;
if (i == n-1) {
// 如果i == n-1说明，在0...n-2之间都没有key，所以返回-1
return -1;
} else {
// 否则，返回i，就是等于key值的元素的下标
return i;
}
}
重点留意边界条件处理
如果链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？
如果链表只包含两个结点时，代码是否能正常工作？
代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
LinkedList源码
底层数据结构双向链表。链表中的元素是Node。
private static class Node<E> {
E item;
LinkedList.Node<E> next;
LinkedList.Node<E> prev;
Node(LinkedList.Node<E> var1, E var2, LinkedList.Node<E> var3) {
this.item = var2;
this.next = var3;
this.prev = var1;
}
}
增加
可以从头部增加，也可以从尾部增加。默认add从尾部增加。
1.从头部增加节点
private void linkFirst(E var1) {
LinkedList.Node var2 = this.first;
// 创建的节点，前一个是null，当前节点是var1，尾节点是var2
LinkedList.Node var3 = new LinkedList.Node((LinkedList.Node)null, var1, var2);
// 新建的节点作为头节点
this.first = var3;
// 如果之前没有头节点，意味着之前链表为空，当前添加元素，头节点，尾节点都是同一个节点
if (var2 == null) {
this.last = var3;
} else {
var2.prev = var3;
}
++this.size;
++this.modCount;
}
2.从尾部增加节点
void linkLast(E var1) {
LinkedList.Node var2 = this.last;
// 当前节点上一个节点是之前链表的尾节点，下一个节点是null
LinkedList.Node var3 = new LinkedList.Node(var2, var1, (LinkedList.Node)null);
this.last = var3;
if (var2 == null) {
this.first = var3;
} else {
var2.next = var3;
}
++this.size;
++this.modCount;
}
删除
可以选择从头部删除，也可以选择从尾部删除，给定index删除节点，删除给定节点。删除操作会把节点的值，前后指向节点都置为null，帮助GC进行回收。
remove(Object o)
添加没有特殊判断，可以添加null，删除也可以删除null。
从头节点向尾节点遍历，删除null，判断节点数据是否为null。
删除其余元素，通过equals判断值是否相同。
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;
}
remove(int index)
需要找到这个index对应的节点信息，通过上面的删除方式删除节点。
Node<E> node(int index) {
// 二分
if (index < (size >> 1)) {
// 获取到头节点，根据index一直向下获取
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 获取到尾节点根据index向上获取
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
remove()
相当于删除链表头节点元素
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
// 头节点的下个节点头指针指向null，它要成为头节点
next.prev = null;
size--;
modCount++;
return element;
}
迭代器
从头到尾方式迭代。
hashNext方法
public boolean hasNext() {
// 下一个节点的索引小于链表的大小
return this.nextIndex < LinkedList.this.size;
}
next方法
public E next() {
this.checkForComodification();
if (!this.hasNext()) {
throw new NoSuchElementException();
} else {
// 当前要删除的节点
this.lastReturned = this.next;
// next是下一个节点了，为下次迭代做准备
this.next = this.next.next;
++this.nextIndex;
return this.lastReturned.item;
}
}
remove方法
public void remove() {
this.checkForComodification();
if (this.lastReturned == null) {
throw new IllegalStateException();
} else {
LinkedList.Node var1 = this.lastReturned.next;
// 删除当前节点
LinkedList.this.unlink(this.lastReturned);
if (this.next == this.lastReturned) {
this.next = var1;
} else {
--this.nextIndex;
}
this.lastReturned = null;
++this.expectedModCount;
}
}
