数据结构与算法-线性表-双向链表（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指针为NULL

    DuLNode *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 插入

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

【算法步骤】

1. 将新结点的前驱指针指向当前结点的前驱结点。①
2. 将当前结点的前驱结点的后继指针指向新结点。②
3. 将新结点的后继指针指向当前结点。③
4. 将当前结点的前驱指针指向新结点。④

【代码实现】

// 插入结点，在 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 删除

【算法步骤】

1. 将前驱结点的后继指针指向当前结点的后继结点。①
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;
}

【算法分析】

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