前言
底层基础决定上层发展。
点个赞在看，让我知道你在关注技术。
本系列文章Github 后端进阶指南 已收录，此项目正在完善中，欢迎star。
本系列内容预览：
1. 什么是链表？
链表也是
线性表中的一种，数组是线性表中的顺序结构，而这次说的链表是线性表的链式存储结构，它在内存中是非连续、非顺序性的数据结构，由若干个节点组成。它每个节点中都会存储数据和下一个节点的地址，存储数据的叫做数据域，存储地址的叫做指针域。指针分为前驱指针、后继指针，分别用来记录前一个节点和后一个节点的位置。指针：将某个变量赋值给指针，实际上就是将变量的地址值赋值给指针，可以看做Java当中的引用。
1.1 单向链表
单向链表，顾名思义就是只有一个方向的链表，从上图中来看，一个单向链表由若干个节点组成，每个节点又分为两个部分，一部分存放数据，一部分存放下一个节点的位置。用图来说话就是橘色的方块叫做数据域，里面用来存放数据data。而黄色的方块叫做指针域，用来存放下一个节点的位置next（注意是下一个节点的位置，不是下一个指针的位置），这个next又被称为后继指针。
大家观察上面的图，有两个地方比较特殊，那就是第一个节点和最后一个节点。我们还可以称作头结点、尾结点。这两个节点有什么特别之处呢？那就是头结点可以不存数据，作为链表的开始，而尾结点的后继指针指向null，代表这是链表的最后一个节点。
头节点：链表中第一个节点，头节点中可以不存储数据。
头指针：链表中第一个节点的指针，用来存储链表的基地址，是整个链表的开始。
尾节点：链表中最后一个节点，指向一个空null，代表这是链表的最后一个节点。
1.2 单向循环链表
单向循环链表是从单向链表衍生出来的，它和单向链表的唯一区别就是单向链表的尾结点的后继指针指向了null，而单向循环链表的尾结点后继指针指向了头节点。这种首尾相连的单链表称单向循环链表。循环链表的优点就是从链尾到链头比较方便，处理环形结构问题时比较适用，比如著名的约瑟夫问题。
1.3 双向链表
双向链表稍微复杂一些，它和单向链表相比除了后继指针以外还多了个前驱指针。如果存储同样多的数据，双向链表比单向链表占用更多的空间，虽然双向链表中的两个指针很浪费空间，但可以支持双向遍历，也给链表本身带来了更多的灵活性。
1.4 双向循环链表
了解了循环链表和双向链表之后，把这两个组合在一起就是双向循环链表，大家看图就知道了，头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点。这里就不做过多介绍了，大家知道链表都有哪几种就可以了。
2. 链表VS数组
说了半天链表，不知道大家了解了没有，我自己都感觉很枯燥。可是基础就是这样，只有学好了基础才能更好的向上爬。现在我们来看下链表和我们之前讲的数组有什么区别。首先它们两个的存储结构就不一样，数组是顺序存储结构，也就是说它在内存中是一块连续的存储空间，而链表是链式存储结构，也就是非连续的。我们来看下它们在内存中表现：
通过图片，相信大家已经看出来区别了，由于数组是连续的存储结构，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。由于数据结构的不同，导致数组和链表的插入、删除、随机访问等操作的时间复杂度正好相反。
| 数组 | 链表 | |
|---|---|---|
| 插入、删除 | O(n) |
O(1) |
| 随机访问 | O(1) |
O(n) |
链表天然的支持动态扩容，因为它不是预先生成内存空间，只有真正使用的时候才会去开辟一块内存空间。而数组就不行，数组的缺点就是大小固定，申请多了浪费，申请少了还得频繁的扩容、搬移数组，如果数据量大了很耗时。所以大家在使用List的时候也是，如果能够事先预估数据量的大小，那么在初始化的时候最好指定下大小，避免扩容时搬移数据带来影响。
3. 链表的基本操作
3.1 链表的增加
链表的增加操作，一共有三种情况：
增加到头部
增加到头部一共分为两步，第一步将新节点的后继指针指向原头节点，第二步是将新节点变为头节点。这样就完成了头部添加。
增加到中间
中间插入也分为两步，第一步将插入位置的前边节点的后继指针指向新节点，第二步是将新节点后继指针指向插入位置的原节点。
增加到尾部
链表的尾部插入最简单，只需要将最后一个节点的后继指针指向新节点就可以了。
我们来看下代码，如果大家时间充沛，建议自己手动敲一遍，这样会理解的更深刻。
/**
* @author: lixiaoshuang
* @create: 2019-12-08 23:11
**/
public class LinkedListAddDemo {
//头节点
private static Node headNode = null;
//尾节点
private static Node lastNode = null;
//链表的长度
private static int size;
public static void main(String[] args) {
//初始化一个链表
addByIndex(1, 0);
addByIndex(2, 1);
addByIndex(3, 2);
addByIndex(4, 3);
//头部插入
addByIndex(5, 0);
printNode(); //输出 5、1、2、3、4
//中间插入
addByIndex(5, 2);
printNode(); //输出 1、2、5、3、4
//尾部插入
addByIndex(5, 4);
printNode(); //输出 1、2、3、4、5
}
private static void addByIndex(int data, int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node node = new Node(data);
if (index == 0) {
//插入到头部
node.setNext(headNode);
headNode = node;
if (size == 0) {
lastNode = node;
}
} else if (index == size) {
//插入到尾部
lastNode.setNext(node);
lastNode = node;
} else {
//插入到中间
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext();
prevNode.setNext(node);
node.setNext(nextNode);
}
size++;
}
/**
* 通过位置查找链表节点
*
* @param index
* @return
*/
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
/**
* 打印节点
*/
private static void printNode() {
while (headNode != null) {
System.out.println(headNode.getDate());
headNode = headNode.getNext();
}
}
}
/**
* 定义一个节点
*
* @param <T>
*/
class Node<T> {
/**
* 节点中的数据
*/
private T date;
/**
* 下一个节点的指针
*/
private Node next;
public Node(T date) {
this.date = date;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public T getDate() {
return date;
}
public void setDate(T date) {
this.date = date;
}
}
3.2 链表的删除
链表删除和增加一样，也有三种情况：
删除头部
删除头部操作只需要将头部节点设置为当前头部节点的下一个节点就可以了。
删除中间
删除中间操作只需要将被删除节点的前一个节点的后继指针指向被删除节点的下一个节点就可以了。
删除尾部
尾部删除只需要将倒数第二个节点的后继指针指向null就可以。
/**
* @author: lixiaoshuang
* @create: 2019-12-08 23:11
**/
public class LinkedListAddDemo {
//头节点
private static Node headNode = null;
//尾节点
private static Node lastNode = null;
//链表的长度
private static int size;
public static void main(String[] args) {
//初始化一个链表
addByIndex(1, 0);
addByIndex(2, 1);
addByIndex(3, 2);
addByIndex(4, 3);
//头部删除
delete(0);
printNode(); //输出 2、3、4
//尾部删除
delete(3);
printNode(); //输出 1、2、3
//中间删除
delete(2);
printNode(); //输出 1、2、4
}
/**
* 链表删除操作
*
* @param index
*/
private static void delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
if (index == 0) {
//删除头部
headNode = headNode.getNext();
} else if (index == size - 1) {
//删除尾部
Node prevNode = get(index - 1);
prevNode.setNext(null);
lastNode = prevNode;
} else {
//删除中间
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext().getNext();
prevNode.setNext(nextNode);
}
size--;
}
/**
* 通过位置查找链表节点
*
* @param index
* @return
*/
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
/**
* 打印节点
*/
private static void printNode() {
while (headNode != null) {
System.out.println(headNode.getDate());
headNode = headNode.getNext();
}
}
}
3.3 链表的修改
修改链表节点就直接将要修改的节点替换为新节点，第一步先将被修改的节点的前一个节点的后继指针指向新节点，然后将新节点的后继指针指向被修改节点的下一个节点，这里讲的是如何修改一个节点，逻辑和上边的增加删除差不多，这里就举一个中间修改的图例吧。如果想不替换节点修改节点中的数据，这个比较简单，大家可以自己实现下。
/**
* @author: lixiaoshuang
* @create: 2019-12-08 23:11
**/
public class LinkedListOperationDemo {
//头节点
private static Node headNode = null;
//尾节点
private static Node lastNode = null;
//链表的长度
private static int size;
public static void main(String[] args) {
//初始化一个链表
addByIndex(1, 0);
addByIndex(2, 1);
addByIndex(3, 2);
addByIndex(4, 3);
//修改头部
update(5, 0);
printNode(); //输出 5、2、3、4
//修改尾部
update(5, 3);
printNode(); //输出 1、2、3、5
//修改中间
update(5, 1);
printNode(); //输出 1、5、3、4
}
/**
* 链表的修改
*
* @param data
* @param index
*/
private static void update(int data, int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node newNode = new Node(data);
if (index == 0) {
//修改头部
Node next = headNode.getNext();
newNode.setNext(next);
headNode = newNode;
} else if (index == size) {
//修改尾部
Node prevNode = get(index - 1);
prevNode.setNext(newNode);
lastNode = newNode;
} else {
//修改中间
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext().getNext();
prevNode.setNext(newNode);
newNode.setNext(nextNode);
}
}
/**
* 通过位置查找链表节点
*
* @param index
* @return
*/
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
/**
* 打印节点
*/
private static void printNode() {
while (headNode != null) {
System.out.println(headNode.getDate());
headNode = headNode.getNext();
}
}
}
3.4 链表的查询
说道查询，不知道大家发现没有，上边的代码中已经有过实现了😭,这里在贴过来，大家看下:
/**
* 通过位置查找链表节点
*
* @param index
* @return
*/
private static Node get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node temp = headNode;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
4. 面试题
4.1 怎么判断一个单向链表是否有环？
我们这里采用快慢指针的方法来判断一个链表是否有环，首先创建两个指针同时指向链表的头节点，慢指针走一步，快指针走两步，判断两个指针是否相等，如果相等，则说明有环。这里就是我们上边介绍的单向环形链表了。只要这个链表有环，那么利用快慢指针遍历它，两个指针肯定会有相等的时候（这里的指针是指节点）。这就好比周末公园里跑步一样，年轻人跑的快一些，老年人跑的慢一些，年轻人就会在某一个地方追赶上老人并超越他，原因很简单，因为公园的跑道是环形，哈哈。
大家看下面的代码我把链表插入操作中的尾部插入做了一个小修改，就是让每一个尾部节点的后继都指向头节点，这样就把单向链表变成了单向循环链表。
/**
* @author: lixiaoshuang
* @create: 2019-12-08 23:11
**/
public class LinkedListOperationDemo {
//头节点
private static Node headNode = null;
//尾节点
private static Node lastNode = null;
//链表的长度
private static int size;
public static void main(String[] args) {
//初始化一个链表
addByIndex(1, 0);
addByIndex(2, 1);
addByIndex(3, 2);
addByIndex(4, 3);
//判断链表是否有环
boolean ringed = isRinged();
System.out.println(ringed); //输出为true
}
/**
* 判断链表是否有环
*
* @return
*/
private static boolean isRinged() {
if (headNode == null) {
return false;
}
//定义快慢指针
Node slowPointer, fastPointer;
slowPointer = fastPointer = headNode;
while (slowPointer != null && fastPointer != null) {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext().getNext();
//如果两个指针有相等则有环
if (slowPointer == fastPointer) {
return true;
}
}
return false;
}
/**
* 链表插入操作
*
* @param data
* @param index
*/
private static void addByIndex(int data, int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node node = new Node(data);
if (index == 0) {
//插入到头部
node.setNext(headNode);
headNode = node;
if (size == 0) {
lastNode = node;
}
} else if (index == size) {
//插入到尾部
lastNode.setNext(node);
lastNode = node;
node.setNext(headNode); //这里尾部插入将最后一个节点的后继指向头节点，这样链表就是循环链表了。
} else {
//插入到中间
Node prevNode = get(index - 1);
Node nextNode = prevNode.getNext();
prevNode.setNext(node);
node.setNext(nextNode);
}
size++;
}
}
4.2 如何实现链表的反转？
这个也是一个高频面试题，这里我就不写实现方式了，当给大家留个思考题，有时间的朋友可以尝试自己解一下，这道题虽然百度下解题方法就出来了，但还是希望大家先自己思考下，如果实在想不出来在查找一下解题方法。也可以去《手撕数据结构与算法》中查看源码，我已经手敲了一遍。
5. 参考
《漫画算法》
《数据结构与算法之美》
《大话数据结构》
6.结尾
在我看来后端程序员应该学的有三大基础知识"数据结构与算法"、"计算机系统"、"操作系统Linux"。在这个互联网寒冬时代，是不是我们的衣服穿得不够多？彻夜难眠的我（纯属扯淡，哈哈）决定带领大家一起学习三大基础知识，本次开篇系列是《手撕数据结构与算法》，每一个系列更完就会开启下一个系列，大家不要着急。可以关注我的公众号，持续追更、持续学习。
本系列文章Github 后端进阶指南 已收录，此项目正在完善中，欢迎star。
公众号内文章都是博主原创，并且会一直更新。如果你想见证或和博主一起成长，欢迎关注！
欢迎扫码关注哦！！！
最后 最后，能够看到这里的朋友，都是有这乐于学习的精神，谢谢你们能够看完我写的文章，博主不太会总结，有什么问题欢迎留言指正，如果感觉读了以后有点收获 点赞、点关注 。写作路上需要各位老铁的支持，你们的支持就是下一篇得动力。
