一、链表
1.1. 链表的概念及结构
链表是一种物理存储结构上非连续的线性表，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。形象地说，就像火车头、车厢与每一节车厢之间由车钩连接起来。在物理内存上，节点不一定连续，但在逻辑上一定是连续的。
如下图所示，链表的结构通常分为两个域：一个域用来储存数据，另一个域用来储存下一个节点的地址（类似于指向下一节车厢）。与顺序表不同的是，链表的地址在物理上不连续，但在逻辑上是连续的。最后一个节点相当于'车尾'，里面存的地址为 null。这就是一个单向、不带头、非循环的链表。类似地，还有双向、带头、循环的链表。但考试和面试中考察最多的通常是单链表。
什么是带头的链表？ 第一个节点可以存任何数据，但存取的数据是没有意义的，唯一的作用就是起到一个'排头兵'的作用，方便统一操作。
什么是不带头的链表？
相当于它的 head 指针会变。比如我们把第一个节点删掉，那么第二个节点就会成为新的 head。
什么是循环链表？ 最后一个节点指向了第一个节点或第二个节点，就可以构成循环链表，一般情况下都是指向第一个节点。
1.2. 链表的实现
接下来我们通过代码来实现链表。我们可以定义一个 MySingleList 类，基于面向对象的思想，使用内部类来定义我们的节点。
public class MySingleList {
static class ListNode {
private int val;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
// 因为不知道下一个节点是谁，所以这里的构造函数的参数里不写 next
}
public ListNode head; // 表示当前链表的头节点
public int listSize; // 记录链表长度
}
链表的基础结构已经搭好，下面要实现增、删、查、改。我们可以把这些方法封装在一个接口里面，然后在 MySingleList 类中对这些方法进行重写。
public interface Ilist {
// 头插法
void addFirst(int data);
// 尾插法
void addLast(int data);
// 任意位置插入，第 0 号下标为第一个数据节点
void addIndex(int index, int data);
// 查找是否包含关键字 key
boolean contains(int key);
// 删除所有值为 key 的节点
void remove(int key);
// 得到单链表的长度
int size();
// 清空链表
void clear();
// 打印链表
void display();
}
public class MySingleList implements Ilist {
static class ListNode {
private int val;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public int listSize;
@Override
public void addFirst(int data) {}
@Override
public void addLast(int data) {}
@Override
public void addIndex(int index, int data) {}
@Override
public boolean contains(int key) { return false; }
@Override
public void remove(int key) {}
@Override
public int size() { return 0; }
@Override
public void clear() {}
@Override
public void display() {}
}
我们也可以手动创建一个链表来测试：
public void CreateList() {
ListNode node1 = new ListNode(11);
ListNode node2 = new ListNode(22);
ListNode node3 = new ListNode(33);
ListNode node4 = new ListNode(44);
// 这些数据之间没有连续性
node1.next = node2;
node2.next = node3;
node3.next = node4;
// node4 已经是最后一个节点了，不需要管最后一个 next
this.head = node1; // 这样可以从第一个节点开始去遍历
}
我们在对象实例化这里打一个断点来进行调试。开始的时候，头节点是空的，运行到下一行时，我们的 val 的值和 next 的地址都被 CreateList 方法串联起来了。
了解了 next 的引用原理之后，我们就可以遍历链表来对里面的数据进行打印。我们通过上面的 display 方法来实现，那如何通过 head 的引用从第一个节点指向第二个节点呢？
// 基本变量通过自增的方式来赋值
int a = 10;
a = a + 1;
// 同理，引用变量也可以采用上述方法
head = head.next;
@Override
public void display() {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
我们来对这个方法进行调试一下。当 head 不为空时，进入 while 循环，当 head.next 指向第二个节点时 val 的值变为了 22，next 的地址也指向了第二个节点。当 head 指向最后一个节点时，地址变为 null，跳出 while 循环。
但这种写法也有致命的缺点：如果说这个方法有返回值呢？head 遍历完我们的链表之后，head 引用变为了 null，返回的值也会成 null。如果我们再用 ListCode 创建一个 cur 变量，把 head 的引用赋值给 cur，再让 cur 去遍历链表，就能保持 head 不动。
比如我们通过 size 方法来获取链表的节点数，就可以这样写：
@Override
public int size() {
ListNode cur = head;
int count = 0;
while (cur != null) {
cur = cur.next;
count++;
}
return count;
}
再比如我们去写 contains 方法去判断链表里是否存在关键字：
@Override
public boolean contains(int key) {
ListNode cur1 = head;
while (cur1 != null) {
if (cur1.val == key) {
return true;
}
cur1 = cur1.next;
}
return false;
}
System.out.println(mySingleList.contains(44));
System.out.println(mySingleList.contains(45));
可能有的朋友在写这个方法会写出 cur1.next != null，因为最后一个节点的 next 为 null，当 cur1 走到最后节点时，不满足 cur1.next != null，相当于根本没有遍历完这个链表。
下面我们将要对链表里的数据进行增删查改。我们先来实现头插和尾插。
1.2.1 头插法
我们如果要把一个 node 节点（里面存的数据是 10）插入 head 节点前面之后，node 节点就变成了 head 节点。我们可以通过下面两行代码来实现这个过程。这里千万不能把两行代码写反，否则就会使得 node.next 指向自己，造成死循环。
node.next = head; // 先让 node.next 的地址指向原来的 head
head = node; // 再通过 head 引用指向 node，就能把 node 变成头节点
@Override
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node; // 相当于插入进一个空的链表
} else {
node.next = head;
head = node;
}
listSize++; // 记得更新长度
}
1.2.2 尾插法
对于尾插的实现，与头插不同的是，我们需要先找出链表的最后一个节点，然后再让 cur.next = node。如果说初始的链表是空的情况下，则 cur 为 null，直接访问 cur.next 就会出现空指针异常。我们就需要参考 contains 方法来寻找链表的尾部。
@Override
public void addLast(int data) {
ListNode node = new ListNode(data);
// 表示链表为空
if (head == null) {
head = node;
return;
}
// 找到链表的尾巴
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
listSize++;
}
1.2.3 任意位置插入
为了方便理解，我们给每个节点都编上号。如果说我们要把新的节点插入到 2 号位置，那么新的节点就会变成 2 号位置。但我们的 cur 是不能走两步的，因为插入之后 2 号位置不知道前面的节点是谁，这个链表是单向的，所以 cur 不能往回走，也就是要走 index-1 步。
node.next = cur.next;
cur.next = node;
对于 cur 需要走 index-1 步的过程，我们可以重新写一个方法来实现。然后我们就可以把新节点插入到链表中了。
private ListNode findIndex(int index) {
ListNode cur = head;
int count = 0;
while (count != index - 1) {
cur = cur.next;
count++;
}
return cur;
}
public void addIndex(int index, int data) {
ListNode node = new ListNode(data);
ListNode cur = findIndex(index);
node.next = cur.next;
cur.next = node;
listSize++;
}
过程确实有点复杂，不懂的朋友可以去画图辅助理解。到这里，看似我们的过程已经结束了，但我们需要考虑其他的一些问题。
如果我们在 0 号位置插或者在 size() 位置插，那么就相当于头插和尾插了，我们可以直接调用 addFirst 和 addLast 方法。那如果我们在 -1、-2 位置插呢？这时就会越界访问。我们就需要写一个方法来检查访问是否合法。
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
private void checkIndexOfAdd(int index) {
if (index < 0 || index > size()) {
throw new RuntimeException("插入的位置不合法，index=" + index);
}
}
1.2.4 删除元素
删除并不是简单的跳过这个节点，还要把要删除的节点前一个和后一个连接起来。那我们先找到要删除元素的前一个元素，我们又该如何找到要删除的节点呢？
cur.next = del.next;
private ListNode findNode(int key) {
ListNode cur = head;
while (cur.next != null) {
if (cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
通过上面这个方法，我们就可以找到我们要删除的节点。注意，我们不能写成 cur != null，因为 cur.next 就会空指针异常。如果我们没有找到，就返回 null。
但是，我们需要考虑一下，我们要删除第一个数据，cur 已经在第一个节点，那么 cur.next 就不会对第一个节点进行判断，从而就不会删除。所以需要单独处理头节点的情况。
@Override
public void remove(int key) {
if (head == null) {
return;
}
// 如果要删除的是头节点
if (head.val == key) {
head = head.next;
listSize--;
return;
}
ListNode cur = findNode(key);
if (cur == null) {
System.out.println("没有你要删除的数据");
return;
}
ListNode del = cur.next;
cur.next = del.next;
listSize--;
}