【数据结构】基础：线性表

【数据结构】基础：线性表

摘要：本文将会介绍关于线性表相关的知识，首先从总体上了解线性表，再通过对常见线性表——顺序表、单链表与带头双向循环链表进行理解与实现，并总结各种线性表的优缺点特点。

---

一. 线性表概述

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

本文将会主要介绍顺序表与链表，并对二者进行实现，还会对两者进行比较，最后再对其他线性表进行补充。

二. 顺序表

2.1 概述

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

笼统来说，顺序表就是数组，但实际上还是有差异的，顺序表在数据插入过程中，必须按照顺序依次插入，不像平时使用数组时可以随机存储，这是顺序表的定义所决定的。

顺序表一般可以分为：

• 静态顺序表：使用定长数组存储
• 动态顺序表：使用动态开辟的数组存储

静态顺序表相比起动态顺序表，优点是实现起来较为简单，缺点是比较不灵活的，它对空间大小开辟并不准确，可能会造成空间的浪费或不足，在后面实现两者后，会发现还有其他问题的存在，将在后文进行总结介绍。

2.2 实现与定义

静态顺序表

直接定义结构体，其中包括一个大小固定的数组，以及通过size表示空位位置或者表示顺序表此时的大小，可以使用typedef来方便在后面需要进行的定义，还可以通过宏定义来方便修改数组的大小。

#define NUM 10
typedef int ListType;
//在此使用了typedef，但后面可以使用SL，但此处不是中
typedef struct SeqList {
	ListType SeqListArr[NUM];
	size_t size;
}SL;
1
2
3
4
5
6
7

动态顺序表

实现方式与静态顺序表相似，存在很多细节上的差异。首先由于需要动态规划的内存空间，因此通过指针来代替数组，在后面会对其开辟空间，同样的需要一个size来标识当前大小，有效数据个数，最重要的是需要一个capacity来标识表的总大小，每当表大小不足时，就会开辟空间。

//动态顺序表
typedef int ListType;
//在此使用了typedef，但后面可以使用SeqList
typedef struct SeqList {
	ListType* SeqListPoint;
	size_t size;
	size_t capacity;
}SeqList;
1
2
3
4
5
6
7
8

由于动态顺序表具有更广泛的应用，以下的操作和销毁都会对动态顺序表进行。

2.3 相关操作

初始化

在初始化过程中，只需要将各项数值赋空就完成，但是注意的是当使用接口的形式时，必须关注相应的传参形式，由于需要修改自身的内容，因此不能使用形参传递，需要用指针传递。当然需要放置传入的指针为空，这时可以进行断言一下，相关代码如下:

void SeqListInit(SeqList* seqlist) {
	seqlist->SeqListPoint = NULL;
	seqlist->capacity = seqlist->size = 0;
}
1
2
3
4

销毁

对动态顺序表销毁只需要将开辟的空间释放，并将各成员的值赋空就完成，同样需要注意传参形式，代码示例如下：

void SeqListDestroy(SeqList* seqlist) {
	assert(seqlist);
	if (seqlist->SeqListPoint != NULL) {
		free(seqlist->SeqListPoint);
		seqlist->SeqListPoint = NULL;
	}
	seqlist->size = 0;
	seqlist->capacity = 0;
}
1
2
3
4
5
6
7
8
9

尾插

尾插是在顺序表末尾插入数据，由于动态顺序表的特性，先进行分析：可以分为内存空间足够与内存空间不足的情况，如果内存足够，直接尾插接口，否则需要先开辟空间，再进行插入操作。对于开辟空间，可以通过相应库函数就可以完成，如果开辟成功需要修改capacity的值。由于担心顺序表为空，因此断言一下。由于后面还会常会出现对空间大小的判断，通过函数形式书写。代码示例如下：

void checkSize(SeqList* seqlist) {
	assert(seqlist);
	if (seqlist->capacity == seqlist->size) {
		int capacity = seqlist->capacity == 0 ? 4 : seqlist->capacity * 2;
		ListType* temp =
			(ListType*)realloc(seqlist->SeqListPoint, capacity * sizeof(ListType));
		if (temp == NULL) {
			perror("realloc");
			exit(-1);
		}
		seqlist->SeqListPoint = temp;
		seqlist->capacity = capacity;
	}
}

void SeqListPushBack(SeqList* seqlist, ListType element) {
	assert(seqlist);

	checkSize(seqlist);
	seqlist->SeqListPoint[seqlist->size] = element;
	seqlist->size++;
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

尾删

尾删操作只需要使得最后一位失效即可，但是需要注意是否可以删除的判断，因此增加断言，示例代码如下：

void SeqListPopBack(SeqList* seqlist) {
	assert(seqlist->size > 0);
	seqlist->size--;
	return;
}
1
2
3
4
5

头插

头插操作对于顺序表是较为麻烦的，首先对其进行分析，和尾插一样需要考虑到空间大小的问题，其次还要考虑到，由于是头插因此每一个后续结点都需要往后移动一位。并且必须是从后往前移动，否则会修改没移动的结点的信息。示例代码如下：

void SeqListPushFront(SeqList* seqlist, ListType element) {
	assert(seqlist);

	checkSize(seqlist);
	// 后移一位
	for (int i = 0; i < seqlist->size; i++) {
		seqlist->SeqListPoint[seqlist->size - i] = seqlist->SeqListPoint[seqlist->size - 1 - i];
	}
	seqlist->SeqListPoint[0] = element;
	seqlist->size++;
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12

对于循环的内容，进行相应解释：我采取的方法是看初始态与末态的方法书写循环，首先是连续遍历，只需注意头尾过程，中间过程为连续重复可忽略的，其次初始态是从后往前复制的，所以初始态位置为``seqlist->size - 0与seqlist->size -1 - 0 ，而末态是为 seqlist->size - seqlist->size -1与seqlist->size -1 - seqlist->size -1`，最后可总结出循环遍历过程的值为 0 ~ seqlist->size -1。当然还有其他方法，值得大家不断探讨。

头删

思路与头插相似，只需要将后面的元素往前移动一位，为了不覆盖数据，应该从前往后移动，示例代码如下：

void SeqListPopFront(SeqList* seqlist) {
	assert(seqlist);
	assert(seqlist->size > 0);
    
	for (int i = 0; i < seqlist->size - 1; i++) {
		seqlist->SeqListPoint[i] = seqlist->SeqListPoint[i + 1];
	}
    
	seqlist->size--;
	return;
}
1
2
3
4
5
6
7
8
9
10
11

此处循环条件书写也是通过头插循环的循环书写方式一致。

查找

查询操作只需要遍历表，返回找到的值，如果找不到则返回负一，而且如果要实现链式访问，可以修改查询起点，如此查询不止一个位置，可以查询多个位置，示例代码如下：

//查找
int SeqListFind(SeqList* seqlist,ListType element) {
	assert(seqlist);
	for (int i = 0; i < seqlist->size; i++) {
		if (seqlist->SeqListPoint[i] == element)
			return i ;
	}
	return -1;
}

int SeqListnFind(SeqList* seqlist, ListType element, int begin) {
	assert(seqlist);
	for (int i = begin; i < seqlist->size; i++) {
		if (seqlist->SeqListPoint[i] == element)
			return i ;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

插入

与头插非常类似，只需要将头插的位置改为中间位置即可，需要注意的是这里的循环的开始与终止，在此我采用解方程的方法求出结果，方法通过图像的形式展示，再用上述书写循环的方法完成代码书写。在此需要也对pos进行检查，添加断言。代码示例如下：

void SeqListInsert(SeqList* seqlist, size_t pos, ListType element) {
	assert(seqlist);
	assert(pos >= 0 );
	assert(pos <= seqlist->size );

	checkSize(seqlist);
	for (int i = 0; i < seqlist->size - pos; i++) {
		//从最后一个开始挪动
		seqlist->SeqListPoint[seqlist->size - i] = seqlist->SeqListPoint[seqlist->size - 1 - i];
	}
	seqlist->SeqListPoint[pos] = element;
	seqlist->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

删除

和插入实现方式一样，只需要修改循环条件，此处通过图片形式展示，注意从前往后移动，示例代码如下：

void SeqListErase(SeqList* seqlist, size_t pos) {
	assert(seqlist);
	assert(pos >= 0);
	assert(pos <= seqlist->size -1);// 不加也可以 因为会跑不到这里
	assert(seqlist->size > 0);
	for (int i = pos; i < seqlist->size - 1; i++) {
		seqlist->SeqListPoint[i] = seqlist->SeqListPoint[i + 1];
	}
	seqlist->size--;
}
1
2
3
4
5
6
7
8
9
10

打印

void SeqListPrint(SeqList* seqlist) {
	for (int i = 0; i < seqlist->size; i++) {
		printf("%d ->", seqlist->SeqListPoint[i]);
	}
	printf("NULL\n");
	printf("size = %d  capacity = %d\n", seqlist->size, seqlist->capacity);
1
2
3
4
5
6

2.4 优点与缺点

优点：方便直接顺序读取，得到位置后，直接获得该位置信息内容

缺点：空间不足时需要扩容，扩容是消耗一定的性能的，还可能存在一定的浪费，头部的插入和删除效率是低下的

三. 单链表

3.1 概述

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

链表的种类也是非常的多样的，可以分为：带头与不带头、单向与双向、循环与非循环，在后续拓展板块将会对各个种类进行简要介绍。而后文主要介绍不带头不循环的单向链表，这是最基础的链表，可以进行变形为各式各样的链表。

首先，将从单链表出发，在通过单链表去理解其他形式链表。单链表**（在该段内容中后续简称链表）结构分为数据部分与指向下一节点的指针部分**，链表的结构使得它可以对顺序表的缺点进行优化的，其中优化方式是通过按需申请释放和在删除和插入时不移动大量数据，这些内容将会在实现后相应功能后，进行完备的总结。

在此展示一下链表的物理结构与逻辑结构，所谓物理结构式内存中实际存储的样子，逻辑结构是为了表示想象出来的，示意图如下：

3.2 实现与定义

实现

在上述内容中提及，链表的结构可以分为数据部分与指向下一结点的指针，同时可以添加宏定义与typedef使代码更易懂可修改，示例代码如下：

typedef int ListType;

struct ListNode {
	ListType data;
	struct ListNode* next;
};

typedef struct ListNode ListNode;
1
2
3
4
5
6
7
8

易错点：可能会有人在结构体类就使用了typedef定义后的结构体名称，实际上这样是错的，需要在定义之后才可以使用，否则是无效语句。错误示例如下：

typedef int ListType;

typedef struct ListNodeListNode {
	ListType data;
	ListNode* next;
}ListNode;
1
2
3
4
5
6

定义

在定义过程中，有一个易错点，即像普通变量那样定义，实际上这是不行的，因为每当在函数中定义时，一旦函数栈帧释放，就会连同该结点一起释放，这样就不存在相应的结点了，因此不能在栈区开辟空间。而解决方法就是在堆区通过库函数进行开辟。由于每次开辟需要对指针进行检测，非常麻烦，因此我们通过一个函数进行封装，示例代码如下：

ListNode* BuyListNode(ListType data) {
	ListNode* listNode = (ListNode*)malloc(sizeof(ListNode));
	if (listNode == NULL) {
		perror("malloc");
		exit(-1);
	}

	listNode->data = data;
	listNode->next = NULL;
	return listNode;
}
1
2
3
4
5
6
7
8
9
10
11

为了更好的进行实验或者更方便的建立链表，在此再封装一个函数来创建链表，在创建链表的过程中，同样需要分情况讨论，对于创建节点数为0的链表时，直接返回NULL，对于第一个节点，需要将直接将头指针指向创建的节点，对于其他节点则是要完成链接操作，在代码后方会进行图片说明。在此提出两个示例，分别为一般顺序创建与用于OJ数组创建，示例代码如下：

ListNode* CreateList(int nums) {
	ListNode* phead = NULL;
	ListNode* ptail = phead;
	if (nums == 0) {
		return phead;
	}
	for (int i = 0; i < nums; i++) {
		if (phead == NULL) {
			phead = BuyListNode(i);
			ptail = phead;
		}
		else {
			ListNode* ptemp = BuyListNode(i);
			ptail->next = ptemp;
			ptail = ptemp;
		}
	}
	return phead;
}
ListNode* Oj_CreateList(int nums, int* arr) {
	ListNode* phead = NULL;
	ListNode* ptail = phead;
	if (nums == 0) {
		return phead;
	}
	for (int i = 0; i < nums; i++) {
		if (phead == NULL) {
			phead = BuyListNode(arr[i]);
			ptail = phead;
		}
		else {
			ListNode* ptemp = BuyListNode(arr[i]);
			ptail->next = ptemp;
			ptail = ptemp;
		}
	}
	return phead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

3.3 相关操作

打印

核心思想是通过遍历完成操作，但需要留意相应细节，首先对于空链表需要单独判断，其次遍历的方式是不断访问当前节点的next指针，结束遍历条件是判断当前节点是否为空，示例代码如下：

void ListPrint(ListNode* pListhead) {
	if (pListhead == NULL) {
		printf("NULL\n");
		return;
	}
	else {
		ListNode* ptemp= pListhead;
		while (ptemp != NULL) {
			printf("[%d|%p] -> ", ptemp->data, ptemp->next);
			ptemp = ptemp->next;
		}
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

尾插

尾插操作的思路是通过遍历找出尾节点，将创建的新节点链接起来。同样需要对其分情况讨论，首先是判断是否为空链表，为空直接指向，否则就进行链接，而遍历方法为访问相应节点的next指针，并当next指针为空时即为尾节点，图示将会放在代码下方。特别需要注意的是，此处是有可能对传递进来的节点指针发生改变的，就不可以使用形参传递，而应该使用指针传递，由于传入的是一级指针，所以需要用二级指针来指向一级指针作为参数。代码示例如下：

void ListPushBack(ListNode** ppListhead, ListType data) {
	ListNode* ptemp = BuyListNode(data);
	if (*ppListhead == NULL) {
		*ppListhead = ptemp;
	}
	else {
		ListNode* pListtail = *ppListhead;
		while (pListtail->next != NULL) {
			pListtail = pListtail->next;
		}
		pListtail->next = ptemp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

尾删

尾删的思路是遍历寻找倒数第二的节点，将其指向NULL，对末尾节点释放操作。其中需要注意其中细节，首先面对空链表，是不可以删去的，此时需要进行断言，其次对于只剩下一个的节点，需要将其指向空指针，最后对于普通删除，按照思路书写即可，示例代码如下：

void ListPopBack(ListNode** ppListhead) {
	assert(*ppListhead);

	if ((*ppListhead)->next == NULL) {
		ListNode* ptemp = *ppListhead;
		free(ptemp);
		*ppListhead = NULL;
	}
	else {
		ListNode* ptail = *ppListhead;
		while (ptail->next->next != NULL) {
			ptail = ptail->next;
		}
		free(ptail->next);
		ptail->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

头插

头删的思路则是创建一个新节点，将通过头结点链接新节点，最后在更改头结点指向新节点，对于空链表、只有一个节点的情况并不需要特殊处理，示例代码如下：

void ListPushFront(ListNode** ppListhead, ListType data) {
	ListNode* ptemp = BuyListNode(data);
	ptemp->next = *ppListhead;
	*ppListhead = ptemp;
	return;
}
1
2
3
4
5
6

头删

思路是通过一个临时指针指向头结点，更改头结点，最后完成对原头结点的释放，其中需要对空链表进行判断，其他情况并无其他特殊情况，代码示例如下：

void ListPushFront(ListNode** ppListhead, ListType data) {
	ListNode* ptemp = BuyListNode(data);
	ptemp->next = *ppListhead;
	*ppListhead = ptemp;
	return;
}
1
2
3
4
5
6

查找

思路是简单的遍历操作，找到返回当前节点的指针，否则返回空

ListNode* ListFind(ListNode* pListhead, ListType data) {
	if (pListhead == NULL) {
		return NULL;
	}
	ListNode* ptemp = pListhead;
	while (ptemp != NULL) {
		if (ptemp->data == data) {
			return ptemp;
		}
		ptemp = ptemp->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

指定位置后插

思路为对指定位置的next指针修改，同时将新节点指向原来的next处，其中需要进行空链表断言或者将空位置赋予到新节点处，再次选择了后者，还需要注意的是其中的赋值顺序，切记不要将数据覆盖，示例代码如下：

void ListInsertAfter(ListNode* pListpos, ListType data) {
	//assert(*ppListpos);
	ListNode* ptemp = BuyListNode(data);
	if (pListpos == NULL) {
		pListpos = ptemp;
	}
	else{
		ptemp->next = pListpos->next;
		pListpos->next = ptemp;
	}
}
1
2
3
4
5
6
7
8
9
10
11

有细心的读者可能发现，此处使用的是一级指针，为什么呢？因为此处修改的不是指针本身，而是指针指向的结构体的next指针，因此使用一级指针进行访问即可。

指定位置插入

其思路是通过一个临时指针，遍历整个链表，当发现下一个节点是pos时停下，这样就可以将新节点插入到pos之前。其中需要对各种情况分类，当传入为空节点时其中需要注意断言，原因是不可以插入到一个空节点前，如果链表只有一个节点时，前插入即可，如果是一般情况，按照思路书写即可，代码示例如下：

void ListInsert(ListNode** ppListhead, ListNode* pListpos, ListType data) {
	assert(pListpos);
	ListNode* ptemp = BuyListNode(data);
	if (*ppListhead == pListpos) {
		ListPushFront(ppListhead, data);
	}
	else {
		ListNode* pListpre = *ppListhead;
		while (pListpre->next != pListpos) {
			pListpre = pListpre->next;
		}
		pListpre->next = ptemp;
		ptemp->next = pListpos;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

指定位置后删

思路是将pos位置的节点next指向next的next位置，其中需要分情况讨论：如果为空节点，无法删除，进行断言操作，如果后续无节点，则会直接返回，不删除，其他情况按照思路实现，代码示例如下：

void ListEraseAfter(ListNode** ppListpos) {
	assert(*ppListpos);
	if ((*ppListpos)->next == NULL) {
		return;
	}
	else {
		ListNode* ptemp = (*ppListpos)->next;
		(*ppListpos)->next = (*ppListpos)->next->next;
		free(ptemp);
	}
}
1
2
3
4
5
6
7
8
9
10
11

指定位置删除

思路与插入相似，都是通过一个临时节点，寻找pos的前一位，通过对next指针的修改完成操作。其中需要注意的是当为空链表或空节点的情况需要断言，若果只有一个节点，则将表头指向为空，其他情况按照思路书写即可，代码示例如下：

void ListErase(ListNode** ppListhead, ListNode* pListpos) {
	assert(pListpos);
	assert(*ppListhead);
	if (pListpos == *ppListhead) {
		*ppListhead = NULL;
	}
	else{
		ListNode* pListpre = *ppListhead;
		while (pListpre->next == pListpos) {
			pListpre = pListpre->next;
		}
		pListpre->next = pListpos->next;
		free(pListpos);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

销毁

通过遍历的方式，逐个free即可，当然是需要进行断言的，示例代码如下：

void ListDestory(ListNode** ppListhead) {
	assert(*ppListhead);
	while ((*ppListhead) != NULL){
		ListNode* ptemp = *ppListhead;
		*ppListhead = (*ppListhead)->next;
		free(ptemp);
	}
	/*assert(*ppListhead);
	ListNode* ptemp = *ppListhead;
	while (ptemp != NULL) {
		ListNode* pnext = ptemp->next;
		free(ptemp);
		ptemp = pnext;
	}
	*ppListhead = NULL;*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.4 代码书写总结

在书写完上述代码后，其实可以总结一下书写的方法，其过程我们都是先将大体思路通过画图的形式规划出，然后再去弥补细节，其中细节多在于空节点、一个节点和使得思路无法实现的情况下这几个方面。这些方法不仅在于书写代码中，还可以帮助去书写部分的测试案例，进行边缘检测。

3.5 优点与缺点

优点：节省空间，使用多少开辟多少；插入删除方便，无需整体移动；

缺点：查询时需要遍历链表；对节点指定位置前的插入与删除需要遍历链表；

3.6 补充

断言的理解：assert是个调试宏，只在debug模式下有效 ，release模式下就不存在了，assert(表达式)为假就会触发，说明程序当前处于非法情况，在书写代码过程中，经常会使用到断言，而需要断言的情况是查看条件是否合理，如果会导致程序崩溃或者不可预期的错误就需要对其断言操作，而不是对每一种情况都进行断言操作的。

形参传递与指针传递：在书写代码的过程中，可能会发现有时使用的是一级指针，有时使用的是二级指针。在使用二级指针时，是为了可以修改一级指针，因此，在一级指针与二级指针的使用情况是看是否需要修改一级指针本身，如果需要则用指针传递，如果不需要而是修改指针指向的对象，则使用形参传递即可。

四. 链表的其他结构

在上文提到，链表有多种结构，其分类方式主要是在于是否带头、单向双向、循环不循环，其逻辑结构如下：

最常用的是上文已经介绍的不带头单向不循环链表，还有一种较为常用的是带头双向循环链表，两者概述如下：

• 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。另外这种结构在笔试面试中出现很多。
• 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。

以下将会实现带头双向循环链表，实际上实现后可以与单链表作比较，发现其他链表实现也并不是太复杂，有异曲同工之妙。

五. 带头双向循环链表

5.1 定义与初始化

该链表节点的结构，为储存数据的内容，以及分别指向前后的两个指针。

实现初始化该链表首先要明确常见的类型，是带头双向循环，因此要进行初始化定义一个哨兵卫节点，而双向的结构，说明需要两个指针分别指向下一位与上一位，最后由于是循环结构，因此要把尾与头相连。对于初始化的节点，首先先从堆区创建一个节点，逐个带入上述分析，对于两个指针，由于是循环，需要指向自己。在此由于从堆区创建需要部分判断，为简化代码封装成函数，代码示例与图示如下：

//结构
typedef int DoubleListType;
struct DoubleListNode {
	DoubleListType val;
	struct DoubleListNode* pre;
	struct DoubleListNode* next;
};
typedef struct DoubleListNode DoubleListNode;
1
2
3
4
5
6
7
8

//初始化
DoubleListNode* ListInit() {
	DoubleListNode* preturn = BuyDoubleListNode(-1);
	preturn->next = preturn;
	preturn->pre = preturn;
	return preturn;
}
1
2
3
4
5
6
7

5.2 相关操作

尾插

该类型的链表的插入与删除是较为简单的，因为结构的复杂性，不需要对过多的情况进行判断。一般思路为首先从创建一个节点储存数据，通过双向循环的性质，找出尾节点，将尾节点指向新节点，将新节点指向头结点，在指向过程需要注意顺序关系，否则可能出现节点覆盖的问题。同时由于不合法的链表无法插入，因此进行断言操作。可能有人会提到如果只有一个节点怎么办，实际上将思路套入并与画图相结合，回到了我们最初初始化的状态。代码与图例如下：

void ListPushBack(DoubleListNode* phead, DoubleListType val){
	assert(phead);

	DoubleListNode* ptemp = BuyDoubleListNode(val);
	DoubleListNode* tail = phead->pre;
	tail->next = ptemp;
	ptemp->pre = tail;
	phead->pre = ptemp;
	ptemp->next = phead;
}
1
2
3
4
5
6
7
8
9
10

尾删

由于结构的复杂减少了对情况的讨论，思路是通过双向循环性质找到尾节点，然后将尾节点前一个节点与头结点相连，删除尾节点。需要注意的是除了判断链表是否有效外，还需要注意是否可以删除，因此进行两处断言，代码示例与图示如下：

void ListPopBack(DoubleListNode* phead) {
	assert(phead);
	assert(phead->next != phead);
	DoubleListNode* ptail = phead->pre;
	phead->pre = ptail->pre;
	ptail->pre->next = phead;
	free(ptail);
}
1
2
3
4
5
6
7
8

头插

思路是将头结点后一节点找出，直接相互指向即可，由于不会出现覆盖问题，因此不需要注意顺序。而当一个节点时，实际上将其作为逻辑是一样的，不是特殊情况，在后续只进行画图不再进行说明只有一个头结点与两个节点的情况。代码示例与图示如下：

void ListPushFront(DoubleListNode* phead, DoubleListType val) {
	assert(phead);

	DoubleListNode* ppre = phead->next;
	DoubleListNode* ptemp = BuyDoubleListNode(val);

	phead->next = ptemp;
	ptemp->next = ppre;
	ptemp->pre = phead;
	ppre->pre = ptemp;
}
1
2
3
4
5
6
7
8
9
10
11

头删

通过指针找出头结点后一节点后，创建一个临时节点储存，将头结点与更新后的下一节点链接，释放中间节点。需要注意的是此处由于是删除，也要进行两次断言，代码示例与图示如下：

void ListPopFront(DoubleListNode* phead) {
	assert(phead);
	assert(phead != phead->next);
	
	DoubleListNode* ppre = phead->next;
	phead->next = ppre->next;
	ppre->next->pre = phead;
}
1
2
3
4
5
6
7
8

插入

删除的思路和前面的插入类似，本质是找出插入位置前后的节点，将其链接，由于可能存在节点覆盖的问题，为了严谨，一般是将新节点与两侧相连接，再旧节点链接新节点，而此时就需要注意顺序了。由于结构的特殊性，每个结点都是等价的，就连只有哨兵卫节点也是，因此没有特殊情况，代码与图示如下：

void ListInsert(DoubleListNode* pos, DoubleListType val) {
	assert(pos);
	DoubleListNode* ptemp = BuyDoubleListNode(val);
	ptemp->pre = pos->pre;
	ptemp->next = pos;
	pos->pre->next = ptemp;
	pos->pre = ptemp;
}
1
2
3
4
5
6
7
8

补充：写完插入函数后，可以根据设定插入位置后来更加简化的重写头插与尾插，代码示例如下：

void ListPushFront(DoubleListNode* phead, DoubleListType val) {
	ListInsert(phead->next, val);
}
void ListPushBack(DoubleListNode* phead, DoubleListType val){
	ListInsert(phead, val);
}
1
2
3
4
5
6

删除

删除思路与前面的删除相似，思路为找出要删除节点，同时用临时指针表示各个节点，将两侧节点链接，自身释放，同样由于结构的特殊性，每个结点都是等价的，就连只有哨兵卫节点也是，因此没有特殊情况。需要注意的是C语言实现，会存在bug，哨兵卫是不能删除的，但是在这里可以删除。代码与图示如下：

void ListErase(DoubleListNode* pos){
	assert(pos);
	// 存在bug 哨兵卫是不能删除的 但是在这里可以删除
	DoubleListNode* pre = pos->pre;
	DoubleListNode* next = pos->next;

	pre->next = next;
	next->pre = pre;

	free(pos);
}
1
2
3
4
5
6
7
8
9
10
11

补充：写完删除函数后，可以根据设定删除位置后来更加简化的重写头删与尾删，代码示例如下：

void ListPopBack(DoubleListNode* phead){
	ListErase(phead->pre);
}
void ListPopFront(DoubleListNode* phead){
	ListErase(phead->next);
}
1
2
3
4
5
6

查找

查找的方法就是通过遍历，不断搜索，由于是循环结构，我们需要设置终点，在此是设置起点为头结点的下一节点，终点为头结点，代码示例如下：

DoubleListNode* ListFind(DoubleListNode* phead, DoubleListType val) {
	assert(phead);
	DoubleListNode* cur = phead->next;
	while (cur != phead) {
		if (val == cur->val) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

大小

与查找思路一致，遍历即可

size_t ListSize(DoubleListNode* phead) {
	assert(phead);
	DoubleListNode* cur = phead->next;
	size_t size = 0;
	while (cur != phead) {
		size++;
		cur = cur->next;
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10

判空

观察为空的结构，只存在哨兵卫，特点为指向自己，代码示例如下：

int isDoubleListEmpty(DoubleListNode* phead) {
	assert(phead);
	return phead == phead->next;
}
1
2
3
4

销毁

通过遍历销毁，最后销毁头结点

void ListDestory(DoubleListNode* phead) {
	assert(phead);
	DoubleListNode* cur = phead->next;
	while (cur != phead) {
		DoubleListNode* ptemp = cur;
		cur = cur->next;
		free(ptemp);
	}
	free(phead);
}
1
2
3
4
5
6
7
8
9
10

5.3 优点与缺点

经过上述实现，可以发现，虽然结构式复杂的， 但是实现起来简单的多，减少了许多其他情况的讨论，这是复杂结构下带来的优势，不过缺点也是有的，其本质仍然是链表，存在无法做到随机访问等问题。

六. 顺序表与链表对比

补充：对于缓存利用率的问题，首先在计算机中由于CPU速度非常快，而在存储设备中读写是需要时间的，如果时间慢了就会拖累CPU速度，但是时间少的，造价就会很贵，因此会对计算机进行分层储存，离CPU越近的越快。分层结构可以大致分从底层到顶层可以分为：外存 --> 内存 -->三级缓存 --> 寄存器。而数据结构的内容存在于内存中，在CPU需要读取数据结构时，为了减少速度代沟会将数据提前存入缓存或寄存器中哦，由于读取时连续空间，如果是连续的数据，可能读取的数据可能比较少就读取完毕，而如果是不连续的，可能会读取许多无效的数据，缓存的利用率就低了。

---

补充：

1. 代码将会放到：C_C++_REVIEW: 一套 C/C++ 系统完整的使用手册，以及部分疑难杂症的解析 (gitee.com) ，欢迎查看！
2. 欢迎各位点赞、评论、收藏与关注，大家的支持是我更新的动力，我会继续不断地分享更多的知识！