1.1 认识链表
1.1.1 简介
链表这类数据结构，有点像生活中的火车，一节车厢连着下一节车厢，在火车里面，只有到了4号车厢你才能进入5号车厢，一般情况下，不可能直接在3号车厢绕过4号车厢进入5号车厢。不过更准确来说，火车是双向链表，也就是说在4号车厢也可以反向进入3号车厢。
下面我们来画个图看看链表这类数据结构到底长啥样子。
1.1.2 特性
每个链表中的节点都包含一个值，和指向下一个节点的指针。由此可以定义出节点的结构：
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
@Override
public String toString() {
return e.toString();
}
}
如果要创建一个链表，如上图1-1-1，我们只要知道一个起始的node节点即可。所以每个链表数据结构中，包含的就是一个起始node头节点。
1.2 链表插入元素
在一个如下的链表中，index为2的地方，插入节点15。步骤如下：
第一步，先找到index为1的node节点23；
第二步，然后把节点15的next指针指向节点10；
第三步，把节点23的next指针指向15；
注意点：这里需要先把15节点的next指向10，然后再把23节点的next指向15，顺序不能打乱，要不然就找不到23节点后面的链表啦。
其实链表这类数据结构，一般情况下，比较适应于头尾节点的操作，索引index的概念其实是不存在的，只是例子中为了方便表示我们插入的位置，才引入了一个index的概念。
1.2.1 虚拟头节点
聪明的你可能发现了，我们在添加元素时，都是先找到待添加位置的前一个位置，可是如果待添加位置的index为0呢？我们就得单独开设逻辑来进行判断。代码如下：
private Node head;
private int size;
public void add(E e, int index) {
if (index == 0) {
addFirst(e);
return;
}
Node preNode = head;
for (int i = 1; i < index; i++) {
preNode = preNode.next;
}
// 这三句话可以整理成一句话
// preNode.next = new Node(e, preNode.next);
Node node = new Node(e);
node.next = preNode.next;
preNode.next = node;
size++;
}
public void addFirst(E e) {
head = new Node(e, head);
size++;
}
这时，如果我们添加一个虚拟的头节点，就能统一所有的操作，使得逻辑看起来更加顺畅。
private Node dummyHead; // 虚拟头节点
private int size;
public LinkedList() {
dummyHead = new Node(null, null);
size = 0;
}
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("index is illegal");
}
// 虚拟头节点赋值给最开始的前一个节点
Node preNode = dummyHead;
// 找寻index前一个节点的索引
for (int i = 0; i < index; i++) {
preNode = preNode.next;
}
preNode.next = new Node(e, preNode.next);
// 这三句话可以整理成一句话
// Node node = new Node(e);
// node.next = preNode.next;
// preNode.next = node;
size++;
}
1.3 链表的遍历
链表的遍历操作意义很大，查询某个元素，修改某个元素等操作都会涉及到链表的遍历。以下就以链表是否包含一个元素来展示一下查询操作。
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
1.4 链表删除元素
第一步，找到待删除元素前一个元素，如下图的23；
第二步，把待删除元素前一个元素(23)的指针指向待删除元素（10）的后一个元素（35）。
第三步，把删除元素返回，删除元素的下一个元素指针置空，脱离链表。
实现代码如下：
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index is illegal");
}
Node preNode = dummyHead;
for (int i = 0; i < index; i++) {
preNode = preNode.next;
}
Node delNode = preNode.next;
preNode.next = delNode.next;
delNode.next = null;
size--;
return delNode.e;
}
1.5 链表实现栈
链表在插入与删除元素时，如果只是对头节点进行操作，那么时间复杂度都是O(1)级别的。因为不存在寻址过程。所以用它来实现栈这种数据结构最合适不过了。
1.6 一些拓展
双向链表，每个node节点都有一个前指针和后指针，一般这种情况下，还会增加一个虚拟的尾节点用做尾指针，增加了寻址的速度。
循环双向链表，可以少维护一个尾指针，向头部添加元素就是在虚拟头节点前增加元素，向尾部添加元素就是在虚拟头节点后插入元素。
1.7 leetcode上练习
leetcode中有许多题目，以下对一些常见的操作进行实现。看看具体实现的思路是什么。
1.7.1 链表反转
最开始，想出来的是以下这一种方法：在遍历链表的过程中，不断new出新的node节点。然后把后遍历的元素添加到链表头位置。代码如下：
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode result = new ListNode(head.val);
ListNode curr = head;
while (curr.next != null) {
ListNode next = new ListNode(curr.next.val);
next.next = result;
result = next;
curr = curr.next;
}
return result;
}
如上代码具体的图文解析如下，假如传进来的链表为3，5，7，8：
这种方式虽然可以完成反转，但在反转的过程中会不断的new出新的节点，有点浪费空间。于是乎就在想，是否可以就利用原来的节点制造出新的链表，但是指针在这种情况下就得先走一步，要不然后续节点就会找不到。于是就产生了以下代码：
public ListNode reverseList3(ListNode head) {
if (head == null) {
return null;
}
ListNode result = new ListNode(head.val);
ListNode cur = head.next;
while (cur != null) {
// 记录住每次循环时当前的指针
ListNode current = cur;
// 指针先行
cur = cur.next;
current.next = result;
result = current;
}
return result;
}
最后还有一种递归的方式来反转链表，关于递归，以后有机会单独写一篇文章来进行总结。利用递归来解决问题，思路是把当前问题拆分成更小的可重复的问题，最终，当问题规模小到一定程度时，可以自然求得答案（如下面当链表的下一个节点next为空时，反转链表就是本身）。
private ListNode reverse(ListNode head){
// 递归到底的退出条件
if (head.next == null) {
return head;
}
// 不能用newHead的next指向当前节点，因为newHead始终没有动
ListNode newHead = reverse(head.next);
head.next.next = head;//链表循环
head.next = null;
return newHead;
}
以3，7，8为例，当循环到底后，return head;返回的就是节点8。此时进入上次递归函数体内，链表的示意图如下：
经过这句代码
head.next.next = head;
将变成如下图显示，节点8指向了节点7，构成了一个循环列表了。
然后在经过这句代码：
head.next = null;
就变成如下这个样子了：
到此，完成了一次递归操作，我们来看看这个例子中更小规模的问题是：两个节点进行了一次指针指向的调换，就是反转。
接下来的逻辑，就是重复以上过程，整个过程如下图：
所以最终就是：节点还是那个节点，只是由我爱(指向)你变成了你爱(指向)我啦啦啦～，还是双向链表好，你有我时我也有你。咳咳～～，我们言归正传，哈哈～～。
1.7.2 寻找中间节点
寻找链表中的中间节点，这个问题，最开始肯定能够想到的就是遍历一下链表的长度，然后，根据长度找到中间节点。
但是如果仅仅是这样，肯定是会被鄙视的，在leetcode上看到了一个快慢指针的方式找寻中间节点的方法，感觉很是巧妙。
看看我们如何来理解快慢指针的：把链表看作一条赛道，运动员A速度是运动员B的两倍，当运动员A跑完全程，运动员B就刚刚好跑了一半。
我们要做的代码如下，fast的next指针为空或者fast的next的next指针为空，则退出寻址循环。
slow = slow.next
fast = fast.next.next
完美找到中点，这种方式真是优雅而又巧妙，遍历次数减少到了n／2次。
1.8 题外话
链表这种数据结构是一种动态的数据结构，节点node就是一个信息存放点，双向链表也就是一个节点中除了存放后指针，还会存放前指针，存放信息更多，那么就会拓展链表的功能。但是同样的就会增加维护的成本，额外的内存开销。
由此引申到生活，数据结构和人一样，有所长必有所短。这个世界是公平的，人和事都没有所谓的完美之说，少追求完美主义，多接受自身的不足点，看到自身闪光点，也许才是快乐生活的源泉。
