【数据结构与算法】双向链表

链表的分类

在我们平时的学习中，最常用的两种链表：

无头单向非循环链表

带头双向循环链表

head的是哨兵位头结点，不存储数据

下文主要讲解第二种带头双向链表

创建结构体

双向链表中，每个结点除了包含下个节点的地址外，还包含前一个结点的地址，因此我们需要分别创建两个指针next和prev

创建结构体代码

typedef int LTDataType;typedef struct ListNode{struct ListNode* next;struct ListNode* prev;LTDataType data;}ListNode;

链表初始化

方法一：要完成初始化，我们需要把phead的地址传给相应的初始化函数，只有址传递才能改变phead的值，下面例子则是错误的：

下面我们来看看调用部分的phead和传入函数后的phead的地址是否相同

调用部分的phead地址如下

传入函数后的phead的地址如下

可见此时phead的地址不一样，因此无法对传入的phead指针变量进行修改，正确的操作应该是传入phead的地址，如下图

此时传入的即为指针变量的地址，可以实现对传入指针变量的修改（初始化）了

初始化函数代码(方法一)

//初始化链表void ListInit(ListNode** pphead){*pphead = BuyListNode(0);(*pphead)->next = *pphead;(*pphead)->prev = *pphead;return pphead;}

**方法二：**这种方法比较简单，不用传入二级指针，直接返回初始化函数创建的头结点赋值给phead即可完成初始化

ListNode* phead = ListInit();

初始化函数代码(方法二)

//初始化链表ListNode* ListInit(){ListNode* phead = BuyListNode(0);phead->next = phead;phead->prev = phead;return phead;}

清理数据结点

指针cur指向当前要清理的结点，next用于保存下一个待清理结点的地址

cur==phead的时候的时候，结束清理，且对phead初始化,以确保头结点继续使用

phead->next = phead;phead->prev = phead;

清理数据结点代码

void ListClear(ListNode* phead){assert(phead);//清理所有数据结点，保留头结点，可以继续使用ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}phead->next = phead;phead->prev = phead;}

销毁链表

上面我们讲的是对链表的结点进行清理，但如果这个链表不再使用时，需要将头结点也一起销毁

销毁链表代码

//销毁链表void ListDestroy(ListNode* phead){assert(phead);ListClear(phead);free(phead);}

创建新结点

ListNode* BuyListNode(LTDataType x){ListNode*node = (ListNode*)malloc(sizeof(ListNode));//初始化node->next = NULL;node->prev = NULL;node->data = x;return node;}

链表的打印

​ 思路：

结束条件和单链表不一样，单链表是在打印结点指向NULL时结束打印，但现在是循环链表，不存在指向NULL的问题，因此，结束条件可改为当cur(进行结点打印的指针)等于phead时结束打印

头结点phead是哨兵位结点，不储存信息，因此从phead的下一个指针开始打印

链表的打印代码

assert(phead);ListNode* cur = phead->next;while (cur != phead) //结束条件{print("%d ", cur->data);cur = cur->next;}

尾插

进行尾插，首先要找到尾结点，由上图可知双链表头结点的prev指针指向的就是尾结点

ListNode* tail = phead->prev;

尾结点找到后，我们来插入新的结点，首先我们将新结点和尾结点进行链接，如下图红色箭头

tail->next = newnode;newnode->prev = tail;

头结点与新结点链接

newnode->next = phead;phead->prev = newnode;

尾插代码

//尾插void ListPushBack(ListNode* phead, LTDataType x){assert(phead); //断言，头指针不指向NULLListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);//进行结点的链接tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

尾删

思路：

确定尾结点

ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;

tailPrev指向的结点与头结点进行链接

phead->prev = tailPrev;tailPrev->next = phead;

删除尾结点

尾删代码

//尾删void ListPopBack(ListNode* phead){assert(phead);if (phead->next == phead) //判断是否只有哨兵位头结点{return phead;}else{ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;phead->prev = tailPrev;tailPrev->next = phead;free(tail);return phead;}}

头插

头插是指在哨兵位头结点的后面插入

思路：

定义first指针用于储存原链表中phead的后一个结点

新结点与phead链接

phead->next = newnode;newnode->prev = phead;

新结点与first链接,头插结束

newnode->next = first;first->prev = newnode;

头插代码

//头插void ListPushFront(ListNode* phead, LTDataType x){assert(phead);ListNode* first = phead->next;ListNode* newnode = BuyListNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

头删

把哨兵位结点的后一个结点删除

创建两个指针first和second

ListNode* first = phead->next;ListNode* second = first->next;

phead与second链接,删除first

phead->next = second;second->prev = phead;free(first);

头删代码

//头删void ListPopFront(ListNode* phead){assert(phead);assert(phead->next!=phead);ListNode* first = phead->next;ListNode* second = first->next;phead->next = second;second->prev = phead;free(first);}

链表的查找

查找只要对链表遍历即可,逻辑和打印链表相似，直接上代码

链表的查找代码

//查找ListNode* ListFind(ListNode* phead, int x){assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}

插入（任意结点）

要在给定结点的前面插入（例如在d2前插入），就要先得到这个给定结点的位置，那么用查找函数确定这个结点的位置pos

后面的插入和前面所提到到两种插入大同小异，这里就不赘述了

插入（任意结点）代码

//插入（任意位置）void ListInsert(ListNode* pos, LTDataType x){assert(pos);ListNode* posPrev = pos->prev;ListNode* newnode = BuyListNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;}

删除（任意结点）

删除（任意结点）代码

//删除（任意位置）void ListErase(ListNode* pos){assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;}

双链表完整代码

List.h文件

#pragma once#include<stdio.h>#include<assert.h>#include<stdlib.h>typedef int LTDataType;typedef struct ListNode{struct ListNode* next;struct ListNode* prev;LTDataType data;}ListNode;//void ListInit(ListNode** phead);ListNode* ListInit();void ListClear(ListNode* phead);void ListDestroy(ListNode* phead);ListNode* BuyListNode(LTDataType x);void ListPrint(ListNode* phead);void ListPushBack(ListNode* phead, LTDataType x);void ListPopBack(ListNode* phead);void ListPushFront(ListNode* phead, LTDataType x);void ListPopFront(ListNode* phead);ListNode* ListFind(ListNode* phead, int x);void ListInsert(ListNode* pos, LTDataType x);void ListErase(ListNode* pos);

List.c文件

#include "List.h"//初始化链表ListNode* ListInit(){ListNode* phead = BuyListNode(0);phead->next = phead;phead->prev = phead;return phead;}//创建新结点ListNode* BuyListNode(LTDataType x){ListNode*node = (ListNode*)malloc(sizeof(ListNode));node->next = NULL;node->prev = NULL;node->data = x;return node;}//清理数据结点void ListClear(ListNode* phead){assert(phead);//清理所有数据结点，保留头结点，可以继续使用ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}phead->next = phead;phead->prev = phead;}//销毁链表void ListDestroy(ListNode* phead){assert(phead);ListClear(phead);free(phead);}//打印void ListPrint(ListNode* phead){assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");}//尾插void ListPushBack(ListNode* phead, LTDataType x){assert(phead); //断言，头指针不指向NULLListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);//进行结点的链接tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}//尾删void ListPopBack(ListNode* phead){assert(phead);if (phead->next == phead) //判断是否只有哨兵位头结点{return phead;}else{ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;phead->prev = tailPrev;tailPrev->next = phead;free(tail);return phead;}}//头插void ListPushFront(ListNode* phead, LTDataType x){assert(phead);ListNode* first = phead->next;ListNode* newnode = BuyListNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}//头删void ListPopFront(ListNode* phead){assert(phead);assert(phead->next!=phead);ListNode* first = phead->next;ListNode* second = first->next;phead->next = second;second->prev = phead;free(first);}//查找ListNode* ListFind(ListNode* phead, int x){assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}//插入（任意位置）void ListInsert(ListNode* pos, LTDataType x){assert(pos);ListNode* posPrev = pos->prev;ListNode* newnode = BuyListNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;}//删除（任意位置）void ListErase(ListNode* pos){assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;}

test.c

#include "List.h"void TestList1(){ListNode* phead = ListInit();ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPrint(phead);ListPopBack(phead);ListPopBack(phead);ListPopBack(phead);ListPopBack(phead);ListPopBack(phead);ListPrint(phead);ListPushFront(phead, 1);ListPushFront(phead, 2);ListPushFront(phead, 3);ListPushFront(phead, 4);ListPushFront(phead, 5);ListPrint(phead);ListPopFront(phead);ListPopFront(phead);ListPopFront(phead);ListPopFront(phead);ListPopFront(phead);ListPrint(phead);ListDestroy(phead);}void TestList2(){ListNode* phead = ListInit();ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPrint(phead);ListNode* pos = ListFind(phead, 3);ListInsert(pos, 30);ListPrint(phead);pos = ListFind(phead, 3);ListErase(pos);ListPrint(phead);ListDestroy(phead);}void main(){//TestList1();TestList2();}