数据结构与算法-线性表-双向链表（Double Linked List）

1 线性表

1.4 双向链表（Double Linked List）

双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱，主要是为了解决前向查找的问题。

双向链表结构：

在这里插入图片描述

书籍和视频教程都只讲解了插入和删除的算法，这里也实现这两个算法。

一些常量和元素和前面类似，结点需要多一个前驱指针，结点结构代码如下：

// 双向链表的结点结构
typedef struct DuLNode
{ElemType data;                // 结点数据，ElemType类型struct DuLNode *prior, *next; // 指向下一个结点的指针
} DuLNode, *DuLinkList;           // DuLinkList 是指向 DuLNode 结构的指针类型，表示单链表的头结点指针

另外为了方便查看插入的效果，需要初始化双向链表，和插入一些数据方便测试，这里使用尾插法进行处理，尾插法的实现和前面基本类似，就是新结点要设置相应的前驱：

// 尾插法创建双向链表
Status CreateListTail(DuLinkList *L, int n)
{*L = (DuLinkList)malloc(sizeof(DuLNode)); // 创建头结点if (*L == NULL){return OVERFLOW;}(*L)->next = NULL; // 初始化头结点的next指针为NULLDuLNode *p = *L; // p 指向头结点for (int i = 1; i <= n; i++){// 创建一个新结点DuLNode *newNode = (DuLNode *)malloc(sizeof(DuLNode));if (!newNode) // 如果内存分配失败return OVERFLOW;newNode->data.x = i; // 将数据赋值给新结点// 插入新结点newNode->next = NULL; // 新结点的后继指针置空newNode->prior = p;   // 新结点的前驱指针指向当前结点p->next = newNode;    // 当前结点的后继指针指向新结点p = newNode;          // p 指向新插入的结点}return OK;
}

还有插入和删除都涉及另外一个算法——获取第 i 个结点，这里补充一下：

// 获取第 i 个结点，并返回结点指针
DuLNode *GetElem_Dul(DuLinkList *L, int i)
{if (i < 1) // i 值不合法return NULL;DuLNode *p = (*L)->next; // 从头结点的下一个结点开始遍历int j = 1;               // 计数器，从1开始while (p != NULL && j < i) // 遍历到第i个结点 并且 当前结点不为空{p = p->next; // 移动到下一个结点j++;}if (p == NULL || j > i)return NULL;return p;
}

1.4.1 插入

插入的步骤要比单链表多设置几个指针指向，主要的难点在于顺序很重要，如果顺序不对，可能导致实际的指针被提前修改，无法获取到对应的结点。

【算法步骤】

将新结点的前驱指针指向当前结点的前驱结点。①
将当前结点的前驱结点的后继指针指向新结点。②
将新结点的后继指针指向当前结点。③
将当前结点的前驱指针指向新结点。④

在这里插入图片描述

【代码实现】

// 插入结点，在 i-1 和 i 之间插入一个结点，新结点的位置就是 i
Status ListInsert(DuLinkList *L, int i, ElemType e)
{DuLNode *p;if (!(p = GetElem_Dul(L, i))) // 获取第 i 个结点return ERROR;DuLNode *newNode = (DuLNode *)malloc(sizeof(DuLNode)); // 创建新结点if (newNode == NULL)return OVERFLOW;newNode->data = e;         // 设置新结点的数据newNode->prior = p->prior; // 将新结点的前驱指针指向当前结点的前驱结点p->prior->next = newNode;  // 将当前结点的前驱结点的后继指针指向新结点newNode->next = p;         // 将新结点的后继指针指向当前结点p->prior = newNode;        // 将当前结点的前驱指针指向新结点return OK;
}

【算法分析】

时间复杂度主要受 GetElem_Dul 影响，因此为 O(n) 。

1.4.2 删除

【算法步骤】

将前驱结点的后继指针指向当前结点的后继结点。①
如果当前结点不是最后一个结点，将后继结点的前驱指针指向当前结点的前驱结点。②

在这里插入图片描述

【代码实现】

// 删除第 i 个结点
Status ListDelete(DuLinkList *L, int i)
{DuLNode *p;if (!(p = GetElem_Dul(L, i))) // 获取第 i 个结点return ERROR;p->prior->next = p->next;      // 将前驱结点的后继指针指向当前结点的后继结点if (p->next != NULL)           // 如果当前结点不是最后一个结点p->next->prior = p->prior; // 将后继结点的前驱指针指向当前结点的前驱结点free(p); // 释放当前结点内存return OK;
}