「数据结构 三」C 语言实现循环链表

• 作者原创，转载请注明出处。

个人博客：renzhe.name

本文主要讲述循环链表，双向链表。

循环链表

循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。

在单链表中，判别条件为 p != NULL 或 p->next != NULL,而循环单链表的判别条件为 p != L 或 p->next != L。

具体代码可以访问下面 GitHub 链接。

循环列表

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

在双向链表中，若 d 为指向向某一结点的指针，则显然有下面代码：

d->next->prior = d->prior->next = d

在双向循环链表中，有些操作和只需要涉及一个方向指针，算法描述和线性链表的操作相同，但是插入和删除时有很大的不同，在双向链表中需要修改两个方向指针。这里只给出了插入和删除的 C 语言实现代码，具体完整代码可以查看文末 GitHub 链接。

双向链表中的插入

/**
 * 初始条件：双向链表 L 存在，且 1 <= i <= ListLength(L) + 1
 * 操作结果：在 L 中第 i 个元素前插入新的元素 e，L 的长度加 1
 * @param L
 * @param i
 * @param e
 * @return
 */
Status ListInsert(DuLinkList L, int i, ElemType e) {
    DuLinkList p, s;
    if (i < 1 || i > (ListLength(L) + 1)) { //i 值不合法
        return ERROR;
    }
    p = GetElemP(L, i - 1);
    if (!p) { //在 L 中确定第 i 个元素的前驱位置指针 p
        return ERROR; // p = NULL 时，第 i 个元素不存在
    }
    s = (DuLinkList)malloc(sizeof(struct DuLNode));
    if (!s) {
        exit(OVERFLOW);
    }
    s->data = e;
    s->prior = p; //在 i - 1 个元素后插入
    s->next = p->next;
    p->next->prior = s;
    p->next = s;
    return OK;
}

这里使用了一个 GetElemP() 函数确定第 i 个元素位置的指针 p，具体代码如下：

/**
 * 返回 L 中第 i 个元素的地址，若 i = 0 返回头结点，若 i 不存在，返回 NULL
 * @param L
 * @param i
 * @return
 */
DuLinkList GetElemP(DuLinkList L, int i) {
    DuLinkList p = L; //p 指向头结点
    if (i < 0 || i > ListLength(L)) { //i 值不合法
        return NULL;
    }
    for (int j = 1; j <= i; j++) {
        p = p->next;
    }
    return p;
}

双向链表的删除

/**
 * 初始条件：双向链表 L 存在且非空，且 1 <= i <= ListLength(L)
 * 操作结果：删除 L 中的第 i 个元素并用 e 返回其值，L 的长度减 1
 * @param S
 * @param i
 * @param e
 * @return
 */
Status ListDelete(DuLinkList L, int i, ElemType *e) {
    DuLinkList p;
    p = GetElemP(L, i);
    if (!p) { //在 L 中确定第 i 个元素的位置指针 p
        return ERROR; //p = NULL 是，第 i 个元素不存在，也就是 i 值不合法
    }
    *e = p->data;
    p->prior->next = p->next; //修改被删除结点的前驱结点的后继指针
    p->next->prior = p->prior; //修改被删除结点的后继结点的前驱指针
    free(p);
    return OK;
}

想要查看源码可以访问下面 github 链接，如果觉得不错，请给个 Star。

循环列表
双向循环链表

本文属数据结构系列持续更新中