从零开始学数据结构：线性表（下）

AcWing 826. 从零开始学数据结构：线性表（上）

AcWing 826. 从零开始学数据结构：线性表（中）

四、双链表

1.双链表的存储结构定义

如果希望快速确定单链表中任一结点的前驱结点，可以在单链表的每个结点在设一个指向其前驱结点的指针域，这样就形成了双链表(double linked list)。
在双链表中，每个结点在存储数据元素的时候，还存储了其前驱元素和后继元素所在结点的地址。双链表的结点结构如图所示，其中，data为数据域，prior为前驱指针域，存放前驱结点的地址；next为后继指针域，存放后继结点的地址。

2.双链表的实现

在双链表中求表长、按位查找、按值查找、遍历等操作的实现与单链表基本相同，下面只讨论插入、删除操作。

· 双链表的结点结构体定义

typedef int Datatype;

typedef struct DulNode
{
    Datatype data;
    struct DulNode* prior, * next;
}DulNode;

· 插入操作

int Insert(int i, DulNode *first)
{
    DulNode* s = NULL;
    DulNode* p = first;
    int count = 1;

    while (p != NULL && count < i - 1)
    {
        p = p->next;
        count++;
    }
    if (p == NULL)
    {
        printf("位置错误，插入失败\n");
        return 0;
    }
    else
    {
        s = (DulNode*)malloc(sizeof DulNode);
        s->prior = p;
        s->next = p->next;
        p->next->prior = s;
        p->next = s;
        return 1;
    }
}

· 删除操作

int Delete(int i, int* ptr, DulNode* first)
{
    DulNode *p = first;
    int count = 1;

    while (p != NULL && count < i - 1)
    {
        p = p->next;
        count++;
    }

    if (p == NULL)
    {
        printf("位置错误，删除失败\n");
        return 0;
    }
    else
    {
        (p->prior)->next = p->next;
        (p->next)->prior = p->prior;
        return 1;
    }
}

五、循环链表

在单链表中，如果将终端结点的指针由空指针改为指向头指针，就能使整个单链表形成一个环，这种头尾相接的单链表称为循环单链表。

循环链表具有以下特点：

1. 循环性质：循环链表中的最后一个节点的指针指向链表的头部，形成一个循环的环路。这使得可以从任何节点开始遍历整个链表，因为链表没有明确的尾部。

2. 无需特殊操作即可实现循环遍历：由于循环链表的循环性质，不需要特殊的操作就可以实现循环遍历。可以从任何节点出发，通过遍历节点的指针来访问链表中的所有节点。

3. 灵活性：由于循环链表的循环性质，可以方便地执行插入和删除操作，而不需要更改链表的头指针。可以通过调整节点之间的指针来实现插入和删除操作。

4. 内存利用率较高：循环链表中的每个节点除了存储数据外，还需要一个指针来指向下一个节点。相比于线性链表，循环链表的内存利用率略高，因为最后一个节点的指针可以重复利用。

5. 可循环利用：循环链表可以通过将最后一个节点的指针指向新节点来实现节点的循环利用。这在某些情况下可以提高内存的使用效率。

需要注意的是，循环链表的一个潜在问题是可能出现无限循环。如果链表中的指针指向出现错误，可能会导致在遍历链表时出现无限循环。因此，在操作循环链表时需要特别小心，确保指针的正确性。

循环链表在某些场景下有其特定的应用，例如模拟循环队列、实现循环缓冲区等。

六、结语

数据结构与算法是计算机人必须精通的基础，在未来的学习中，我将会把我学到的知识总结，发成博客，以便自己和大家学习。我现在也是一名大二的学生，写出的东西会有很多的问题和不严谨的地方。希望大家发现后可以提出来，我会虚心的接受和修改，有心人，天不负！！！让我们继续努力，一定会创出自己美好的未来！！！