企业官网建设流程全解析

前面我们学完单向链表、单链表排序，今天进入双向链表。 单向链表只能向后遍历，删除节点时，必须从头遍历找到待删节点的前驱，效率低。带头双向链表每个节点同时保存前驱prev、后继next指针，可以向前、向后双向遍历，查找前驱节点 O (1)，极大简化删除操作。 最后拓展循环链表、队列的基础概念，为后面环形队列做铺垫。

统一节点定义：

typedef int data_t; typedef struct node { data_t data; struct node *next; //后继指针，指向下一个节点 struct node *prev; //前驱指针，指向上一个节点 }node_t;

一、带头双向链表

带头：存在哨兵头节点 head，头节点不存储有效业务数据，用来简化空链表、边界节点插入删除的判断。

1. 创建双向链表（创建哨兵头节点）

node_t *dlinklist_create(void) { node_t *head = malloc(sizeof(node_t)); if (head == NULL) { printf("dlinklist_create malloc fail\n"); return NULL; } head->next = NULL; head->prev = NULL; return head; }

空链表状态：phead->next == NULL

2. 头插法（在头节点后面插入新节点）

步骤

1. 创建新节点，填充数据
2. 新节点 next 指向原来头节点后面第一个有效节点
3. 新节点 prev 指向哨兵头节点
4. 头节点 next 指向新节点
5. 如果原链表不为空，原首节点的 prev 要指向新节点（边界坑！链表只有一个节点的时候必须处理）

int dlinklist_insert_head(node_t *phead, data_t data) { if (phead == NULL) { return -1; } node_t *pnew = malloc(sizeof(node_t)); if (pnew == NULL) { return -1; } pnew->data = data; pnew->next = phead->next; pnew->prev = phead; //如果插入前链表不是空，修改原第一个节点的prev if (phead->next != NULL) { phead->next->prev = pnew; } phead->next = pnew; return 0; }

3. 尾插法（链表尾部插入节点）

思路：先找到链表最后一个节点，再修改指针链接。

int dlinklist_insert_tail(node_t *phead, data_t data) { if (phead == NULL) { return -1; } node_t *pnew = malloc(sizeof(node_t)); if (pnew == NULL) { return -1; } pnew->data = data; //找到尾节点 node_t *p = phead; while (p->next != NULL) { p = p->next; } pnew->next = p->next; pnew->prev = p; p->next = pnew; return 0; }

4. 遍历打印（支持正向 / 反向打印）

dir=1：从头往后正向打印；dir=0：从尾向前反向打印

int dlinklist_dir_print(node_t *phead, data_t dir) { if (phead == NULL || is_empty(phead) == 1) { return -1; } node_t *p = phead->next; if (dir == 0) { //正向打印 while (p!=NULL) { printf("%d ",p->data); p = p->next; } putchar('\n'); }else if(dir == 1) { //反向打印：先走到尾节点，再向前遍历 while (p->next != NULL) { p = p->next; } while (p != phead) { printf("%d ",p->data); p = p->prev; } putchar('\n'); } return 0; }

5. 查找节点（按值查找）

从头遍历，匹配 data，返回节点地址；找不到返回 NULL

node_t *dlinklist_find_key(node_t *phead, data_t key) { if (phead == NULL || is_empty(phead) == 1) { return NULL; } node_t *p = phead; while (p != NULL) { if (p->data == key) { return p;//找到，返回节点地址 } p = p->next; } return NULL; }

6.更新链表值

从头遍历，匹配old，更新成new。

node_t *dlinklist_update(node_t *phead, data_t old, data_t new) { if (phead == NULL || is_empty(phead) == 1) { return NULL; } node_t *p = phead->next; while (p != NULL) { if (p->data = old) { p->data = new; return p; } p = p->next; } return NULL; }

7. 删除操作（头删、尾删、按关键字删除）

头删：删除第一个有效节点

int dlinklist_delete_head(node_t *phead) { if (phead == NULL) { return -1; } node_t *p = phead->next; phead->next = p->next; if (p->next != NULL) { p->next->prev = phead; }else//只剩一个节点 { phead->prev = NULL;//变成空链表 } free(p); p = NULL; return 0; }

尾删：删除最后一个节点

int dlinklist_delete_tail(node_t *phead) { if (phead == NULL) { return -1; } //找到尾节点 node_t *p = phead; while (p->next != NULL) { p = p->next; } p->prev->next = NULL; free(p); p = NULL; return 0; }

按关键字删除：删除指定值的节点

int dlinklist_delete_key(node_t *phead, data_t key) { if (phead == NULL) { return -1; } node_t *p = phead; node_t *q = NULL; while (p != NULL && p->data != key) { p = p->next; } if (p == NULL) { return -1; } //要删除的值 p->prev->next = p->next; if(p->next != NULL) { p->next->prev = p->prev; } free(p); p = NULL; return 0; }

8. 销毁双向链表，释放全部内存

int dlinklist_destroy(node_t **pphead) { if (pphead == NULL) { return -1; } node_t *p = *pphead; node_t *q = p; while (p != NULL) { q = p->next; free(p); p = q; } //悬空指针 *pphead = NULL; return 0; }

双向链表小结

优点

1. 双向遍历，支持反向输出链表
2. 删除任意节点，直接通过prev拿到前驱，不需要从头遍历查找前驱，效率高

缺点

1. 每个节点多一个 prev 指针，占用更多内存
2. 插入、删除操作，要维护两组指针，指针赋值顺序容易出错，容易断链

二、循环链表（环形链表）

普通链表尾节点 next 为 NULL；循环链表：尾节点的 next 指针，指向头节点，形成闭环。

• 单向循环链表：尾节点 ->next = head
• 双向循环链表：尾节点 next=head，头节点 prev = 尾节点

特点：

1. 没有严格意义上的链表末尾，遍历的时候判断条件不再是p!=NULL，而是p != phead
2. 适合环形场景：循环队列、轮询调度、环形任务调度（嵌入式很常用）

注意：循环链表遍历的时候千万不要忘记终止条件，否则死循环！

1. 创建环形链表（创建哨兵头节点）

node_t *clinklist_create(void) { node_t *head = malloc(sizeof(node_t)); if (head == NULL) { printf("clinklist_create malloc fail\n"); return NULL; } head->next = head; return head; }

2. 头插法（在头节点后面插入新节点）

int clinklist_insert_head(node_t *phead, data_t data) { if (phead == NULL) { return -1; } node_t *pnew = malloc(sizeof(node_t)); if (pnew == NULL) { return -1; } pnew->data = data; pnew->next = phead->next; phead->next = pnew; return 0; }

3. 尾插法（链表尾部插入节点）

int clinklist_insert_tail(node_t *phead, data_t data) { if (phead == NULL) { return -1; } node_t *pnew = malloc(sizeof(node_t)); if (pnew == NULL) { return -1; } pnew->data = data; node_t *p = phead->next; while (p->next != phead) { p = p->next; } p->next = pnew; pnew->next = phead; return 0; }

4. 查找节点（按值查找）

node_t *clinklist_find_key(node_t *phead, data_t key) { if (phead == NULL || is_empty(phead) == 1) { return NULL; } node_t *p = phead->next; while (p != phead) { if (p->data == key) { return p; } p = p->next; } return NULL; }

5.更新链表值

node_t *clinklist_update(node_t *phead, data_t old, data_t new) { if (phead == NULL || is_empty(phead) == 1) { return NULL; } node_t *p = phead->next; while (clinklist_find_key(phead,old) != NULL) { p = clinklist_find_key(phead,old); p->data = new; return p; } return NULL; }

6. 删除操作（头删、尾删、按关键字删除）

头删：删除第一个有效节点

int clinklist_delete_head(node_t *phead) { if (phead == NULL) { return -1; } //待删除的值 node_t *p = phead->next; phead->next = p->next; free(p); p = NULL; return 0; }

尾删：删除最后一个节点

int clinklist_delete_tail(node_t *phead) { if (phead == NULL) { return -1; } node_t *p = phead; while (p->next->next != phead) { p = p->next; } node_t *q = p->next; p->next = phead; free(q); q = NULL; return 0; }

按关键字删除：删除指定值的节点

int clinklist_delete_key(node_t *phead, data_t key) { if (phead == NULL) { return -1; } node_t *p = phead; node_t *q = NULL; while (p->next != phead && p->next->data != key) { p = p->next; } if (p->next == phead) { return -1; } //待删除的值 q = p->next; p->next = q->next; free(q); q = NULL; return 0; }

8. 销毁循环链表，释放全部内存

int clinklist_destroy(node_t **pphead) { if (pphead == NULL) { return -1; } node_t *p = (*pphead)->next; node_t *q = p->next;//用于循环 while (p != *pphead) { q = p->next; free(p); p = q; } free(p); p = NULL; printf("destroy succ\n"); return 0; }

三、队列的基础概念

队列：先进先出 FIFO的线性表。

• 只允许队尾入队，队头出队
• 先进入队列的数据，最先拿出来，类似排队

区分：栈是后进先出 LIFO，队列先进先出 FIFO。

两种实现方式：

1. 链式队列：基于链表实现，无容量上限
2. 顺序队列 / 环形队列：基于数组实现，固定大小，嵌入式项目高频使用（后续学习）

应用场景：消息队列、任务队列、IO 缓冲、串口接收缓冲区。

四、总结

1. 带头双向链表全套接口：创建、头插、尾插、正向 / 反向遍历、查找、头删、尾删、按值删除、销毁。 核心要点：操作节点时同时维护prev和next两个指针，处理边界（空链表、只有单个节点）。
2. 循环链表尾节点指向头部形成环；遍历终止条件不再是判断 NULL；适合循环调度场景。
3. 队列FIFO 先进先出；队尾入队，队头出队；分为链式队列、环形数组队列，嵌入式消息处理大量使用。