什麼是雙鏈表？
雙鏈表是在操作系統中常用的數據結構，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅，其結點組成如下：
其示意圖舉例如下：
雙鏈表的操作示例
1、雙鏈表結點定義：
<code>/* 數據元素類型 */typedef int Type;/* 雙鏈表結點結構體 */typedef struct _DListNode{ struct _DListNode * prior; /* 指向直接前趨結點 */ struct _DListNode * next; /* 指向直接後繼結點 */ Type data; /* 數據 */ }DListNode;/<code>2、相關操作示例
<code>/* 函數聲明 */static DListNode *dlist_create(void);static int dlist_find(DListNode *dlist, Type find_data);static DListNode *dlist_change(DListNode *dlist, int pos, Type new_data);static DListNode *dlist_insert(DListNode *dlist, Type insert_data, int pos);static DListNode *dlist_delete(DListNode *dlist, Type del_data); static void dlist_print_int(DListNode *dlist);/<code>
（1）創建一個雙鏈表： （5，2，0，13，14）
示意圖：
代碼：
<code>static DListNode *dlist_create(void){ /* 創建第一個結點 */ DListNode *node = (DListNode*)malloc(sizeof(DListNode)); node->prior = NULL; node->next = NULL; node->data = list[0]; /* 創建頭指針並指向第一個結點 */ DListNode *head = node; /* 創建其它結點並鏈接成雙鏈表 */ for (int i = 1; i < LEN; i++) { /* 創建新結點 */ DListNode *new_node = (DListNode*)malloc(sizeof(DListNode)); new_node->next = NULL; new_node->prior = head; /* 關鍵點1：新結點的prior指針指向前驅結點 */ new_node->data = list[i]; /* 改變前驅結點的next指針指向 */ head->next = new_node; /* 關鍵點2：前驅結點的next指針指向新結點 */ /* 頭指針後移 */ head = head->next; } return node;}/<code>（2）元素查找：
<code>static int dlist_find(DListNode *dlist, Type find_data){ DListNode* temp = dlist; int pos = 1; while (temp) { if (find_data == temp->data) { return pos; } else { temp = temp->next; pos++; } } return ERROR;}/<code>（3）元素替換：
<code>static DListNode *dlist_change(DListNode *dlist, int pos, Type new_data){ DListNode* temp = dlist; for (int i = 1; i < pos; i++) { temp = temp->next; } temp->data = new_data; return dlist;}/<code>（4）結點插入：
- 頭部插入：
- 中間插入：
- 尾部插入：
<code>static DListNode *dlist_insert(DListNode *dlist, Type insert_data, int pos){ /* 創建新結點待插入 */ DListNode *new_node = (DListNode*)malloc(sizeof(DListNode)); new_node->next = NULL; new_node->prior = NULL; new_node->data = insert_data; if (pos > LEN + 1) { printf("插入的位置錯誤!\\n"); } /* 頭部插入 */ if (1 == pos) { dlist->prior = new_node; /* 步驟1 */ new_node->next = dlist; /* 步驟2 */ dlist = new_node; /* 步驟3 */ } else { DListNode *temp = dlist; for (int i = 1; i < pos-1; i++) { temp = temp->next; } /* 中間插入 */ if (temp->next != NULL) { new_node->next = temp->next; /* 步驟1 */ new_node->prior = temp; /* 步驟2 */ temp->next->prior = new_node; /* 步驟3 */ temp->next = new_node; /* 步驟4 */ } /* 尾部插入 */ else { temp->next = new_node; /* 步驟1 */ new_node->prior = temp; /* 步驟2 */ } } return dlist;}/<code>（5）結點刪除：
<code>static DListNode *dlist_delete(DListNode *dlist, Type del_data){ DListNode *temp = dlist; while (temp) { if (del_data == temp->data) { temp->next->prior = temp->prior; temp->prior->next = temp->next; free(temp); return dlist; } temp = temp->next; } return dlist;}/<code>3、驗證
主函數：
<code>int main(void){ printf("創建一個雙鏈表:"); DListNode *dlist = dlist_create(); dlist_print_int(dlist); printf("元素13所在的位置是:"); int pos = dlist_find(dlist, 13); if (ERROR == pos) { printf("該元素不存在。\\n"); } else { printf("%d\\n", pos); } printf("把第1個位置的元素替換為2020得到新的雙鏈表為:"); dlist = dlist_change(dlist, 1, 2020); dlist_print_int(dlist); printf("第2個位置插入888得到新的雙鏈表為:"); dlist = dlist_insert(dlist, 888, 2); dlist_print_int(dlist); printf("刪除元素2得到新的雙鏈表為："); dlist = dlist_delete(dlist, 2); dlist_print_int(dlist); return 0;}/<code>運行結果：
最後
以上就是本次分享的雙鏈表的筆記，希望各位喜歡！如有錯誤歡迎指出。以上代碼僅用於學習使用，可能沒有那麼完善、嚴謹，還望諒解。最後，如果可以的話，麻煩幫忙分享、轉發、再看，謝謝。
分享到:
閱讀更多 嵌入式大雜燴 的文章
