????????一个月没有更新了。上次讲了单链表的基础操作并且还简单介绍了一下指针的概念。简单回顾一下，单链表的两个结构体，一个是node，我们类比为房屋，里面储存房屋的各种信息，例如人口等，另一个结构体是list，我们类比为街道，里面储存了街道上第一个房屋和最后一个房屋的位置，即头尾指针，而街道内的每一个房屋都有一个路牌，它指向下一个房屋的位置，这就是next指针。
? ? ? ? 那么接下来就是双链表的讲解，双链表就是在单链表next指针的基础上增加了一个prev指针，作用就是用来指向上一个node，有了双链表，c语言的用法会灵活许多，在后续讲解图论时大家会有明显的感受。
? ? ? ? 首先给出双链表的两个核心结构体：
typedef struct node {
struct node *prev; //前指针
struct node *next; //后指针
char *data;
} Node;
typedef struct dll {
Node *tail; //头指针
Node *head; //尾指针
} Dll;
????????从本质上来讲，单双链表的意义上相同的，所以如果单链表能理解，双链表就特别容易理解 了，我用一个手画草图来演示：
? ? ? ? ?这样就非常直观了是不是？
? ? ? ? 那么废话不多说，我们直接开始讲解在使用双链表时常用的几大操作。注意，具体操作细节都在注释内。
基础部分：
1. 街道创建（list的创建）
Dll *DLL_create() {
Dll *new_list = malloc(sizeof(Dll));
new_list->head = new_list->tail = NULL; //一定要记得初始化
return new_list;
}?
2.房屋创建（node的创建）
//如果要在链表内储存字符串类型的信息，就必须用复制的方法传入信息
char *copyString(char *value) {
char *data = malloc(sizeof(char) * (strlen(value) + 1));
strcpy(data, value);
return data;
}
Node *create_new_house(char *value) {
Node *new_house = malloc(sizeof(Node));
new_house->next = NULL;
new_house->prev = NULL; //同样不要忘记这里的初始化（类似于单列表中设置每个新的房子单指针是NULL）
//再次强调，因为data是字符串，不能用直接传入的方法，而应该用复制的方法传入数据，故才有了以下再次使用malloc的过程
new_house->data = copyString(value); //复制字符串
return new_house;
}
3.插入新的node至链表的头/尾/中间
? ? ? ? 首先也是我先用手画图帮大家理解一下，然后我们再看代码。
????????首先无论是插入到哪里，我们都要先通过刚刚写出来的create_new_house函数创建一个全新的初始化后的node，然后：
????????这是插入到双链表末端的示意图：
????????大体思路就是先用新的node的prev指针指向链表的tail，在用tail的next指针指向这个新的node，最后吧tail的位置挪到这个新的node的位置即可。
? ? ? ? ?插入到开头也是同理：
????????先用新的node的next指针指向链表的head，在用head的prev指针指向这个新的node，最后吧head的位置挪到这个新的node的位置即可。?
? ? ? ? 接下来是代码展示：
//末尾插入链表 Dll *DLL_append(Dll *list, char *value) { if (list != NULL) { //需要check链表的头、尾和中间 if (list->head == NULL) { //这是指目前链表内还没有任何node Node *new_house = create_new_house(value); new_house->data[strlen(value)] = '\0'; //以防不同电脑的系统差异，应该在字符串最后强制加一个空字符串 list->head = new_house; list->tail = new_house; } else { Node *need_insert_house = create_new_house(value); //重点！！！ need_insert_house->prev = list->tail; list->tail->next = need_insert_house; list->tail = need_insert_house; } } return list; } //开头插入链表 Dll *DLL_prepend(Dll *list, char *value) { if (list != NULL) { if (list->head == NULL) { list->head = list->tail = create_new_house(value); } else { Node *new_house = create_new_house(value); new_house->next = list->head; list->head->prev = new_house; list->head = new_house; } } return list; }//寻找到目标字符串后在其前面插入新的链表，如果找不到目标就插入到最开头（类似于插到中间，大家可以自行简化） void DLL_insertBefore(Dll *list, char *target, char *value) { Node *target_list = is_exist(list, target); //这里是判断目标node是否存在，进阶部分会讲解这个函数 if (target_list == NULL) { DLL_prepend(list, value); //未找到，插入到最后 } else { Node *new_list = create_new_house(value); if (target_list == list->head) { //要额外考虑目标是头指针的情况 list->head = new_list; new_list->prev = target_list->prev; target_list->prev = new_list; new_list->next = target_list; } else { //这里就是目标node在中间的情况了（理解不了就根据代码画图！！！） target_list->prev->next = new_list; //注意，这四个的顺序不能错！ new_list->next = target_list; new_list->prev = target_list->prev; target_list->prev = new_list; } } }
4.删除头/尾的node
????????如果已经掌握了插入的方法，那么删除就特别好理解了。但是这里有一个特殊情况要注意，就是一定要多加一个判断来判断链表内是否只有一个node，如果只有一个node，在free掉这个node后一定一定一定要记得重新初始化链表的头尾指针为NULL，不然后续的程序会报错。
? ? ? ? 上代码（我这里的程序是删除并且返回被删除的内容，大家可以根据需求自行修改）：
//显示最后元素并删除
char *DLL_shrink(Dll *list) {
char *result = NULL;
if (list != NULL && list->head != NULL) {
//判断是否只有一个的方法是判断head是否等于tail
if (list->head == list->tail) {
Node *delete_house = list->tail;
result = copyString(delete_house->data);
list->head = list->tail = NULL;//千万记得加不然会变成野指针
free(delete_house);
return result;
} else {
Node *delete_house = list->tail;
delete_house->prev->next = delete_house->next; //意思是把tail的上一位的next设置为NULL
list->tail = delete_house->prev; //把tail往前挪一位
result = delete_house->data;
free(delete_house);
return result;
}
} else {
return NULL;
}
}
//显示开头元素并删除
char *DLLshift(Dll *list) {
char *result = NULL;
if (list != NULL && list->head != NULL) {
//判断是否只有一个的方法是判断head是否等于tail
if (list->head == list->tail) {
Node *delete_house = list->tail;
result = copyString(delete_house->data);
list->head = list->tail = NULL;//记得初始化不然会报错，而且很难排查！
free(delete_house);
return result;
} else {
Node *delete_house = list->head;
delete_house->next->prev = delete_house->prev; //意思是把原第一位设置为NULL
list->head = delete_house->next; //head往后挪一位
result = delete_house->data;
free(delete_house);
return result;
}
} else {
return NULL;
}
}
进阶部分 ：
1.复制链表
????????中心思想是创建一个新的list，然后找到被复制链表的头指针，在循环下不断调用末尾插入函数插入被复制链表的node内容，完成复制。
Dll *DLL_copy(Dll *list) {
Dll *new_list = NULL;
if (list != NULL) {
new_list = DLL_create();
Node *find_last = list->head;
while (find_last != NULL) {
DLL_append(new_list, find_last->data);
find_last = find_last->next;
}
}
return new_list;
}
2.翻转链表
? ? ? ? 把链表内容整个翻转。在写的时候一定要注意分析node个数的奇偶。主要思路是tail指针不停指向下一个，prev不停指向上一个，在奇数个node时，head和tail会相遇；如果是偶数个那么head->next == ?tail 和 tail->prev == head这两种情况会相等，相遇就是函数的循环终止条件，在终止前不停交换头尾数据即可。
Dll *DLL_reverse(Dll *list) {
if (list != NULL && list->head != NULL) {
Node *head = list->head;
Node *tail = list->tail;
while (true) {
//针对奇数
if (head == tail) {
break;
}
char *exchange = head->data;
head->data = tail->data;
tail->data = exchange;
//针对偶数
if (head->next == tail) {
break;
}
head = head->next;
tail = tail->prev;
}
}
return list;
}
3.判断链表是否有按顺序排列
? ? ? ? 这里以字符串举例所以要用到strcmp函数。以下三个函数特别易懂，就不多做解释了。直接看代码吧。? ??
bool DLLisOrdered(Dll *list) {
bool result = true;
if (list != NULL && list->head != NULL) {
Node *first_element = list->head;
while (first_element != NULL && first_element->next != NULL) {
if (strcmp(first_element->data, first_element->next->data) > 0{
return false;
}
first_element = first_element->next;
}
}
return result;
}
4.用于判断目标node是否存在
Node *is_exist(Dll *list, char *target) {
Node *final_list = NULL;
if (list != NULL && list->head != NULL) {
Node *find_target = list->head;
while (find_target != NULL) {
if (strcmp(find_target->data, target) == 0) {
final_list = find_target;
break;
}
find_target = find_target->next;
}
}
return final_list;
}
5.找到目标字符串后将其内容替换
void DLL_replace(Dll *list, char *target, char *value) {
if (list != NULL && list->head != NULL) {
Node *find_target = list->head;
while (find_target != NULL) {
if (strcmp(find_target->data, target) == 0) {
find_target->data = copyString(value);
break;
}
find_target = find_target->next;
}
}
}
高级部分：
? ? ? ? 如果到这里都看懂了，其实链表也就掌握的差不多了，当然这只是C语言的，C++会更复杂大家可以查阅其他资料。
? ? ? ? 剩下还有两个链表方法想和大家分享，其实也不是特别高级，只是略微比前面复杂一点点。
1.链表内容排序
? ? ? ? 排序的各种方法相信大家都耳熟能详了，这里选用的是冒泡排序。
Dll *DLL_sort(Dll *list) {
????//这个是记录node数量的函数，太简单就不单独写了
size_t length = DLL_length(list);
Node *pre_list = list->head; //使用快慢指针
Node *cur_list = pre_list->next;
????//以下为冒泡排序的算法内容，这个就不多做解释了
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (strcmp(cur_list->data, pre_list->data) < 0) {
char *exchange = pre_list->data;
pre_list->data = cur_list->data;
cur_list->data = exchange;
}
if (cur_list->next != NULL)
cur_list = cur_list->next;
}
if (pre_list->next != NULL) { //这一步的目的是为了归位
pre_list = pre_list->next;
cur_list = pre_list->next;
}
}
return list;
}
2.有序的不重复的插入链表内容
????????这个是对之前的链表插入函数的改良，用这个函数时当你插入node时会一边插入一边自动排序。这个函数在图论中会用到。同时在图论里我还会补充插入子链表的知识点，有兴趣的可以关注一下我更新图论以及后续字符串匹配的知识点！
void list_append_by_order(list l, string item) {
????????//这个contain就相当于之前的exist函数，用于避免重复的情况
if (l != NULL && list_contains(l, item) == false){
if (l->head == NULL) {
l->head = l->tail = create_node(item);
l->length++;
} else if (strcmp(item, l->head->data) < 0) { //比第一个数小的情况
list_push(l, item);
l->length++;
} else if (strcmp(item, l->tail->data) > 0) { //比最后一个数大的情况
Node newNode = create_node(item);
newNode->prev = l->tail;
l->tail->next = newNode;
l->tail = newNode;
l->length++;
} else { //在中间，但这里不考虑有重复元素
Node temp = l->head;
while (temp != NULL && temp->next != NULL) {
if (strcmp(item, temp->data) > 0 && strcmp(item, temp->next->data) < 0) {
Node newNode = create_node(item);
newNode->next = temp->next;
newNode->prev = temp;
temp->next->prev = newNode;
temp->next = newNode;
l->length++;
break;
}
}
}
}
}
????????谢谢浏览！编程小白会继续努力给大家分享的！！！