第一个动态结构：链表

封面：链表.png

王有志，一个分享硬核Java技术的互金摸鱼侠
加入Java人的提桶跑路群：共同富裕的Java人

今天我们一起学习线性表中的第二种数据结构：链表，也是真正意义上的第一个动态数据结构。
今天的内容分为3个部分：认识链表，链表的形式和单向链表的实现。

什么是链表

在数据结构：线性表入门中，我们知道数组使用连续的内存，可如果程序已经运行了很久，内存中没有足够的连续内存，这时需要一个线性表结构，~~除了使用360安全卫士清理内存外~~，该怎么办呢？
早在1955年就有人想到了这个问题，从而诞生了一种影响深远的数据结构-链表。

链表开发于1955-56，由当时所属于兰德公司（英语：RAND Corporation）的艾伦纽维尔（Allen Newell），克里夫肖（Cliff Shaw）和赫伯特西蒙（Herbert Simon）在他们编写的信息处理语言（IPL）中做为原始数据类型所编写。IPL被作者们用来开发几种早期的人工智能程序，包括逻辑推理机，通用问题解算器和一个计算机象棋程序。

以上来源于维基百科的链表。在预备知识：概念和存储结构中，我们讲到链式存储结构，链表正是这样一种结构：
图1：链式分配内存.png
可以看到，链表使用分散在内存各个角落的内存块，通过“一根线”将内存块”串“起来。
得益于链式存储结构，我们可以很容易的为链表动态扩缩容，通常我们会称这种为动态数据结构，而像数组那样顺序存储的数据结构称为静态数据结构。

链表的概念

链表中，如果每块内存只存储数据元素的话，内存之间就无法形成线性结构。
为了使链表“串起来”，除了存储数据元素外，还需要存储直接后继节点的内存地址，通过“无形的线”将内存块“串”起来。
图2：链表的节点.png
我们将存储后继节点内存地址的变量称为指针（即图中next）；存储着数据元素和指针的组合称为链表的节点；链表中第一个节点称为头节点，最后一个节点称为尾节点。
可能很多小伙伴听到指针就头疼，从C语言就开始折磨，好不容易到了Java，Python中没有了指针，可学个数据结构还要遭受指针的折磨。
其实指针的概念很简单，指针实际上是一个变量，存储的是某个对象的内存地址。

链表的特点

对于链表来说，插入和删除很简单，因为不需要使用连续的内存，所以也不需要在插入和删除后“整理”内存，得益于这种链式的存储结构，链表具有时间复杂度为 $O (1)$ 的插入和删除操作。

插入和删除

图3：链表的插入.png
如图，我们在节点B和D之间插入节点C，只需要2步操作即可：

节点C的指针指向节点D
节点B的指针指向节点C

删除操作也是类似的：
图4：链表的删除.png
如果要删除节点C，需要3步操作：

存储节点D
删除节点C的指针
节点B指向节点D

可以看到，链表的插入和删除操作仅需要有限的操作步骤即可完成，在这个意义上时间复杂度为 $O (1)$ 。

查询操作

对于链表来说，因为不具备顺序存储结构的特点，无法通过简单的计算查找到指定下标的数据元素，我们只能从链表的头节点出发，依次向后查询，直到查询到需要的数据元素位置。
这种情况下，链表查询操作的时间复杂度为 $O (n)$ 。

链表的形式

到目前为止，我们对链表有了一定的认识，接下来我们来看看都有哪些常用链表的实现。

单向链表

单向链表是最简单的链表，也是我们在学习链表的概念中使用到的形式。
图5：链表的节点.png
特点是，每个节点中只存储数据元素和指向直接后继节点的指针。下面会和大家实现一个简单的单向链表。

双向链表

双向链表是单向链表的升级版，除了存储数据元素和指向直接后继节点的指针外，还存储了指向直接前驱节点的指针。
图6：双向链表.png
假设我们已知链表中的某个节点，我们希望在链表中删除这个节点。
如果是单向链表，我们需要遍历整个链表，查找到该节点的直接前驱节点后再进行删除，而在双向链表中，我们可以通过该节点获取到直接前驱节点。
实际上，我们经常使用的LinkedList.java就是双向链表，可谓是商业应用中，双向链表的最佳实现。

循环链表

除此之外，循环链表也是链表的一种实现，它的特点是尾节点的指针指向头节点，形成环状。
图7：循环链表.png
在循环链表中，我们可以从任意节点开始向同一方向出发，访问到链表中的全部节点，这是单向链表和双向链表无法完成的。
循环链表最著名的应用就是约瑟夫问题。

单向链表的实现

今天的最后一部分，我们就一起来实现单向链表。首先，我们定义单向链表的节点，节点主要包含两部分：数据元素和直接后继节点的指针。

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;
	}
}