链表的数据结构与算法图解（单项、双项）

数组是软件开发过程中非常重要的一种数据结构，但是数组至少有两个局限：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

• 编译期需要确定元素大小
• 数组在内存中是连续的，插入或者删除需要移动数组中其他数据

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

事实上，我们更加关注的是基于数据结构的算法，链表是一种简单的数据组织方式，适合中等数量的数据，我们考察链表的添加、删除、查找即可，更加复杂的操作需求最好使用更加高级的数据结构。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

首先定义链表：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST

class Node {
public:
	//构造函数，创建一个节点
	Node(int el = 0, Node* ptr = nullptr) {
		info = el;
		next = ptr;
	}
	//节点的值
	int info;
	//下一个节点地址
	Node* next;
};

class NodeList {
public:
	//构造函数，创建一个链表，用于管理节点
	NodeList() {
		head = tail = nullptr;
	}
	//节点插入到头部
	void addToHead(int);
	//节点插入到尾部
	void addToTail(int);
	//删除头部节点
	int  deleteFromHead();
	//删除尾部节点
	int  deleteFromTail();
	//删除指定节点
	void deleteNode(int);
private:
	//头指针、尾指针
	Node *head, *tail;
};

#endif
复制代码

这里定义了两个class，分别用来表示节点以及管理节点的链表。其中，节点具有两个成员变量，分别是当前节点的值以及指向下个节点的指针。链表也具有两个成员变量，分别指向头结点以及尾节点。链表class具有5个成员方法，分别代表着节点的添加、删除、查找，我们来考察下这3种操作在链表中的表现。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

单向链表的操作比较简单，这里直接使用动图来代替代码，更加易于理解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

假设已有链表如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

• 节点插入到头部

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

节点插入到头部的逻辑比较简单，算法复杂度能在固定时间O(1)内完成，也就是说，无论链表中有多少个节点，该函数所执行操作的数目都不会超过某个常数c。注意，该操作的实现依赖head指针，否则无法确定头结点的地址，那么算法的复杂度将会大大增加。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

• 节点插入到尾部

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

节点插入到尾部的逻辑和插入到头部相似，算法复杂度也是O(1)，区别在于该操作的实现依赖tail指针，否则无法确定尾节点的地址，那么算法的复杂度将会大大增加。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

• 删除头部节点

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

删除头部节点操作的算法复杂度也是O(1)，该操作依赖head指针，通过head指针可以直接获取到下个节点的地址，所以复杂度很低。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

• 删除尾部节点

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

注意这里，删除尾部节点的算法复杂度是O(n)，相比于前面的O(1)，提升了两个量级。原因在于我们需要一个临时指针p，从头结点一直遍历到倒数第二个节点。因为删除尾节点之后，tail指针需要向头结点方向移动一次，但是在链表中不能直接获取到倒数第二个节点的地址，只能依靠遍历的方式，这就导致算法复杂度上升为O(n)。在单向链表中没有更好的解决方式了，在后面我们需要改进链表结构避免这种情况。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

• 删除指定节点

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

删除指定节点的算法复杂度也是不尽人意，在最好的情况下花费O(1)的时间，在最坏和平均情况下则是O(n)。通过动态图可以发现，我们定义P指针指向目标节点，定义Q节点指向目标节点的前驱节点。这两个变量的存在意义在于修正单向链表的指向，是不可或缺的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

基于单向链表的某些操作的算法复杂度无法满足我们的需求，这里主要指删除尾部节点以及删除指定节点，它们的平均复杂度达到了O(n)，相比于O(1)增加了两个量级。为了改进算法，我们需要修改链表的结构。对于删除尾部节点来说，瓶颈在于无法直接获取尾节点的前驱节点地址，我们可以为节点加上一个指向前节点的指针来解决，这就是所谓的双向链表。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

2、双向链表

双向链表是这个样子：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

首先是定义：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST

class Node {
public:
	//构造函数，创建一个节点
	Node(int el = 0, Node* p = nullptr, Node* q = nullptr) {
		info = el;
                pre  = p;
		next = q;
	}
	//节点的值
	int info;
        //前一个节点地址
        Node* pre;
	//下一个节点地址
	Node* next;
};

class NodeList {
public:
	//构造函数，创建一个链表，用于管理节点
	NodeList() {
		head = tail = nullptr;
	}
	//节点插入到头部
	void addToHead(int);
	//节点插入到尾部
	void addToTail(int);
	//删除头部节点
	int  deleteFromHead();
	//删除尾部节点
	int  deleteFromTail();
	//删除指定节点
	void deleteNode(int);
private:
	//头指针、尾指针
	Node *head, *tail;
};

#endif复制代码

基于双向链表的操作和单向链表非常相似，我们是从单向链表中扩展出双向链表的，目的是改进删除尾部节点的算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

• 删除尾部节点

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

可以看到删除尾部节点的算法复杂度已经降至O(1)，事实上pre指针不仅仅简化了删除尾节点操作，对于其他O(1)的操作也有简化，因为有了pre指针，有些临时指针就没必要定义了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

尽管如此，我们还是增加了空间的使用程度才降低了时间上的消耗，本质上是空间换取时间的做法。对于现代软件开发来讲，硬件已经不是主要瓶颈，一些空间上的代价是值得的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

也许有人了解过所谓的循环单向链表、循环双向链表，它们到底是什么东西呢？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

循环单向链表和单向链表的差别：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

差别就在于尾节点的next指针循环指向了头结点，这时候head指针就没必要存在了，如果继续定义head指针，只是更加方便一些，但它已经不是不可或缺的了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

循环双向链表和双向链表的差别：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

同样的道理，head指针根据需要添加。循环链表和普通链表没有本质的差别，可以根据需要自行选择。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html

到目前为止，我们还有一个问题没有解决，那就是删除指定节点。该操作本质上是查找问题，为了优化查找算法，我们需要继续对链表结构进行改动。事实上，上述链表已经足够满足需求了，因为我们假设对象是中等数量的数据，O(n)级别的操作可以接受，对于更加复杂的数据，需要更加复杂的数据结构进行处理。出于学习的态度，可以继续研究，毕竟有句话叫做-厚积薄发。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/8887.html