数据结构——双向链表

文章目录

双向链表
- 概念
- 初始化
- 插入节点
- 剔除节点
- 链表的遍历
- 修改链表
- 销毁链表
- 完整案例
- 适用场合

双向链表

概念

对链表而言，双向均可遍历是最方便的，另外首尾相连循环遍历也可大大增加链表操作的便捷性。因此，双向循环链表，是在实际运用中是最常见的链表形态。

请添加图片描述

基本操作

与普通的链表完全一致，双向循环链表虽然指针较多，但逻辑是完全一样。基本的操作包括：

节点设计
初始化空链表
增删节点
链表遍历
销毁链表

节点设计

双向链表的节点只是比单向链表多了一个前向指针。示例代码如下所示：

typedef int DATA;
typedef struct node
{// 以整型数据为例DATA data;// 指向相邻的节点的双向指针struct node *prev;struct node *next;
}NODE;

初始化

所谓初始化，就是构建一条不含有效节点的空链表。

以带头结点的双向循环链表为例，初始化后，其状态如下图所示：

请添加图片描述

在初始空链表的情况下，链表只有一个头结点，下面是初始化示例代码：

int dlist_create(NODE** head,DATA data)
{// 创建新节点（申请内存空间）NODE *pNew = (NODE*)malloc(sizeof(NODE));if(!pNew)return -1;// 给节点赋初值pNew -> data = data;// 前后指针默认都指向NULLpNew -> prev = pNew -> next = NULL;// 将新节点作为头节点*head = pNew;return 0;
}

插入节点

与单链表类似，也可以对双链表中的任意节点进行增删操作，常见的有所谓的头插法、尾插法等，

即：将新节点插入到链表的首部或者尾部，示例代码是：

头插法：新节点插入到链表的头部

// 将新节点pNew，插入到链表的首部
int dlist_addHead(NODE** head,DATA data)
{// 创建新节点并申请内存NODE *pNew = (NODE*)malloc(sizeof(NODE));if(!pNew)return -1;// 给新节点赋值pNew -> data = data;pNew -> prev = NULL;// 后针指向头指针pNew -> next = *head;// 如果头指针存在if(*head)// 头指针的前指针指向新节点(*head) -> prev = pNew;// 新插入的节点作为新的头节点*head = pNew;return 0;
}

尾插法

// 将新节点pNew，插入到链表的尾部
int dlist_addTail(NODE **head, DATA data)
{// 创建节点并申请内存NODE *pNew = (NODE *)malloc(sizeof(NODE));if (!pNew)return -1;// 初始化节点pNew->data = data;pNew->prev = NULL;pNew->next = NULL;// 用来记录尾节点，默认头节点就是尾节点NODE *p = *head;if (!p){// 头节点不存在，新插入的节点作为头节点*head = pNew;return 0;}// 通过循环，查找尾节点while (p->next){p = p->next;}// 尾节点的后指针指向新插入的节点p->next = pNew;// 新插入的节点的前指针指向尾节点pNew->prev = p;// 此时的新节点作为了新的尾节点return 0;
}

中间插法：将新节点插入到链表的指定位置

// 将新节点pNew，插入到链表的指定位置
int dlist_insert(NODE** head,DATA pos,DATA data)
{NODE *pNew = (NODE*)malloc(sizeof(NODE));if(!pNew)return -1;pNew -> data = data;pNew -> prev = NULL;pNew -> next = NULL;NODE* p = *head, *q = NULL;if(!p){*head = pNew;return 0;}if(memcmp(&(p -> data),&pos,sizeof(DATA)) == 0){pNew -> next = p;p -> prev = pNew;*head = pNew;return 0;}while(p){if(memcmp(&(p -> data),&pos,sizeof(DATA)) == 0){pNew -> next = p;pNew -> prev = q;p -> prev = pNew;q -> next = pNew;return 0;}q = p;p = p -> next;}q -> next = pNew;pNew -> prev = q;return 0;
}

剔除节点

注意，从链表中将一个节点剔除出去，并不意味着要释放节点的内容。当然，我们经常在剔除了一个节点之后，紧接着的动作往往是释放它，但是将“剔除”与“释放”两个动作分开，是最基本的函数封装的原则，因为它们虽然常常连在一起使用，但它们之间并无必然联系，例如：当我们要移动一个节点的时候，实质上就是将“剔除”和“插入”的动作连起来，此时就不能释放该节点了。

在双向链表中剔除指定节点的示例代码如下：

// 将data对应的节点从链表中剔除
int dlist_delete(NODE** head,DATA data)
{NODE* p = *head;if(!p)return -1;if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0){if(p -> next == NULL){*head = NULL;free(p);return 0;}*head = p -> next;p -> next -> prev = NULL;free(p);return 0;}while(p){if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0){p -> prev -> next = p -> next;if(p -> next == NULL)p -> prev -> next = NULL;elsep -> next -> prev = p -> prev;free(p) ;return 0;}p = p -> next;}return -1;
}

链表的遍历

对于双向循环链表，路径可以是向后遍历，也可以向前遍历。

下面是根据指定数据查找节点，向前、向后遍历的示例代码，假设遍历每个节点并将其整数数据输出：

// 根据指定数据查找节点
NODE* dlist_find(const NODE* head,DATA data)
{const NODE* p = head;while(p){if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)return (NODE*)p;p = p -> next;}return NULL;}// 向前|向后遍历
void dlist_showAll(const NODE* head){const NODE* p = head;while(p){printf("%d ",p -> data);p = p -> next;// 向后遍历// p = p -> prev;// 向前遍历}printf("\n");
}

修改链表

我们也可以针对链表中的数据进行修改，只需要提供一个修改的源数据和目标数据即可。

示例代码如下：

int dlist_update(const NODE* head,DATA old,DATA newdata)
{NODE* pFind = NULL;if(pFind = dlist_find(head,old)){pFind -> data = newdata;return 0;}return -1;
}

销毁链表

由于链表中的各个节点被离散地分布在各个随机的内存空间，因此销毁链表必须遍历每一个节点，释放每一个节点。

注意：

销毁链表时，遍历节点要注意不能弄丢相邻节点的指针

示例代码如下：

void dlist_destroy(NODE** head)
{NODE *p = *head, *q = NULL;while(p){q = p;p = p -> next;free(q);}*head = NULL;
}

完整案例

dlist.h

#ifndef __DLIST_H
#define __DLIST_H
typedef int DATA;
typedef struct node
{DATA data;struct node *prev;// 前驱指针struct node *next;// 后继指针
}NODE;
// 创建链表（初始化）
int dlist_create(NODE**,DATA);
// 向链表插入数据（头插法）
int dlist_addHead(NODE** head,DATA data);
// 向链表插入数据（尾插法）
int dlist_addTail(NODE** head,DATA data);
// 向链表插入数据（中间插法）
int dlist_insert(NODE** head,DATA pos,DATA data);
// 链表数据查询
NODE* dlist_find(const NODE* head,DATA data);
// 链表数据更新
int dlist_update(const NODE* head,DATA old,DATA newdata);
// 链表数据遍历
void dlist_showAll(const NODE* head);
// 链表数据删除
int dlist_delete(NODE** head,DATA data);
// 链表回收
void dlist_destroy(NODE** head);
#endif

dlist.c

#include "dlist.h"/*** @function:   int dlist_create(NODE**,DATA);* @berif:      创建双向链表* @argument:   head: 指向头指针变量的地址，用来接收首节点地址*              data: 存储在节点中的数据* @return :    成功返回 0*              失败返回 -1*/
int dlist_create(NODE **head, DATA data)
{// 创建一个节点（申请内存）NODE *pNew = (NODE *)malloc(sizeof(NODE));if (!pNew){perror("内存申请失败！");return -1;}// 节点的初始化pNew->data = data;pNew->prev = pNew->next = NULL; // 给前驱指针和后继指针都赋值为NULL// 将pNew作为头结点*head = pNew;return 0;
}/*** @function:   int dlist_addHead(NODE**,DATA);* @berif:      向链表头部插入数据* @argument:   head: 指向头指针变量的地址，用来接收首节点地址*              data: 存储在节点中的数据* @return :    成功返回 0*              失败返回 -1*/
int dlist_addHead(NODE **head, DATA data)
{// 创建一个节点，申请内存NODE *pNew = (NODE *)malloc(sizeof(NODE));// 校验if (!pNew){perror("内存申请失败！");return -1;}// 给节点赋值pNew->data = data;pNew->prev = NULL;pNew->next = *head;// 如果头结点存在，需要设置head.prev指向pNewif (*head){(*head)->prev = pNew;}// 将pNew作为新的头结点*head = pNew;return 0;
}/*** @function:   int dlist_addTail(NODE**,DATA);* @berif:      向链表尾部插入数据* @argument:   head: 指向头指针变量的地址，用来接收首节点地址*              data: 存储在节点中的数据* @return :    成功返回 0*              失败返回 -1*/
int dlist_addTail(NODE **head, DATA data)
{// 创建一个节点，申请内存NODE *pNew = (NODE *)malloc(sizeof(NODE));if (!pNew){perror("内存申请失败！");return -1;}// 给节点赋初值pNew->data = data;pNew->prev = pNew->next = NULL;// 定义一个变量，用来存储尾结点NODE *p = *head;// 第一种情况：没有节点，pNew作为头结点if (!p){*head = pNew;return 0;}// 第二种情况：有节点，向末尾添加pNewwhile (p->next){// 移动p的位置p = p->next;}// 末尾的p节点跟pNew建立联系，此时pNew称为尾结点p->next = pNew;pNew->prev = p;return 0;
}/*** @function:   int dlist_insert(NODE**,DATA,DATA);* @berif:      向链表任意位置插入数据（中间插法）* @argument:   head: 指向头指针变量的地址，用来接收首节点地址*              pos：目标位置数据*              data: 存储在节点中的数据* @return :    成功返回 0*              失败返回 -1*/
int dlist_insert(NODE **head, DATA pos, DATA data)
{// 创建节点，申请内存NODE *pNew = (NODE *)malloc(sizeof(NODE));if (!pNew){perror("内存申请失败！");return -1;}// 给节点赋初值pNew->data = data;pNew->prev = pNew->next = NULL;NODE *p = *head, *q = NULL;// 第一种情况：没有节点，pNew作为头结点if (!p){*head = pNew;return 0;}// 第二种情况：pos对应的节点刚好是头结点（有效节点是头结点，只有一个节点的时候）if (memcmp(&(p->data), &pos, sizeof(DATA)) == 0){pNew->next = p;p->prev = pNew;*head = pNew;return 0;}// 第三种情况：pos对应的节点不是头结点（有效节点超过两个）while (p) // p 判断当前节点是否为NULL，p->next 判断写一个节点是否为NULL{if (memcmp(&(p->data), &pos, sizeof(DATA)) == 0){pNew->next = p;pNew->prev = q;p->prev = pNew;q->next = pNew;return 0;}// 记录当前位置（上一个节点的位置）q = p;// 记录下一个节点的位置，也就是更新后的pp = p->next;}// 如果在链表中找不到pos对应的节点，就尾插q->next = pNew;pNew->prev = q;return 0;
}/*** @function:   void dlist_showAll(const NODE*);* @berif:      向链表任意位置插入数据（中间插法）* @argument:   head: 指向头指针变量的地址，用来接收首节点地址*              pos：目标位置数据*              data: 存储在节点中的数据* @return :    成功返回 0*              失败返回 -1*/
void dlist_showAll(const NODE *head)
{const NODE *p = head;while (p){printf("%d ", p->data);// 向后遍历p = p->next;// 向前遍历// p = p->prev;}printf("\n");
}/*** @function:   NODE* dlist_find(const NODE*,DATA);* @berif:      链表数据查询（根据指定的数据查找节点）* @argument:   head: 指向头指针变量的地址，用来接收首节点地址*              data: 要检索的数据* @return :    成功返回 NODE**              失败返回 NULL*/
NODE *dlist_find(const NODE *head, DATA data)
{// 创建一个变量去接收链表const NODE *p = head;while (p){if (memcmp(&(p->data), &data, sizeof(DATA)) == 0){return (NODE *)p;}p = p->next;}return NULL;
}//
/*** @function:   dlist_update(const NODE*,DATA,DATA);* @berif:      链表数据更新* @argument:   head: 指向头指针变量的地址，用来接收首节点地址*              old_data：源数据*              new_data: 目标数据* @return :    成功返回 0*              失败返回 -1*/
int dlist_update(const NODE *head, DATA old_data, DATA new_data)
{// 用来接收查询到的节点NODE *pFind = NULL;// 利用刚刚写的查询函数，查询if (!(pFind = dlist_find(head, old_data))){return -1;}// 更新数据pFind->data = new_data;return 0;
}/*** @function:   dlist_delete(NODE**,DATA);* @berif:      链表数据删除* @argument:   head: 指向头指针变量的地址，用来接收首节点地址*              data: 需要删除的数据* @return :    成功返回 0*              失败返回 -1*/
int dlist_delete(NODE **head, DATA data)
{// 记录需要删除的节点的位置NODE *p = *head;// 第一种情况：链表不存在if (!p){return -1;}// 第二种情况：删除的数据对应的节点正好是头结点if (memcmp(&(p->data), &data, sizeof(DATA)) == 0){// 1. 链表中只有一个节点if (p->next == NULL){free(p);*head = NULL;return 0;}// 2. 链表中有两个以上节点// 执行下列代码之前，head和p都指向头结点，下面代码的意思是：将p节点的下一个节点作为新的头结点*head = p->next;// 解除p的引用关系(下一个节点指向它的关系)p->next->prev = NULL;// 回收pfree(p);return 0;}// 正常删除：链表中要删除的节点不是头结点while (p){if (memcmp(&(p->data), &data, sizeof(DATA)) == 0){// p的上一个节点的next指向p的下一个节点p->prev->next = p->next;// p是尾结点if(p->next==NULL){// 解除p的上一个节点跟p的引用p->prev->next = NULL;}else // p不是尾结点{// p的下一个节点的prev指向p的上一个节点p->next->prev = p->prev;}// 回收解除引用的节点free(p);return 0;}// 改变循环条件p = p->next;}return -1;
}/*** @function:   void dlist_destroy(NODE**);* @berif:      链表回收* @argument:   head: 指向头指针变量的地址，用来接收首节点地址*              old_data：源数据*              new_data: 目标数据* @return :    成功返回 0*              失败返回 -1*/
void dlist_destroy(NODE **head)
{// p记录移动的节点，q记录需要回收的节点NODE *p = *head, *q = NULL;while (p){// 实现指针尾随q = p;       // 前一个节点p = p->next; // 后一个节点// 回收qfree(q);}*head = NULL;
}