【洋哥带你玩转线性表（三）——双向链表】

双向链表的用法

文章目录

• 前言
• 一、双向链表的结构及定义
• 二、双向链表的代码实现
  • 1.创建新结点
  • 2.双向链表的初始化
  • 3.双向链表的数据打
  • 4.链表的尾插法
  • 5.链表的头插法
  • 6.链表的尾删法
  • 7.链表的尾删法
  • 8.链表的头删法
  • 9.判断链表是否为空
  • 10.任意位置元素的插入
  • 11.任意位置元素删除
• 三、链表与顺序表的比较
• 总结

---

前言

        本文主要介绍带头双向循环链表，此种链表结构复杂、一般用于单独存放数据，在现实生活当中所使用的链表大多数是带头循环双向链表，另外这个结构虽然复杂，但是在代码的实现过程当中却会带来很大的优势，使用起来反而简单了不少。

        另外，对于为什么要使用带头结点的结构，也就是我们平常所说的哨兵卫结点，那么带头结点（带哨兵卫结点）到底有什么样的好处呢？其实这个问题我已经在我的上一篇博客当中详细说明过了，如果读者有什么不明白的地方的话，可以查阅我的上一篇博文《线性表（二）——单链表》，在这片文章的末尾，我详细地介绍了址传递和值传递的区别，以及使用哨兵卫结点的好处，因为使用哨兵卫结点可以避免使用二级指针，这对于传参有很大的好处

---

一、双向链表的结构及其定义

1.双向链表的结构：

        双向链表也叫双链表，是指链表的每个节点拥有两个指针域，分别是直接前驱和直接后继，顾名思义直接前驱指向该结点的前一个结点，可以对其进行访问和操作，直接后继结点指向该结点的后一个结点，可以对后一个结点进行访问，而且此次我们主要讲解带头双向循环链表，如图所示。

2.双链表的定义：

typedef int DataType;

typedef struct ListNode {
	struct ListNode* next;
	struct ListNode* prev;
	DataType data;
}List;

拓展：

        ” struct ListNode “ 这个结构体就代表着链表的一个结点，在这个结构体当中我们有定义了来给两个结构体指针，我们可以由C语言所学到的知识所了解到，指针就是地址，我们平常所说的指针其实更多时候是指指针变量，并不是真正的指针，结构体指针也就是结构体地址，所以我们可以通过这一段代码了解到，在每一个双链表的每个结点当中都存放着前后两个结点的地址用于访问前后结点。

        我们在这里可以思考一下，为什么不可以直接在这个结构体当中再定义另一个结构体，而是要定义一个结构体指针呢，其实道理并不难理解，如果在结构体当中有定义了另外一个结构体的话，那么他们将会形成无限嵌套，结构体当中含有结构体，而含有的结构体当中有含有另外一个结构体，这显然是不可以的。

3.双链表的初始化

List* ListInit()
{
	List* head = BuyListNode(-1);
	head->next = head;
	head->prev = head;

	return head;
}

4.双链表的常用接口

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int DataType;

typedef struct ListNode {
	struct ListNode* next;
	struct ListNode* prev;
	DataType data;
}List;

List* BuyListNode(DataType x);
List* ListInit();
void ListPrint(List* head);
void ListPushBack(List* head, DataType x);
void ListPushFront(List* head, DataType x);
void ListPopBack(List* head);
void ListPopFront(List* head);
bool ListEmpty(List* head);
void ListInsert(List* pos, DataType x);
void ListErase(List* pos);

说明：

        在对这个链表进行初始化的时候必须为其分配一个头结点也就是哨兵卫结点，将哨兵卫结点定义好之后，直接将其返回这样子的优势在于，无论对双链表进行怎样的操作，都可以直接通过头结点进行结点的查找，无论对双链表进行怎样的操作，头结点始终都不会发生变化，这样可以有效的避免在函数传参的时候使用二级指针，对于二级指针不是很清楚的小伙伴请看文章最开头的前言，那里面已经说明的很清楚了。

---

二、双向链表接口实现

1.创建新结点

List* BuyListNode(DataType x)
{
	List* newnode = (List*)malloc(sizeof(List));
	if (newnode == NULL)
	{
		printf("malloc is fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

2.双向链表的初始化

List* ListInit()
{
	List* head = BuyListNode(-1);
	head->next = head;
	head->prev = head;

	return head;
}

3.双向链表的数据打印

void ListPrint(List* head)
{
	assert(head);
	List* cur = head;
	while (cur->next !=head)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

4.链表的尾插法

说明：

        想要对双链表进行尾插，就必须先找到链表的最后一个结点以及倒数第二个结点，将倒数第二个结点与头结点建立联系（因为此处采用的是双向带头循环链表），再将最后一个结点释放掉，因为这里已经提前将倒数第二个结点用tailPrev标识出来了，所以也可以先将末尾结点释放。

void ListPushBack(List* head, DataType x)
{
	assert(head);
	List* newnode = BuyListNode(x);
	List* tail = head->prev;
	List* tailPrev = tail->prev;
	tailPrev->next = head;
	head->prev = tailPrev;
	free(tail);
	tail = NULL;
}

5.链表的头插法

说明：

        即便是头插法也是在头结点之后进行插入，再次强调头结点并不等同于首结点（第一个结点），头结点只是对链表的一个标识作用，相当于首地址，不管是单向还是双向链表，只要是带头结点的链表，无论对链表进行怎样的操作（销毁除外），链表的头结点（哨兵卫结点）都不会发生变化。

        所以此处必须先找到链表的首结点，然后再将新结点放在原来的首结点之前，那么这时新结点就成为了首结点。

void ListPushFront(List* head, DataType x)
{
	assert(head);
	List* prev = head->next;
	List* newnode = BuyListNode(x);
	head->next = newnode;
	newnode->prev = head;
	newnode->next = prev;
	prev->prev = newnode;
}

6.链表的尾删法

void ListPopBack(List* head)
{
	assert(head);
	assert(head->next != head);
	List* tail = head->prev;
	List* tailPrev = tail->prev;
	tailPrev->next = head;
	head->prev = tailPrev;
	free(tail);
}

7.链表的头删法

void ListPopFront(List* head)
{
	assert(head);
	assert(head->next != head);
	List* cur = head->next;
	head->next = cur->next;
	cur->next->prev = head;
	free(cur);
}

8.判断链表是否为空

说明：

        带头结点的链表只要链表除了头结点外没有任何的结点，那么这个链表就为空。

bool ListEmpty(List* head)
{
	assert(head);
	return head->next == head;
}

9.任意位置元素的插入

void ListInsert(List* pos, DataType x)
{
	assert(pos);
	List* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
	newnode->prev = pos;
}

10.任意位置元素删除

说明：

        对于初学者来说最好能够使用第三种方案，因为将前后两个结点标识出来以后，操作的时候简介明了，而像第一种情况下不进行任何的标识，操作的顺序就显得尤为重要，因为要想访问一个结点，就必须知道它的前一个结点或者后一个结点，如果操作顺序不当有可能导致空指针异常，也就是我们平常所说的野指针。

void ListErase(List* pos)
{
	//方法一：
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	
	//方法二
	List* posPrev = pos->prev;
	posPrev->next = pos->next;
	pos->next->prev = posPrev;
	free(pos);

	//方法三
	List* prev = pos->prev;
	List* next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
}

---

三、链表与顺序表的对比

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续但物理上不一定连续
随机访问	支持：O（1）	不支持：O（N）
在任意位置插入或者删除元素	可能需要搬移元素	只需要修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储、频繁访问	任意位置插入和删除
缓存利用率	高	低

你的支持就是我前进的动力，怎么样，你学会了吗？

---

总结

        其实在进行到这里的时候，我本人已经敲了三万多行的代码了，这个阶段也只能算是个程序员入门者，我也在不断地丰富自己的经验，也在不断地学习，我始终相信着量变一定能够引起质变，但是对于很多的时候有很多知识点我掌握的不是很清楚，为了能够让自己更好地理解所学的知识，我选择开始写博客分享我的学习经历，曾经的我也一度认为，学习数据结构是一件很困难的事情，但是如今的我，不管是链表、栈、队列或是二叉树、排序这样难度的知识我也可以很好的理解了，数据结构不再向我想象的那样难了。

        要记住学习编程最重要的就是有一个好的老师指引，这一点非常重要，一般人根本不可能通过自学就能够学会编程，所以在你知道努力的重要性的前提下，找对一个启蒙老师是至关重要的，计算机专业的小伙伴可能有很深的体会，就是现在学校里面的教育和社会其实是完全脱节的，在学校里面是学不到任何的技术的，这就需要你一定要高瞻远瞩，尽一切可能寻找课外的资源，还有一点，这也是我曾经踩过的坑，在你学习一门语言的时候，先不要着急去看相关的书籍，而且有很多的书籍他本身就存在很多漏洞，还是先以视频资源为主吧。

        这就需要你对于很多信息的把握和搜集的能力了，现在的网络上有很多的资源，像B战和慕课之类的学习网站，上面海量的学习资源总有适合你的。

        在你充分的理解数据结构的基础上，再去写代码，这样子写出来的代码才有可能变成你的东西，还有更重要的，一定要养成每日刷题的习惯，LeetCode这是我经常使用的刷题软件，对于算法没有别的办法只有大量的刷题，见识越多，当自己面对相同类的问题的时候也就会更灵活。

        不光要重视计算机语言的学习，很多计算机基础也一定要掌握，例如数据结构与算法、操作系统、计算机网络、计算机组成原理、数据库等等这些计算机底层的逻辑，都一定要掌握。

        最后我想说的是”热爱可抵岁月漫长“，一定要热爱自己的专业，这是你的立身之本，这将使你一生受用，在无尽的岁月中，有很多值得我们来人间走一回的人或事，生如蝼蚁当有鸿鹄之志，命比纸薄当有不屈之心，不要因为眼前的一片乌云，就总是抱怨前途没有光明，永远不要用现状去评价任何一个人，包括你自己。如果此生不能成为一个伟大的人，那就成为一个拥有伟大内心世界的人吧！共勉之。