雙向鏈表的操作函數
DouLink.c
#include "DouLink.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** @brief 創建一個空的雙向鏈表* * 動態分配雙向鏈表管理結構的內存,并初始化頭指針和節點計數* * @return 成功返回指向新鏈表的指針,失敗返回NULL*/
DouLinkList *CreateDouLinkList()
{// 為鏈表管理結構分配內存DouLinkList *dl = malloc(sizeof(DouLinkList));if (NULL == dl){perror("CreateDouLinkList malloc"); // 分配失敗時輸出錯誤信息return NULL;}dl->head = NULL; // 初始化頭指針為空(空鏈表)dl->clen = 0; // 初始化節點計數為0return dl;
}/*** @brief 在雙向鏈表頭部插入新節點* * 動態創建新節點,將數據存入節點并插入到鏈表頭部* * @param dl 指向雙向鏈表的指針* @param data 指向要插入的數據的指針* @return 成功返回0,失敗返回1*/
int InsertHeadDouLinkList(DouLinkList *dl, DATATYPE *data)
{// 為新節點分配內存DouLinkNode *newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){perror("InsertHeadDouLinkList malloc\n"); // 分配失敗時輸出錯誤信息return 1;}// 復制數據到新節點memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL; // 初始化新節點的后繼指針newnode->prev = NULL; // 初始化新節點的前驅指針// 如果鏈表為空,直接將新節點作為頭節點if (IsEmptyDouLinkList(dl)){dl->head = newnode;}// 否則將新節點插入到頭部else{newnode->next = dl->head; // 新節點的后繼指向原頭節點dl->head->prev = newnode; // 原頭節點的前驅指向新節點dl->head = newnode; // 更新頭指針為新節點}dl->clen++; // 節點計數加1return 0;
}/*** @brief 在雙向鏈表尾部插入新節點* * 動態創建新節點,將數據存入節點并插入到鏈表尾部* * @param dl 指向雙向鏈表的指針* @param data 指向要插入的數據的指針* @return 成功返回0,失敗返回1*/
int InsertTailDouLinkList(DouLinkList *dl, DATATYPE *data)
{// 如果鏈表為空,直接調用頭部插入函數if (IsEmptyDouLinkList(dl)){return InsertHeadDouLinkList(dl, data);}// 否則在尾部插入else{// 為新節點分配內存DouLinkNode *newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){perror("InsertTailDouLinkList malloc\n"); // 分配失敗時輸出錯誤信息return 1;}// 復制數據到新節點memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL; // 新節點的后繼為空(作為尾節點)newnode->prev = NULL; // 初始化前驅指針// 找到當前尾節點DouLinkNode *tmp = dl->head;while (tmp->next) // 遍歷到最后一個節點{tmp = tmp->next;}// 將新節點鏈接到尾節點后newnode->prev = tmp; // 新節點的前驅指向原尾節點tmp->next = newnode; // 原尾節點的后繼指向新節點}dl->clen++; // 節點計數加1return 0;
}/*** @brief 在雙向鏈表指定位置插入新節點* * 在鏈表的指定索引位置插入新節點,索引從0開始* * @param dl 指向雙向鏈表的指針* @param data 指向要插入的數據的指針* @param pos 插入位置的索引* @return 成功返回0,失敗返回1*/
int InsertPosDouLinkList(DouLinkList *dl, DATATYPE *data, int pos)
{int size = GetSizeDouLinkList(dl);// 檢查位置是否合法if (pos < 0 || pos > size){printf("InsertPosDouLinkList pos error\n");return 1;}// 位置0等同于頭部插入if (0 == pos){return InsertHeadDouLinkList(dl, data);}// 位置等于鏈表長度等同于尾部插入else if (size == pos){return InsertTailDouLinkList(dl, data);}// 中間位置插入else{// 為新節點分配內存,注意只能再此處為該新節點的分配內存,(因為如果上面的條件符合,調用頭插或尾插函數時就會有分配內存這一操作,如果一開始就為該新節點分配內存可能會導致段錯誤)DouLinkNode *newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){perror("InsertPosDouLinkList malloc\n"); // 分配失敗時輸出錯誤信息return 1;}// 復制數據到新節點memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;newnode->prev = NULL;// 找到要插入位置的節點DouLinkNode *tmp = dl->head;while (pos--) // 移動到目標位置{tmp = tmp->next;}// 插入新節點newnode->next = tmp; // 新節點的后繼指向當前節點newnode->prev = tmp->prev; // 新節點的前驅指向當前節點的前驅tmp->prev = newnode; // 當前節點的前驅指向新節點newnode->prev->next = newnode; // 當前節點原前驅的后繼指向新節點}dl->clen++; // 節點計數加1return 0;
}/*** @brief 顯示雙向鏈表中的所有節點數據* * 可以按照正向或反向遍歷并打印鏈表中的所有數據* * @param dl 指向雙向鏈表的指針* @param direct 遍歷方向(正向或反向)* @return 成功返回0*/
int ShowDouLinkList(DouLinkList *dl, DIRECT direct)
{DouLinkNode *tmp = dl->head;// 正向遍歷(從頭部到尾部)if (DIR_FORWARD == direct){while (tmp) // 遍歷所有節點{// 打印節點數據printf("name:%s sex:%c age:%d score:%d\n", tmp->data.name, tmp->data.sex, tmp->data.age, tmp->data.score);tmp = tmp->next; // 移動到下一個節點}}// 反向遍歷(從尾部到頭部)else{// 先移動到尾節點while (tmp->next){tmp = tmp->next;}// 從尾節點遍歷到頭部while (tmp){// 打印節點數據printf("name:%s sex:%c age:%d score:%d\n", tmp->data.name, tmp->data.sex, tmp->data.age, tmp->data.score);tmp = tmp->prev; // 移動到前一個節點}}return 0;
}/*** @brief 判斷雙向鏈表是否為空* * @param dl 指向雙向鏈表的指針* @return 鏈表為空返回1,不為空返回0*/
int IsEmptyDouLinkList(DouLinkList *dl)
{return 0 == dl->clen; // 通過節點計數判斷是否為空
}/*** @brief 按姓名查找雙向鏈表中的節點(舊版實現,通過姓名直接匹配,可與函數指針回調版對比)* * 遍歷雙向鏈表,逐個對比節點中存儲的姓名與傳入的目標姓名,找到則返回對應節點指針,用于簡單的按姓名精準查找場景。* 若后續有多樣化查找需求(比如按年齡、分數等),更推薦用函數指針回調的通用查找方式( FindDouLinkList 函數)。* * @param dl 指向要操作的雙向鏈表管理結構的指針,通過它能訪問鏈表頭節點,進而遍歷整個鏈表* @param name 要查找的目標姓名,以字符串形式傳入,用于和鏈表節點中存儲的姓名做對比* @return 找到匹配姓名的節點時,返回該節點的指針;遍歷完鏈表未找到時,返回 NULL */
DouLinkNode *FindDouLinkList(DouLinkList *dl, char *name)
{DouLinkNode* tmp = dl->head; // 從鏈表頭節點開始遍歷while (tmp) // 只要當前節點指針不為空,就持續遍歷{// 調用 strcmp 函數對比當前節點姓名和目標姓名,strcmp 返回 0 表示字符串相等if (0 == strcmp(tmp->data.name, name)) {return tmp; // 找到匹配姓名的節點,返回該節點指針}tmp = tmp->next; // 移動到下一個節點,繼續遍歷}return NULL; // 遍歷完所有節點都沒找到匹配姓名的,返回 NULL
}/*** @brief 在雙向鏈表中查找符合條件的節點* * 使用回調函數作為匹配條件,實現靈活的查找功能* * @param dl 指向雙向鏈表的指針* @param fun 回調函數指針,用于判斷節點是否符合條件* @param arg 傳遞給回調函數的參數,作為查找條件* @return 找到返回匹配節點的指針,未找到返回NULL*/
DouLinkNode *FindDouLinkList(DouLinkList *dl, PFUN fun, void *arg)
{DouLinkNode *tmp = dl->head; // 從頭部開始遍歷while (tmp) // 遍歷所有節點{// 調用回調函數判斷當前節點是否符合條件if (fun(&tmp->data, arg)){return tmp; // 找到匹配節點,返回該節點指針}tmp = tmp->next; // 移動到下一個節點}return NULL; // 未找到匹配節點
}/*** @brief 反轉雙向鏈表* * 將雙向鏈表的節點順序反轉,改變節點間的鏈接關系* * @param dl 指向雙向鏈表的指針* @return 成功返回0,無需反轉返回1*/
int ReverseDouLinkList(DouLinkList *dl)
{int size = GetSizeDouLinkList(dl);// 節點數小于2時無需反轉if (size < 2){printf("No need to reverse (size < 2)\n");return 1;}DouLinkNode *cur = dl->head; // 當前節點指針,從頭部開始DouLinkNode *Prev = NULL; // 保存前一個節點的指針while (cur != NULL){ DouLinkNode *tmp = cur->next; // 保存下一個節點,防止斷鏈cur->next = Prev; // 反轉當前節點的后繼指針,指向前一個節點cur->prev = tmp; // 反轉當前節點的前驅指針,指向后一個節點Prev = cur; // 更新前一個節點指針cur = tmp; // 移動到下一個節點}dl->head = Prev; // 反轉后,原尾節點成為新的頭節點return 0;
}/*** @brief 獲取雙向鏈表的節點數量* * @param dl 指向雙向鏈表的指針* @return 返回鏈表中的節點數量*/
int GetSizeDouLinkList(DouLinkList *dl)
{return dl->clen; // 直接返回節點計數值
}/*** @brief 修改雙向鏈表中符合條件的節點數據* @param dl 雙向鏈表的指針* @param fun 比較函數指針,用于查找目標節點* @param arg 傳給比較函數的參數(用于指定查找條件)* @param newdata 指向新數據的指針,將用此數據替換找到節點的數據* @return 0表示修改成功,1表示修改失敗(未找到節點)*/
int ModifyDouLinkList(DouLinkList *dl, PFUN fun, void *arg, DATATYPE *newdata)
{// 調用查找函數,根據fun和arg找到目標節點DouLinkNode *tmp = FindDouLinkList(dl, fun, arg);// 若未找到目標節點,打印錯誤信息并返回失敗if (NULL == tmp){printf("ModifyDouLinkList failure failure\n");return 1;}// 將新數據拷貝到找到的節點中(覆蓋原有數據)// 使用memcpy確保結構體所有成員都被正確替換memcpy(&tmp->data, newdata, sizeof(DATATYPE));// 修改成功,返回0return 0;
}/*** @brief 從雙向鏈表中刪除符合條件的節點* @param dl 雙向鏈表的指針* @param fun 比較函數指針,用于查找目標節點* @param arg 傳給比較函數的參數(用于指定查找條件)* @return 0表示刪除成功,1表示刪除失敗(未找到節點)*/
int DeleteDouLinkList(DouLinkList *dl, PFUN fun, void *arg)
{// 調用查找函數,根據fun和arg找到目標節點DouLinkNode *tmp = FindDouLinkList(dl, fun, arg);// 若未找到目標節點,打印錯誤信息并返回失敗if (NULL == tmp){printf("del failure\n");return 1;}// 情況1:刪除的是頭節點if (tmp == dl->head){// 將頭指針指向原頭節點的下一個節點dl->head = dl->head->next;// 若新頭節點存在,需要將其prev指針置為NULL(斷開與原頭節點的聯系)if (dl->head){dl->head->prev = NULL;}}// 情況2:刪除的是中間節點或尾節點else{// 若當前節點不是尾節點,需要將下一個節點的prev指向當前節點的前一個節點if (tmp->next){tmp->next->prev = tmp->prev;}// 將當前節點前一個節點的next指向當前節點的下一個節點tmp->prev->next = tmp->next;}// 釋放被刪除節點的內存,避免內存泄漏free(tmp);// 鏈表長度減1dl->clen--;// 刪除成功,返回0return 0;
}/*** @brief 銷毀整個雙向鏈表,釋放所有分配的內存* @param dl 雙向鏈表的指針* @return 0表示銷毀成功*/
int DestroyDouLinkList(DouLinkList *dl)
{DouLinkNode *tmp = NULL;// 循環刪除鏈表中的所有節點while (1){// 每次獲取當前頭節點tmp = dl->head;// 若頭節點為NULL,說明所有節點已刪除,退出循環if (NULL == tmp){break;}// 將頭指針移動到下一個節點dl->head = dl->head->next;// 釋放當前頭節點的內存free(tmp);}// 釋放鏈表結構體本身的內存free(dl);// 銷毀成功,返回0return 0;
}
雙向鏈表特點
雙向鏈表(Doubly Linked List)是一種更復雜的鏈表,它的每個節點不僅包含指向下一個節點的指針(next
),還包含指向前一個節點的指針(prev
)。
雙向遍歷
核心特點:可以從頭節點開始向后遍歷,也可以從尾節點開始向前遍歷。這是其與單向鏈表最根本的區別。
節點結構
每個節點包含三部分:
data
: 存儲數據。next
: 指針,指向下一個節點。prev
: 指針,指向前一個節點。
操作效率(與單向鏈表對比的核心優勢)
刪除特定節點:在已知某個節點指針的情況下,雙向鏈表可以在 O(1) 時間內刪除該節點,因為它可以直接通過?
prev
?指針找到前驅節點。而單向鏈表需要從頭遍歷才能找到前驅節點,時間復雜度為 O(n)。在特定節點前插入:同樣,在已知某個節點指針的情況下,雙向鏈表可以在 O(1) 時間內完成在其前面的插入操作。單向鏈表無法直接做到,仍需遍歷尋找前驅節點。
反向遍歷:需要反向遍歷鏈表(例如,從大到小輸出一個有序鏈表)時,雙向鏈表非常高效。單向鏈表則非常笨拙,通常需要借助棧等輔助數據結構,或者先反轉鏈表(這會修改原鏈表)。
缺點
內存開銷:每個節點都需要一個額外的指針來存儲前驅節點的地址。對于節點數據本身很小的鏈表(例如,只存儲一個整數),這個額外的指針開銷占比會很大。
操作復雜性:插入和刪除節點時,需要維護兩個方向的指針(
next
?和?prev
),共需要修改?4?個指針(在某些邊界情況下是 2 個)。而單向鏈表只需要修改?1?或?2?個指針。代碼實現上更復雜,容易出錯。
與單向鏈表的對比
特性 | 單向鏈表 (Singly Linked List) | 雙向鏈表 (Doubly Linked List) |
---|---|---|
節點結構 | data ,?next | data ,?next ,?prev |
遍歷方向 | 只能從頭到尾單向遍歷 | 可以雙向遍歷(從頭到尾或從尾到頭) |
內存占用 | 更小(每個節點少一個指針) | 更大(每個節點多一個指針) |
刪除操作 | 刪除已知節點的前驅節點很高效 (O(1)) 刪除已知節點本身需要找前驅,效率低 (O(n)) | 刪除已知節點本身非常高效 (O(1)) |
插入操作 | 只能在已知節點后插入?(O(1)) 在已知節點前插入需要找前驅,效率低 (O(n)) | 在已知節點前或后插入都非常高效 (O(1)) |
靈活性 | 較低 | 很高,前后移動都很方便 |
代碼復雜度 | 相對簡單 | 相對復雜,需要維護前后指針的完整性 |