双向循环链表原理与 C 语言实现

节点结构与表结构

typedef int Element;
typedef struct _node {
    Element val;
    struct _node *next;
    struct _node *prev;
} DNode, DList;

这既是节点的结构，也是整个表的结构 有指向前驱节点的指针 也有指向后继节点的指针

接口

初始化接口

void initDList(DList* header) {
    header->val = 0;
    header->next = header->prev = header;
}

这是一个指向双向循环链表 DList 的 header 指针，也是后续插入/删除的入口

头插/尾插

插入逻辑

在操作时，建议从后往前进行。若先改变前面的值，后面的值可能无法找到前驱节点。

实现逻辑如下： next->prev = node; // 1 建立后继与前驱的联系 node->next = next; // 2 node->prev = prev; // 3 prev->next = node; // 4

其中 node 是要插入的新节点，next 是原位置的后继节点，prev 是原位置的前驱节点。

static void addDNode(DNode *new_node, DNode *prev, DNode *next) {
    next->prev = new_node;
    new_node->next = next;
    new_node->prev = prev;
    prev->next = new_node;
}

头插/尾插共用一个逻辑，定义一个内部接口

头插