数据结构简单入门/复习（二）-循环链表与双向链表（C语言）

2022/1/23：更新为 Markdown 格式。

循环链表

循环链表是在线性链表的基础上，将最后一个结点的next设置为头指针。即

|empty - first| -> |data1 - second| -> |data2 - head|

双向链表

定义与结构

双向链表是在线性链表的基础上加入一个指向直接前驱的指针变量prior。

define int ElemType          //元素类型设置为int
typedef struct DuLNode{      //链表结构定义
    ElemType data;           //数据域
    struct DuLNode *prior    //直接前驱
    struct DuLNode *next;    //直接后继
}DuLNode;

插入

目的：只知道A与B，A的直接后继是C，将B插入A后C前。

原理：将B的前驱设置为A，后继设置为C，将C前驱设置为B，A后继设置为B

B->prior = A;
B->next = A->next;
A->next->prior = B;
A->next = B;

结点删除

目的：只知道A，删除ABC中的B。

原理：将A的后继设置为C，将B释放，将C的前驱设置为A。

A->next = A->next->next;
free(A->next->prior);
A->next->prior = A;