深入剖析帶頭循環雙向鏈表的實現與應用

引言

場景描述

想象一個 環形地鐵線路(如深圳地鐵11號線),這條線路首尾相連,列車可以順時針或逆時針循環行駛。為了方便管理,地鐵系統設置了一個 “虛擬調度中心”(頭節點),它不承載乘客,但作為整個環線的邏輯起點和終點,用于監控和協調所有站點的運行。


映射關系
雙向循環鏈表結構地鐵環線系統
頭節點(不存儲數據)虛擬調度中心(無乘客上下車)
數據節點地鐵站點(如“沙井站”、“馬安山站”)
next 指針順時針方向的下一個站點
prev 指針逆時針方向的上一個站點
循環結構線路首尾相連,列車可雙向循環行駛

一、數據結構定義

typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* next;struct ListNode* prev;
} LTNode;
  • 節點結構
    • data:存儲節點數據
    • next:指向下一個節點
    • prev:指向前一個節點
  • 循環特性
    • 頭節點的next指向第一個有效節點
    • 頭節點的prev指向最后一個節點
    • 形成閉環結構(頭節點自環表示空鏈表)

二、核心函數實現詳解

1. 節點創建函數 LTBuyNode
LTNode* LTBuyNode(LTDataType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode; // 初始自環return newnode;
}
  • 功能:動態分配內存創建新節點。

  • 細節

    • 數據域初始化為 x

    • nextprev 指針初始指向自身,形成自環結構。

    • 若內存分配失敗,程序直接終止(exit(1))。


2. 鏈表初始化 LTInit
LTNode* LTInit() {LTNode* phead = LTBuyNode(-1); // 頭節點數據為-1return phead;
}
  • 功能:創建帶頭節點的空鏈表。

  • 細節

    • 頭節點數據為 -1nextprev 均指向自身。

    • 空鏈表僅含頭節點,邏輯上表示鏈表為空。


3. 打印鏈表 LTPrint
void LTPrint(LTNode* phead) {LTNode* pcur = phead->next;while (pcur != phead) {printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}
  • 功能:遍歷鏈表并打印所有數據節點(不打印頭節點)。

  • 細節

    • 從頭節點的下一個節點開始遍歷,直到回到頭節點結束。

    • 輸出格式為 1 -> 2 -> 3 -> ...,末尾換行。


4. 尾插法 LTPushBack
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev; // 新節點prev指向原尾節點newnode->next = phead;       // 新節點next指向頭節點phead->prev->next = newnode; // 原尾節點的next指向新節點phead->prev = newnode;       // 頭節點的prev指向新節點
}
  • 功能:在鏈表尾部插入新節點。

  • 指針調整步驟

    1. 新節點的 prev 指向原尾節點。

    2. 新節點的 next 指向頭節點。

    3. 原尾節點的 next 指向新節點。

    4. 頭節點的 prev 指向新節點。


5. 頭插法 LTPushFront
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next; // 新節點next指向原首節點newnode->prev = phead;       // 新節點prev指向頭節點phead->next->prev = newnode; // 原首節點的prev指向新節點phead->next = newnode;       // 頭節點的next指向新節點
}
  • 功能:在鏈表頭部插入新節點。

  • 指針調整步驟

    1. 新節點的 next 指向原首節點。

    2. 新節點的 prev 指向頭節點。

    3. 原首節點的 prev 指向新節點。

    4. 頭節點的 next 指向新節點。


6. 鏈表判空 LTEmpty
bool LTEmpty(LTNode* phead) {assert(phead);return phead->next == phead; // 僅頭節點自環時為空
}
  • 功能:判斷鏈表是否為空。

  • 返回值

    • true:鏈表為空(僅頭節點存在)。

    • false:鏈表至少有一個數據節點。


7. 尾刪法 LTPopBack
void LTPopBack(LTNode* phead) {assert(!LTEmpty(phead));     // 鏈表非空才能刪除LTNode* del = phead->prev;   // 待刪除的尾節點del->prev->next = phead;     // 尾節點前驅的next指向頭節點phead->prev = del->prev;     // 頭節點的prev指向尾節點前驅free(del);del = NULL;                  // 局部指針置空(不影響外部)
}
  • 功能:刪除鏈表尾節點。

  • 細節

    • 斷言確保鏈表非空。

    • 調整尾節點前驅的指針,跳過尾節點。

    • 釋放尾節點內存,局部指針 del 置空。


8. 頭刪法 LTPopFront
void LTPopFront(LTNode* phead) {assert(!LTEmpty(phead));LTNode* del = phead->next;   // 待刪除的首節點del->next->prev = phead;     // 首節點后繼的prev指向頭節點phead->next = del->next;     // 頭節點的next指向首節點后繼free(del);del = NULL;
}
  • 功能:刪除鏈表首節點。

  • 操作步驟:類似尾刪法,調整指針后釋放內存。


9. 查找節點 LTFind
LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {      // 遍歷數據節點if (pcur->data == x) return pcur;pcur = pcur->next;}return NULL;                 // 未找到返回NULL
}
  • 功能:查找第一個值為 x 的節點。

  • 返回值:找到返回節點指針,否則返回 NULL


10. 在指定位置后插入 LTInsert
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;   // 新節點next指向pos的后繼newnode->prev = pos;         // 新節點prev指向pospos->next->prev = newnode;   // pos后繼的prev指向新節點pos->next = newnode;         // pos的next指向新節點
}
  • 功能:在 pos 節點后插入新節點。

  • 應用場景:結合 LTFind 實現任意位置插入。


11. 在指定位置前插入 LTInsertFront
void LTInsertFront(LTNode* pos, LTDataType x) { assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;         // 新節點next指向posnewnode->prev = pos->prev;   // 新節點prev指向pos的前驅pos->prev->next = newnode;   // pos前驅的next指向新節點pos->prev = newnode;         // pos的prev指向新節點
}
  • 功能:在 pos 節點前插入新節點。


12. 刪除指定節點 LTErase
void LTErase(LTNode* pos) {assert(pos);pos->prev->next = pos->next; // pos前驅的next指向pos的后繼pos->next->prev = pos->prev; // pos后繼的prev指向pos的前驅free(pos);pos = NULL; // 局部指針置空(外部指針需手動置空)
}
  • 功能:刪除 pos 節點。

  • 注意事項

    • pos 不能是頭節點,否則鏈表結構被破壞。

    • 調用后,外部指向 pos 的指針變為野指針,需手動置空。


13. 銷毀鏈表 LTDesTroy
void LTDesTroy(LTNode** phead) {LTNode* pcur = (*phead)->next;while (pcur != *phead) {     // 遍歷釋放所有數據節點LTNode* next = pcur->next;free(pcur);pcur = next;}free(*phead);                // 釋放頭節點*phead = NULL;               // 頭指針置空
}
  • 功能:銷毀整個鏈表,釋放所有內存。

  • 設計

    • 使用二級指針確保外部頭指針被置空。

    • 避免內存泄漏和野指針問題。


測試用例解析 test01

void test01() {LTNode* plist = LTInit();            // 初始化空鏈表LTPushBack(plist, 1);                // 尾插1LTPushBack(plist, 2);                // 尾插2 → 鏈表: 1 -> 2LTPushBack(plist, 3);                // 尾插3 → 鏈表: 1 -> 2 -> 3LTPushBack(plist, 4);                // 尾插4 → 鏈表: 1 -> 2 -> 3 -> 4LTPrint(plist);                      // 輸出: 1 -> 2 -> 3 -> 4LTPushFront(plist, 0);               // 頭插0 → 鏈表: 0 -> 1 -> 2 -> 3 -> 4LTPrint(plist);LTPopBack(plist);                    // 尾刪4 → 鏈表: 0 -> 1 -> 2 -> 3LTPrint(plist);LTPopFront(plist);                   // 頭刪0 → 鏈表: 1 -> 2 -> 3LTPrint(plist);LTNode* pos = LTFind(plist, 2);      // 查找值為2的節點if (pos) {LTInsert(pos, 5);                // 在2后插入5 → 鏈表: 1 -> 2 -> 5 -> 3LTPrint(plist);}LTDesTroy(&plist);                   // 銷毀鏈表,plist置NULL
}
  • 驗證操作

    • 初始化、尾插、頭插、尾刪、頭刪、查找、指定位置插入、銷毀。

    • 通過打印驗證每一步操作的正確性

四、關鍵技術點總結

技術點說明
頭節點設計簡化邊界條件處理,統一頭插尾插操作
循環鏈表特性通過頭節點的 prev 指針快速訪問尾節點
指針操作技巧插入需修改 4 個指針,刪除需修改 2 個指針
內存管理使用LTBuyNode統一分配內存,LTDesTroy徹底釋放內存
安全性設計assert參數校驗,內存釋放后置 NULL

五、典型應用場景

  1. LRU 緩存
    • 通過頭尾指針快速訪問最近使用和最久未使用的節點
  2. 雙端隊列
    • 支持 O (1) 時間復雜度的頭尾操作
  3. 文件系統 inode 管理
    • 快速定位文件的前后節點
  4. 哈希表沖突處理
    • 雙向鏈表便于刪除操作

六、擴展學習建議

  1. 實現鏈表逆序操作
  2. 嘗試合并兩個有序鏈表
  3. 研究跳表(Skip List)數據結構
  4. 了解 Linux 內核中的鏈表實現

最后附上全部代碼:

代碼List.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//雙向鏈表的結構
typedef int LTDataType;
typedef struct  ListNode {LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//打印鏈表
void LTPrint(LTNode* phead);//雙向鏈表但初始化
LTNode* LTInit();//銷毀數據表
void LTDesTroy(LTNode** phead);
//void LTDataTroy(LTNode* phead); //也可也傳一級指針不過,最后得自己NULL一下,// 尾插
void LTPushBack(LTNode* phead, LTDataType x);// 頭插
void LTPushFront(LTNode* phead, LTDataType x);//只有一個頭結點的情況下,雙向鏈表為空
bool LTEmpty(LTNode* phead);//尾刪
void LTPopBack(LTNode* phead);
//頭刪
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入數據
void LTInsert(LTNode* pos, LTDataType x);//在pos位置之前插入數據
void LTInsertFront(LTNode* pos, LTDataType x);//刪除pos位置的結點
void LTErase(LTNode* pos);

代碼List.c

#include"List.h"//創建新的結點
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//判斷新結點是否創建成功if (newnode == NULL){perror("malloc fail!");exit(1);}//成功就把值賦上和指針指向newnode->data = x;newnode->next = newnode->prev = newnode;//返回一級指針指向的地址return newnode;
}void LTPrint(LTNode* phead)
{//把頭結點的下一個指向的地址賦給新創建的臨時指針LTNode* pcur = phead->next;//遍歷鏈表的數據,遍歷到頭結點結束while (pcur != phead){printf("%d -> ", pcur->data);//把pcur下一個地址賦給自己pcur = pcur->next;}printf("\n");
}LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{//斷言phead不為空assert(phead);//創建新的結點LTNode* newnode = LTBuyNode(x);//把新的結點prev指向頭結點的prevnewnode->prev = phead->prev;//把新的next指向phead的地址newnode->next = phead;//把頭結點的prev的結點的next結點指向新的結點phead->prev->next = newnode;//把頭結點prev指向新的結點phead->prev = newnode;
}//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//只有一個頭結點的情況下,雙向鏈表為空
bool LTEmpty(LTNode* phead)
{assert(phead);//判斷 phead->next 是否等于 phead 來確定鏈表是否為空,若相等則返回 true,表示鏈表為空;否則返回 false。return phead->next == phead;
}//尾刪
void LTPopBack(LTNode* phead)
{//對LTEmpty函數取反assert(!(LTEmpty(phead)));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//頭刪
void LTPopFront(LTNode* phead)
{//對LTEmpty函數取反assert(!(LTEmpty(phead)));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//在pos位置之后插入數據
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}
//在pos位置之前插入數據
void LTInsertFront(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;}//刪除pos位置的結點
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}//銷毀數據表
void LTDesTroy(LTNode** phead)
{LTNode* pcur = (*phead)->next;while (pcur != *phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(*phead);*phead = NULL;
}//void LTDataTroy(LTNode* phead)
//{
//    LTNode* pcur = phead->next;
//    while (pcur != phead)
//    {
//        LTNode* next = pcur->next;
//        free(pcur);
//        pcur = next;
//    }
//    free(phead);
//    phead = NULL;
//
//}

代碼test.c

#include"List.h"void test01()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPushFront(plist, 0);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTNode* pos = LTFind(plist, 2);if (pos){LTInsert(pos, 5);LTPrint(plist);}LTDesTroy(&plist);
}int main()
{test01();return 0;
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/73454.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/73454.shtml
英文地址,請注明出處:http://en.pswp.cn/web/73454.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

DeepSeek Smallpond 在火山引擎 AI 數據湖的探索實踐

資料來源&#xff1a;火山引擎-開發者社區 DeepSeek Smallpond 介紹 Smallpond 是一套由 DeepSeek 推出的 、針對 AI 領域&#xff0c;基于 Ray 和 DuckDB 實現的輕量級數據處理引擎&#xff0c;具有以下優點&#xff1a; 1.輕量級 2.高性能 3.支持規模大 4.無需運維 5.P…

Linux進程間的通信

進程間通信 1.進程間通信介紹2.匿名命名管道原理操作 1.進程間通信介紹 1.1 進程間通信目的&#xff1a;一個進程需要將他的數據發送給另一個進程&#xff0c;大家應該都多少接觸過linux中的管道符"|"&#xff0c;這個符號就是用來多個命令執行&#xff0c;在Linux中…

直播預告 | TDgpt 智能體發布 時序數據庫 TDengine 3.3.6 發布會即將開啟

從海量監控數據&#xff0c;到工業、能源、交通等場景中實時更新的各類傳感器數據&#xff0c;時序數據正在以指數級速度增長。而面對如此龐雜的數據&#xff0c;如何快速分析、自動發現問題、精準預測未來&#xff0c;成為企業數字化轉型過程中的關鍵挑戰。 TDengine 的答案是…

手撕FIO工具指南:從壓測翻車到避坑實戰

文章目錄 手撕FIO工具指南&#xff1a;從壓測翻車到避坑實戰一、背景&#xff1a;一次FIO壓測引發的驚魂夜二、FIO vs 其他IO工具&#xff1a;為何讓人又愛又怕&#xff1f;三、安裝指南&#xff1a;避開依賴地獄四、參數詳解五、避坑指南&#xff1a;血淚經驗總結六、安全壓測…

智能汽車圖像及視頻處理方案,支持視頻星軌拍攝能力

美攝科技作為智能汽車圖像及視頻處理領域的先行者&#xff0c;正以革新性的技術引領著行業的未來發展。美攝科技智能汽車圖像及視頻處理方案&#xff0c;一個集高效性、智能化、畫質增強于一體的創新解決方案&#xff0c;旨在重塑智能汽車圖像畫質的新標準&#xff0c;并支持前…

B站左神算法課學習筆記(P7):圖

目錄 一、圖的存儲方式&#xff08;千奇百怪&#xff09; 1&#xff09;鄰接表 2&#xff09;鄰接矩陣 3&#xff09;其他 4&#xff09;推薦存儲方式&#xff08;代碼&#xff09; 二、圖的遍歷 &#xff08;1&#xff09;寬度優先遍歷 &#xff08;2&#xff09;深度…

深度解析「前綴和」與「差分法」:高效算法的基石

深度解析前綴和與差分法&#xff1a;高效算法的基石 在計算機科學和數據處理領域&#xff0c;前綴和&#xff08;Prefix Sum&#xff09;與差分法&#xff08;Difference Method&#xff09;是兩種基礎且高效的算法技術。它們在處理數組的區間查詢和區間修改操作時&#xff0c…

2-1 基本放大電路

放大的概念 mV →V mA→A 特征&#xff1a;放大功率&#xff08;電壓與電流&#xff09;。 本質&#xff1a;能量在控制下的轉換。&#xff08;外接供電電源&#xff09; 必要條件&#xff1a;有源元件&#xff08;能量控制原件&#xff09; 前提&#xff1a;不失真 測試的…

詳解接口的常見請求方式

詳解接口的常見請求方式 一、 常見接口請求方式1. GET2. POST3. PUT4. DELETE5. PATCH6. HEAD7. OPTIONS 二、 實現方法1. 前端實現2. 后端實現 三、 作用與主要區別四、 舉例講解1. 創建 Spring Boot 工程2. 添加依賴3. 編寫 Controller 實現接口關鍵點說明 4. 啟動與測試5. 總…

【附代碼】【MILP建模】3D裝箱問題(3D-Bin Packing Problem)

文章目錄 相關教程相關文獻問題描述建模思路——carton 方向平行軸建模方法&#xff08;9變量6約束&#xff09;平行軸建模方法&#xff08;4變量8約束&#xff09;枚舉建模方法&#xff08;6變量1約束&#xff09; 建模思路——carton 位置平行軸建模方法枚舉建模方法 Bin長寬…

【計算機網絡中的奈氏準則與香農定理】

文章目錄 一、前言二、奈氏準則1. 概念2. 奈氏準則公式3. 奈氏準則的意義 三、香農定理1. 概念2. 香農定理公式3. 香農定理的意義 四、奈氏準則與香農定理的對比五、應用示例1. 奈氏準則示例2. 香農定理示例 六、總結 一、前言 在計算機網絡中&#xff0c;數據的傳輸速率與信道…

【C++】回調函數和回調對象

文章目錄 回調可調用對象函數指針作回調函數對象作回調函數對象的使用std::function【C11】作回調使用 【C11】Lambda表達式作回調【C11】bind對象作回調std::bind的使用作回調使用 回調 當發生某種事件時需要調用或觸發另一個事件即為回調&#xff0c;回調的核心即為將可調用…

DeepSeek助力文案,智能音箱如何改變你的生活?

你好&#xff0c;我是三橋君 你有沒有為寫智能音箱的宣傳文案而抓耳撓腮過&#xff1f;三橋君在這方面可是有些感想&#xff0c;今天就來給你嘮嘮怎么用DeepSeek寫出超贊的智能音箱宣傳文案。 首先&#xff0c;你得給DeepSeek喂足“料”。這就好比做飯&#xff0c;你得準備好各…

【區塊鏈安全 | 第一篇】密碼學原理

文章目錄 1.哈希函數1.1 哈希函數的性質1.2 常見哈希算法1.3 Merkle Tree&#xff08;默克爾樹&#xff09;1.4 HMAC&#xff08;哈希消息認證碼&#xff09; 2. 公鑰密碼學2.1 對稱加密 vs 非對稱加密2.2 RSA 算法2.3 ECC&#xff08;橢圓曲線密碼學&#xff09;2.4 Diffie-He…

基于websocketpp實現的五子棋項目

該博客對于學完C和linux操作系統&#xff0c;但不知道如何用C開發項目&#xff0c;已經不知道C如何使用第三方庫的人來說一定很有幫助&#xff0c;請耐心看完&#xff01; 先看一下游戲會顯示的前端界面&#xff0c;對理解這個游戲的前后端交互過程會有幫助 1. 開發環境 1.1 …

基于Redis分布鎖+事務補償解決數據不一致性問題

基于Redis的分布式設備庫存服務設計與實現 概述 本文介紹一個基于Redis實現的分布式設備庫存服務方案&#xff0c;通過分布式鎖、重試機制和事務補償等關鍵技術&#xff0c;保證在并發場景下庫存操作的原子性和一致性。該方案適用于物聯網設備管理、分布式資源調度等場景。 …

RK3568筆記八十: Linux 小智AI環境搭建

若該文為原創文章&#xff0c;轉載請注明原文出處。 最近小智AI火了&#xff0c;韋老師出了 Linux 小智 AI 聊天機器人 版本&#xff0c;想移植到 RK3568上&#xff0c; 由于和韋老師硬件不同&#xff0c;所以需要交叉編譯一些庫&#xff0c;為后續移植做準備。 一、環境 1、…

C# SerialPort 使用詳解

總目錄 前言 在工業控制、物聯網、嵌入式開發等領域&#xff0c;串口通信&#xff08;Serial Port Communication&#xff09;是連接串行設備&#xff08;如條碼掃描器、GPS接收器等&#xff09;與計算機的重要手段。C# 提供了內置的 SerialPort 類&#xff0c;簡化了串口開發…

3D點云的深度學習網絡分類(按照作用分類)

1. 3D目標檢測&#xff08;Object Detection&#xff09; 用于在點云中識別和定位目標&#xff0c;輸出3D邊界框&#xff08;Bounding Box&#xff09;。 &#x1f539; 方法類別&#xff1a; 單階段&#xff08;Single-stage&#xff09;&#xff1a;直接預測3D目標位置&am…

LabVIEW 與 PLC 通訊的常見方式

在工業自動化和數據采集系統中&#xff0c;PLC&#xff08;可編程邏輯控制器&#xff09; 廣泛用于控制和監測各種設備&#xff0c;而 LabVIEW 作為強大的圖形化編程工具&#xff0c;常用于上位機數據處理和可視化。為了實現 LabVIEW 與 PLC 的高效通訊&#xff0c;常見的方法包…