大家好，我是王有志，欢迎和我聊技术，聊漂泊在外的生活。快来加入我们的Java提桶跑路群：共同富裕的Java人。
今天我们一起学习线性表中的第二种数据结构：链表，也是真正意义上的第一个动态数据结构。
今天的内容分为3个部分：认识链表，链表的形式和单向链表的实现。
什么是链表
在数据结构：线性表入门中，我们知道数组使用连续的内存，可如果程序已经运行了很久，内存中没有足够的连续内存，这时需要一个线性表结构，除了使用360安全卫士清理内存外，该怎么办呢？
早在1955年就有人想到了这个问题，从而诞生了一种影响深远的数据结构-链表。
链表开发于1955-56，由当时所属于兰德公司（英语：RAND Corporation）的艾伦纽维尔（Allen Newell），克里夫肖（Cliff Shaw）和赫伯特西蒙（Herbert Simon）在他们编写的信息处理语言（IPL）中做为原始数据类型所编写。IPL被作者们用来开发几种早期的人工智能程序，包括逻辑推理机，通用问题解算器和一个计算机象棋程序。
以上来源于维基百科的链表。在预备知识：概念和存储结构中，我们讲到链式存储结构，链表正是这样一种结构：
可以看到，链表使用分散在内存各个角落的内存块，通过“一根线”将内存块”串“起来。
得益于链式存储结构，我们可以很容易的为链表动态扩缩容，通常我们会称这种为动态数据结构，而像数组那样顺序存储的数据结构称为静态数据结构。
链表的概念
链表中，如果每块内存只存储数据元素的话，内存之间就无法形成线性结构。
为了使链表“串起来”，除了存储数据元素外，还需要存储直接后继节点的内存地址，通过“无形的线”将内存块“串”起来。
我们将存储后继节点内存地址的变量称为指针（即图中next）；存储着数据元素和指针的组合称为链表的节点；链表中第一个节点称为头节点，最后一个节点称为尾节点。
可能很多小伙伴听到指针就头疼，从C语言就开始折磨，好不容易到了Java，Python中没有了指针，可学个数据结构还要遭受指针的折磨。
其实指针的概念很简单，指针实际上是一个变量，存储的是某个对象的内存地址。
链表的特点
对于链表来说，插入和删除很简单，因为不需要使用连续的内存，所以也不需要在插入和删除后“整理”内存，得益于这种链式的存储结构，链表具有时间复杂度为$O(1)$的插入和删除操作。
插入和删除
如图，我们在节点B和D之间插入节点C，只需要2步操作即可：
节点C的指针指向节点D
节点B的指针指向节点C
删除操作也是类似的：
如果要删除节点C，需要3步操作：
存储节点D
删除节点C的指针
节点B指向节点D
可以看到，链表的插入和删除操作仅需要有限的操作步骤即可完成，在这个意义上时间复杂度为$O(1)$。
查询操作
对于链表来说，因为不具备顺序存储结构的特点，无法通过简单的计算查找到指定下标的数据元素，我们只能从链表的头节点出发，依次向后查询，直到查询到需要的数据元素位置。
这种情况下，链表查询操作的时间复杂度为$O(n)$。
链表的形式
到目前为止，我们对链表有了一定的认识，接下来我们来看看都有哪些常用链表的实现。
单向链表
单向链表是最简单的链表，也是我们在学习链表的概念中使用到的形式。
特点是，每个节点中只存储数据元素和指向直接后继节点的指针。下面会和大家实现一个简单的单向链表。
双向链表
双向链表是单向链表的升级版，除了存储数据元素和指向直接后继节点的指针外，还存储了指向直接前驱节点的指针。
假设我们已知链表中的某个节点，我们希望在链表中删除这个节点。
如果是单向链表，我们需要遍历整个链表，查找到该节点的直接前驱节点后再进行删除，而在双向链表中，我们可以通过该节点获取到直接前驱节点。
实际上，我们经常使用的LinkedList.java就是双向链表，可谓是商业应用中，双向链表的最佳实现。
循环链表
除此之外，循环链表也是链表的一种实现，它的特点是尾节点的指针指向头节点，形成环状。
在循环链表中，我们可以从任意节点开始向同一方向出发，访问到链表中的全部节点，这是单向链表和双向链表无法完成的。
循环链表最著名的应用就是约瑟夫问题。
单向链表的实现
今天的最后一部分，我们就一起来实现单向链表。首先，我们定义单向链表的节点，节点主要包含两部分：数据元素和直接后继节点的指针。
public class Node<E> {
private E element;
private Node<E> next;
public Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
实际上，仅有Node也已经足够我们构建链表了，比如说：
Node<Integer> node = new Node<>(0, new Node<>(1, new Node<>(2, null)));
但是这样的链表看着有点闹心，并且非常“丑陋”，而且需要手动实现诸如插入删除等操作，因此我们要对它进行简单的包装：
public class SinglyLinkedList<E> {
// 头节点
private Node<E> first;
// 尾节点
private Node<E> last;
private int size;
// 检查下标
private void checkIndex(int index) {
if (index >= this.size || index < 0) {
throw new IndexOutOfBoundsException();
}
}
private static class Node<E> {
private E element;
private Node<E> next;
public Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
}
将Node封装到单向链表SinglyLinkedList中，同时添加了私有变量first，last和size为了方便后续的操作，同时添加了检查下标的私有方法。
新增操作非常简单，只需要处理好链表为空的情况，其余直接在链表尾部添加即可，代码实现如下：
public void add(E element) {
Node<E> newestNode = new Node<>(element, null);
if(this.first == null) {
this.first = this.last = newestNode;
} else {
this.last.next = newestNode;
this.last = newestNode;
}
this.size++;
}
我们再来实现查找指定下标数据元素的方法，实现的思想也非常简单，只需要从链表的头部开始，不断的向后移动，直到到达指定下标为止，代码实现如下：
public E get(int index) {
checkIndex(index);
int i = 0;
Node<E> current = this.first;
while (i < index) {
current = current.next;
i++;
}
return current.element;
}
最后，我们实现删除指定数据元素的方法，实现也并不复杂，不过要处理比较多的情况：
头节点符合，并且链表中全部元素都符合，删除整个链表，并更新头尾节点
头节点不符合，链表中间包含或者尾节点符合，删除指定元素/更新尾节点
代码实现如下：
while (this.size != 0 && this.first.element.equals(element)) {
Node<E> oldFirst = this.first;
if(oldFirst == this.last) {
this.first = this.last = null;
} else {
this.first = oldFirst.next;
oldFirst.next = null;
}
this.size--;
}
if (this.size == 0) {
return;
}
Node<E> prev = this.first;
while (prev.next != null) {
if (prev.next.element.equals(element)) {
Node<E> delNode = prev.next;
if(delNode == this.last) {
this.last = prev;
}
prev.next = delNode.next;
delNode.next = null;
this.size--;
} else {
prev = prev.next;
}
}
这样我们就实现了一个单向链表，并为其添加了查找，新增和删除的操作。这样的链表我们拿来学习，“娱乐”是可以的，但是在商业应用中使用，就显得远远不足了。诸如，在指定位置添加，删除指定位置数据元素等，就留给小伙伴们自行实现了。
结语
今天，我们一起学习了第一个真正意义上的动态数据结构-链表，了解了它的3种实现，并一起动手实现了简单的单向链表。
相较于数组而言，链表对内存的要求相当低，这为链表带来优势，同时也使其失去了随机存取的能力。
练习
动手实现下自己的链表吧：
本篇内容的代码仓库：Gitee代码仓库
好了，今天就到这里了，Bye~~
