【数据结构】循环链表、双向链表、双向循环链表

0x01：循环链表

什么是循环链表

定义
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

循环链表

特点
1. 从循环链表中的任何一个结点位置都可以找到其他所有其他结点，而单链表做不到
2. 循环链表中没有明显的尾端，故为了避免死循环，我们对以下循环判断语句进行了修改
```
p != NULL;    ---->    p != L;
p->next != NULL;    --->    p->next != L;
```
3. 对循环链表，有时不给出头指针，而给出尾指针，这样可以更方便的找到第一个和最后一个结点
4. 所以循环链表的开始结点为：rear->next->next，结束结点为：rear
当循环链表为空表时，头结点的后继指向他自己本身
所以判断循环链表是否为空时，只要确定 L->next = L 是否为真即可

循环链表的应用

循环链表的合并

使用 p 暂存表 La 头结点信息
将 Lb 表头连结到 La 表尾
释放 Lb 表头结点
修改 Lb 表尾指向 La 头结点

LinkList connect(LinkList La, LinkList Lb){
    p = La->next;
    La->next = Lb->next->next;
    delete Lb->next;
    Lb->next = p;
    return Lb;
}

0x02：双向链表

什么是双向链表

与单链表的结点不同，双向链表的结点比单链表的结点多出一个指针域，来指向他的直接前驱

不同点
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有俩个指针分别指向直接后继和直接前驱；

typedef struct DuLNode{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode, *DuLinkList

双链表

所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

双向链表的应用

双向链表的插入操作
1. 找到$ a_i $结点用 p 指向该结点
2. 新建一个结点 s，将其数据域置为 e
3. 将结点 s 的前驱指针指向结点 p 的前驱指针所指向的地址
4. 将结点 p 的直接前驱结点的后继指针指向结点 s
5. 将结点 s 的后继指针指向结点 p
6. 将结点 p 的前驱指针指向结点 s
注意：必须保证：先连后改
```
Status listInsert(DuLinkList &L, int i, ElemType e){
    if(!(p = getElemP_DuL(L, i))){
        return ERROR;
    }
    s = new DuLNode;
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
}
```

双向链表的删除操作

找到$ a_i $结点用 p 指向该结点

双向链表的删除①

将 p 结点的直接前驱结点的后继指针指向 p 的直接后继结点

双向链表的删除②.、

将 p 结点的直接后继结点的前驱指针指向 p 的直接前驱结点

双向链表的删除③

Status listDelete_DuL(DuLinkList &L, int i, ElemType &e){
    if(!(p = getElemP_DuL(L, i))){
        return ERROR;
    }
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    delete p;
    return OK;
}