数据结构————双链表

一、单链表的定义及其特点

定义：

特点：

双链表的优缺点

双链表的关键特性

二、双链表的实现

准备工作：

自定义数据元素类型：

1.双链表的创建

1.1头插法介绍

1.2尾插法介绍

2.双链表的初始化

3.双链表的求表长

4.双链表的销毁

5.双链表的遍历

6.双链表的查找

6.1按值查找

6.2按序查找

7.双链表的插入

8.双链表的删除元素

全部代码（含测试）：

总结：

一、单链表的定义及其特点

定义：

双链表，顾名思义，是一种链式存储结构，其中每个节点不仅包含数据元素，还包含两个指针，分别指向其前驱和后继节点。

为什么引入双链表？

单链表的结点中只有一个指向其后继的指针，使得单链表要访问某个结点的前驱结点时，只能从头开始遍历，访问后驱结点的复杂度为O(1)，访问前驱结点的复杂度为O(n)。为了克服上述缺点，引入了双链表。

特点：

双链表的优缺点

优点：

可以在O(1)时间复杂度下在已知节点位置进行插入和删除操作。
双向遍历，适用于需要频繁从两端访问数据的场景。

缺点：

额外的存储空间需求，每个节点需要两个指针。
比单链表更复杂的实现和维护。

双链表的关键特性

双向性：每个节点都有两个指针，一个指向前一个节点，另一个指向后一个节点。
灵活性：可以在链表的任何位置插入或删除节点，而不仅仅是链表的尾部。
额外空间：相比单链表，双链表需要额外的空间来存储前驱指针，但这种开销通常被认为是值得的，因为它提供了额外的灵活性和性能提升。

其它

数据安全性：由于每个节点都有指向前后节点的指针，即使某个节点的指针损坏，也能通过其他节点恢复链表结构，增加了数据的可靠性。
应用场景的拓展： 双链表因其双向性和操作效率，在文件系统、缓存管理、浏览器历史记录等领域有着广泛的应用。例如，浏览器历史记录中，用户可以方便地前后浏览，这正是利用了双链表的双向访问特性。
算法实现的简化： 在实现某些算法时，双链表可以简化代码。例如，在需要频繁进行反转、反转部分子链表或在链表中查找元素的前一个或后一个元素等操作时，双链表的双向特性可以简化算法实现，减少代码复杂度。

二、双链表的实现

准备工作：

自定义数据元素类型：

typedef int ElemType;

1.双链表的创建

双链表的创建通常涉及两种主要的插入方法：头插法和尾插法。

1.1头插法介绍

头插法指的是在双链表的头部插入节点，

特点

但链表元素的顺序与插入顺序相反，如果需要保持原有顺序，需要在插入后进行反转

代码：

//<1>头插法建立双链表
void CreateListF(DLinkNode*& L, ElemType a[], int n)
{DLinkNode* s;//待插入结点//（1）创建头结点L = (DLinkNode*)malloc(sizeof(DLinkNode));L->next = L->prior = NULL;//(2） 插入操作for (int i = 0; i < n; i++){s= (DLinkNode*)malloc(sizeof(DLinkNode));s->data = a[i];s->next = L->next;//第一步：新结点的next指向第一个结点if (L->next != NULL)//第二步，第一个结点的前驱结点指向新结点L->next->prior = s;L->next = s;//第三步修改头结点的nexts->prior = L;//最后修改新结点的前驱结点}
}

1.2尾插法介绍

尾插法指的是在链表的尾部插入节点。此方法下，新节点成为链表的最后一个节点。

特点

保持了数据的插入顺序，链表元素的顺序与插入顺序一致。

代码：

//<2>尾插法建立双链表
void CreateListR(DLinkNode*& L, ElemType a[], int n)
{DLinkNode* s, * r;L = (DLinkNode*)malloc(sizeof(DLinkNode));L->next = L->prior = NULL;r = L;//r始终指向尾结点，开始指向Lfor (int i = 0; i < n; i++){s= (DLinkNode*)malloc(sizeof(DLinkNode));s->data = a[i];r->next = s;//第一步将尾部节点的后继指针指向新结点s->prior = r;//第二步将新结点的前驱指针指向尾部节点r = s;//最后移动尾指针}r->next = NULL;
}

2.双链表的初始化

创建一个头结点，并将其头结点的next域置空

void InitList(DLinkNode*& L)
{L = (DLinkNode*)malloc(sizeof(DLinkNode));L->next = L->prior = NULL;
}

3.双链表的求表长

用p指向头结点，用n来累计数据节点的个数，n初始值为0；

//【4】求表长
int  ListLength(DLinkNode* L)
{int j = 1;DLinkNode* p = L->next;while (p->next!=NULL){j++;p = p->next;}return j;
}

4.双链表的销毁

1. pre 和 p指向相邻的节点，初始pre 指向头结点，p指向首个数据节点。

2.p不为空时循环，释放pre节点，然后pre 和p 俩个节点后移。

3. 循环结束后pre指向尾节点，将其释放

代码：

//【3】双链表的销毁
void DeleteList(DLinkNode*& L)
{DLinkNode* pre, * p;pre = L; p = L->next;while (p != NULL){free(pre);pre = p;p = p->next;}free(pre);
}

5.双链表的遍历

遍历双链表，p指向L的第一个结点（L->next）

代码：

void PrintList(DLinkNode* L)
{DLinkNode* p = L->next;while (p){printf("%d->",p->data);p = p->next;}printf("end\n");
}

6.双链表的查找

6.1按值查找

与单链表的按值查找是一致的，在L中查找第一个出现元素为e的结点。

代码：

//<1>按值查找 查找值e在L中的第一个出现位置
DLinkNode* LocateElem(DLinkNode* L, ElemType e,int& n)
{n = 1;DLinkNode* p = L->next;while (p!=NULL&&p->data!=e){n++;p =p->next;}if (p==NULL){return NULL;}else{return p;}
}

6.2按序查找

与单链表的按序查找是一致的，在L中查找序号为i的结点，并返回该结点。

代码：

//<2>按序查找
DLinkNode* GetElem(DLinkNode* L, int i) 
{int j = 0;DLinkNode* p = L->next;if (i <= 0)return NULL;while (j < i - 1&&p!=NULL){j++;p = p->next;}if (p != NULL){return p;}else{return NULL;}
}

7.双链表的插入

给定双链表L ,在第i个位置插入节点s（即放在i-1个结点的前面），值为e。

我们定义结点 p指针用于找到第i-1个结点，s是待插入的结点。

实现示意图如下：

值得注意的是，当我们插入的结点是最后一个结点的后面时，我们要判断p的后继结点是否存在

代码：

//【8】插入 
bool ListInsert(DLinkNode*& L, int i, ElemType e)
{DLinkNode* s, * p = L;int j = 0; if (i <= 0)return NULL;//第一步，找到第i-1个结点while (p != NULL && j < i - 1){j++;p = p->next;}if (p == NULL){return false;}else//插入操作{s = (DLinkNode*)malloc(sizeof(DLinkNode));s->data = e;s->next = p->next;//1if(p->next!=NULL)//如果p的后继结点存在，允许修改前驱指针（处理插入尾结点后面的情况）p->next->prior = s;//2s->prior = p;//3p->next = s;//4return true;}
}

8.双链表的删除元素

给定双链表L，删除第i个节点，并将删除节点的值带回，p指向第i-1个节点,q为第i个节点

示意图：

同样，我们也因该考虑删除最后一个结点时，由于要修改第i个结点的后继的结点的前驱指针（上图的2号操作），我们要判断q的后继结点是否存在

代码：

//【9】删除 删除第 i 个结点
bool  ListDelete(DLinkNode*& L, int i, ElemType& e)
{if (i <= 0)return false;DLinkNode* p=L;//p用于指向i-1个结点DLinkNode* q;// q用于指向第i个结点int j = 0;while (j < i - 1 && p != NULL){j++;p = p->next;}if (p == NULL){return false;}else{q = p->next;if (q == NULL)return false;  //不存在第i个结点e =q->data;if(q->next!=NULL)//如果q的后继结点存在，修改后继结点的前驱指针q->next->prior = p;//1p->next = q->next;//2free(q);return true;}
}

全部代码（含测试）：

#include<stdio.h>
#include<stdlib.h>typedef  int  ElemType;
typedef struct DNode {ElemType data;//数据域struct DNode* prior,* next;//前驱指针和后驱指针
}DLinkNode,*DLinkList;
/*【1】双链表的建立*/
//<1>头插法建立双链表
void CreateListF(DLinkNode*& L, ElemType a[], int n)
{DLinkNode* s;//待插入结点//（1）创建头结点L = (DLinkNode*)malloc(sizeof(DLinkNode));L->next = L->prior = NULL;//(2） 插入操作for (int i = 0; i < n; i++){s= (DLinkNode*)malloc(sizeof(DLinkNode));s->data = a[i];s->next = L->next;//第一步：新结点的next指向第一个结点if (L->next != NULL)//第二步，第一个结点的前驱结点指向新结点L->next->prior = s;L->next = s;//第三步修改头结点的nexts->prior = L;//最后修改新结点的前驱结点}
}
//<2>尾插法建立双链表
void CreateListR(DLinkNode*& L, ElemType a[], int n)
{DLinkNode* s, * r;L = (DLinkNode*)malloc(sizeof(DLinkNode));L->next = L->prior = NULL;r = L;//r始终指向尾结点，开始指向Lfor (int i = 0; i < n; i++){s= (DLinkNode*)malloc(sizeof(DLinkNode));s->data = a[i];r->next = s;//第一步将尾部节点的后继指针指向新结点s->prior = r;//第二步将新结点的前驱指针指向尾部节点r = s;//最后移动尾指针}r->next = NULL;
}/*双链表的基本运算*///【2】双链表的初始化void InitList(DLinkNode*& L)
{L = (DLinkNode*)malloc(sizeof(DLinkNode));L->next = L->prior = NULL;
}
//【3】双链表的销毁
void DeleteList(DLinkNode*& L)
{DLinkNode* pre, * p;pre = L; p = L->next;while (p != NULL){free(pre);pre = p;p = p->next;}free(pre);
}
//【4】求表长
int  ListLength(DLinkNode* L)
{int j = 1;DLinkNode* p = L->next;while (p->next!=NULL){j++;p = p->next;}return j;
}
//【5】判断是否为空
bool ListEmpty(DLinkNode*L)
{return (L->next == NULL);
}
//【6】遍历双链表
void PrintList(DLinkNode* L)
{DLinkNode* p = L->next;while (p){printf("%d->",p->data);p = p->next;}printf("end\n");
}
//【7】查找
//<1>按值查找 查找值e在L中的第一个出现位置
DLinkNode* LocateElem(DLinkNode* L, ElemType e,int& n)
{n = 1;DLinkNode* p = L->next;while (p!=NULL&&p->data!=e){n++;p =p->next;}if (p==NULL){return NULL;}else{return p;}
}
//<2>按序查找
DLinkNode* GetElem(DLinkNode* L, int i)
{int j = 0;DLinkNode* p = L->next;if (i <= 0)return NULL;while (j < i - 1&&p!=NULL){j++;p = p->next;}if (p != NULL){return p;}else{return NULL;}
}
//【8】插入 
bool ListInsert(DLinkNode*& L, int i, ElemType e)
{DLinkNode* s, * p = L;int j = 0; if (i <= 0)return NULL;//第一步，找到第i-1个结点while (p != NULL && j < i - 1){j++;p = p->next;}if (p == NULL){return false;}else//插入操作{s = (DLinkNode*)malloc(sizeof(DLinkNode));s->data = e;s->next = p->next;//1if(p->next!=NULL)//如果p的后继结点存在，允许修改前驱指针p->next->prior = s;//2s->prior = p;//3p->next = s;//4return true;}
}
//【9】删除 删除第 i 个结点
bool  ListDelete(DLinkNode*& L, int i, ElemType& e)
{if (i <= 0)return false;DLinkNode* p=L;//p用于指向i-1个结点DLinkNode* q;// q用于指向第i个结点int j = 0;while (j < i - 1 && p != NULL){j++;p = p->next;}if (p == NULL){return false;}else{q = p->next;if (q == NULL)return false;  //不存在第i个结点e =q->data;if(q->next!=NULL)//如果q的后继结点存在，修改后继结点的前驱指针q->next->prior = p;//1p->next = q->next;//2free(q);return true;}
}int main()
{//尾插法建立双链表，并遍历单链表DLinkList L1 ,L2 ,L3;InitList(L3);//初始化int a[5] = { 1,2,3,4,5 };int b[5] = { 11 ,66, 12,44,55 };CreateListF(L1, a, 5);//头插法建立链表L1CreateListR(L2, b, 5);//尾插法建立链表L2if (ListEmpty(L3))//判空printf("L3为空\n");//输出PrintList(L1);PrintList(L2);//按值查找DLinkNode* p;//按值查找int n;p = LocateElem(L1, 2,n);if(p!=NULL){ printf("值为2的结点的序号为是：%d\n",n);printf("值为2的结点的下一个结点值是：%d\n" , p->next->data);printf("值为2的结点的上一个结点值是：%d\n", p->prior->data);}else{printf("无效查找\n");}//按位查找p = GetElem(L2, 3);if (p != NULL){printf("L2第三个结点值是：%d\n", p->data);}else{printf("无效查找\n");}//插入操作ListInsert(L1,6,99);printf( "在第6个结点插入值为99后L1： ");PrintList(L1);//删除操作int e;ListDelete(L1,5,e);printf( "删除第五个结点后L1： ");PrintList(L1);printf("删除的值为%d\n", e);//求表长printf("L1长为：%d" ,ListLength(L1) );printf("\n");printf("L2长为：%d", ListLength(L2));printf("\n");DeleteList(L1);DeleteList(L2);return 0;
}