- 作者原创，转载请注明出处。
个人博客：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。
本文属数据结构系列持续更新中
