双向链表：高效遍历与删除指南

一、先解答上次的思考题问单链表反转为什么要用三个指针答因为反转时要把当前节点指向前一个节点如果不提前保存next链表就会断掉找不到后面的节点。pre记录已经反转好的前驱cur当前正在反转的节点next保存下一个节点防止断链二、今天学习目标理解双向链表可以向前、向后遍历理解循环链表最后节点指向头节点双向链表完整代码增、删、打印三种链表对比总结三、双向链表是什么单链表只能往后走不能往回走。双向链表每个节点有两个指针prev指向前一个节点next指向后一个节点结构struct Node { int data; struct Node* prev; // 前驱指针 struct Node* next; // 后继指针 };优点可以向前遍历找前驱节点极快删除节点时不用单独记录前驱更符合实际工程使用四、双向链表完整代码可直接运行#include stdio.h #include stdlib.h // 1. 双向链表节点定义 struct Node { int data; struct Node* prev; struct Node* next; }; // 2. 创建新节点 struct Node* createNode(int val) { struct Node* newNode (struct Node*)malloc(sizeof(struct Node)); newNode-data val; newNode-prev NULL; newNode-next NULL; return newNode; } // 3. 尾部插入 void addToTail(struct Node** head, int val) { struct Node* newNode createNode(val); if (*head NULL) { *head newNode; return; } struct Node* cur *head; while (cur-next ! NULL) { cur cur-next; } cur-next newNode; newNode-prev cur; } // 4. 正向打印 void printForward(struct Node* head) { struct Node* cur head; while (cur ! NULL) { printf(%d - , cur-data); cur cur-next; } printf(NULL\n); } // 5. 反向打印双向链表特有 void printBackward(struct Node* head) { if (head NULL) return; struct Node* cur head; while (cur-next ! NULL) { cur cur-next; } printf(NULL); while (cur ! NULL) { printf( - %d, cur-data); cur cur-prev; } printf(\n); } // 6. 按值删除节点 void deleteByValue(struct Node** head, int val) { if (*head NULL) return; struct Node* cur *head; // 找节点 while (cur ! NULL cur-data ! val) { cur cur-next; } if (cur NULL) { printf(未找到值为 %d 的节点\n, val); return; } // 1. 删除的是头节点 if (cur-prev NULL) { *head cur-next; if (*head ! NULL) { (*head)-prev NULL; } } // 2. 删除的是尾节点 else if (cur-next NULL) { cur-prev-next NULL; } // 3. 删除中间节点 else { cur-prev-next cur-next; cur-next-prev cur-prev; } free(cur); } // 主函数测试 int main() { struct Node* head NULL; // 构建链表 addToTail(head, 10); addToTail(head, 20); addToTail(head, 30); addToTail(head, 40); printf(正向打印); printForward(head); printf(反向打印); printBackward(head); // 删除 20 deleteByValue(head, 20); printf(\n删除20后); printForward(head); return 0; }运行结果正向打印10 - 20 - 30 - 40 - NULL 反向打印NULL - 40 - 30 - 20 - 10 删除20后10 - 30 - 40 - NULL五、循环链表是什么循环链表最后一个节点的next不指向NULL而是指向头节点链表形成一个环常用于轮询调度、环形缓冲区特点没有明显的头尾遍历时要判断是否回到起点防止死循环六、三种链表终极对比表格特点单链表双向链表循环链表指针数量1 个next2 个prev、next1 个next遍历方向仅向后可前可后环形循环找前驱节点慢快一般占用内存小较大小适用场景简单队列、栈缓存、LRU、双向队列轮询、环形结构一句话记忆简单场景 →单链表要前后都能走 →双向链表要环形、循环使用 →循环链表七、今日小练习带代码练习任务创建双向链表5 - 15 - 25 - 35 - NULL正向、反向打印删除15再次打印直接把上面main函数里的数字改成5、15、25、35 即可完成。