文章目錄

• • • • 前言
      • 頭插法
      • 尾插法
      • 刪除節(jié)點
      • 測試代碼如下

前言

雙向鏈表和單鏈表的唯一區(qū)別就是多個一個指針域而已，該指針域可以訪問鏈表的上一個節(jié)點。

關(guān)于構(gòu)造雙向鏈表的過程我們常見的有兩種方法，和單鏈表一樣：頭插法和尾插法。
頭插法：字面意思也是很好理解，每次插入的元素在上一個節(jié)點之前
尾插法：字面意思也表達出了每次的元素插入會在上一個節(jié)點之后
詳細插入過程可以參考如下

---

頭插法

頭插法基本過程如下圖，已經(jīng)描述的很清楚了

簡單講一下，這里需要有一個指向的順序問題
第三步和第四步是需要有先后關(guān)系的
第三步： head -> next -> prev = p ，這一步是更新head節(jié)點下一個節(jié)點的pre域鏈接的；而第四步: head -> next = p，則是更新head的next域。
如果第四步在前，第三步的head -> next -> prev 就變?yōu)榱?p -> prev = p，顯然不合理。

實現(xiàn)算法如下（文末有完整源碼）

Data *insert_head(int n) {Data *head = (Data *)malloc(sizeof(Data));head->next = NULL;head -> prev = head;Data *r = head -> next;while (n--){int tmp;Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &tmp);p -> data = tmp;/*考慮頭節(jié)點的next域為空，防止訪第3步head->next->prev訪問到空的指針*/if (head -> next == NULL) { p -> next = NULL;p -> prev = head;head -> next = p;} else{p -> next = head -> next;p -> prev = head;head -> next -> prev = p;head -> next = p;}}return head -> next;
}

尾插法

具體步驟如下：

具體指向的過程看圖就可以，非常清晰
這里多了一個第五步，是為了保證臨時節(jié)點r的移動，持續(xù)指向插入節(jié)點的上一個節(jié)點。
實現(xiàn)代碼如下:

Data *insert_tail(int n){Data *head = (Data *)malloc(sizeof(Data));head->next = NULL;head -> prev = head;Data *r = head;while (n --){int tmp;Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &tmp);p -> data = tmp;/*同樣為了防止第三部 r->next->prev訪問到了空節(jié)點，提前進行處理*/if (r -> next == NULL) {p -> next = NULL;p -> prev = r;r -> next = p;} else  {p -> next = NULL;p ->prev = r;r -> next -> prev = p;r -> next = p;}r = p;}return head -> next;
}

刪除節(jié)點

刪除過程很簡單，主要是上下節(jié)點的直接指向：

1. 找到要刪除的節(jié)點p，以及其上一個節(jié)點r
2. 重新指向r的next域，跳過需要刪除的節(jié)點

Data *delete_list(Data *head, int data) {Data *p;Data *r = head ;/*找到要刪除的節(jié)點，命名為p，同時需要獲取p的上一個節(jié)點r*/while (r->next) {if (r-> next ->data == data) {p = r->next;break;}r = r->next;}/*刪除節(jié)點p*/r->next = p -> next;p->next->prev = r;p = NULL;return head;
}

測試代碼如下

#include <stdio.h>
#include <stdlib.h>typedef struct DoubleLink {int data;struct DoubleLink *next;struct DoubleLink *prev;
}Data;/*打印鏈表,先next順序打印，再prev逆序打印*/
void print_list(Data *head) {if(head == NULL)return;printf("next \n");while (head -> next) {printf("%d ",head->data);head = head -> next;}printf("%d\n",head->data);Data *p = head;printf("\nprev \n");while (p -> prev != p) {printf("%d ",p->data);p = p ->prev;}printf("\n");
}/*尾插法*/
Data *insert_tail(int n){Data *head = (Data *)malloc(sizeof(Data));head->next = NULL;head -> prev = head;Data *r = head;while (n --){int tmp;Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &tmp);p -> data = tmp;if (r -> next == NULL) {p -> next = NULL;p -> prev = r;r -> next = p;} else  {p -> next = NULL;p ->prev = r;r -> next -> prev = p;r -> next = p;}r = p;}return head -> next;
}/*頭插法*/
Data *insert_head(int n) {Data *head = (Data *)malloc(sizeof(Data));head->next = NULL;head -> prev = head;Data *r = head -> next;while (n--){int tmp;Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &tmp);p -> data = tmp;if (head -> next == NULL) {p -> next = NULL;p -> prev = head;head -> next = p;} else{p -> next = head -> next;p -> prev = head;head -> next -> prev = p;head -> next = p;}}return head -> next;}/*刪除鏈表,刪除節(jié)點data為2的鏈表*/
Data *delete_list(Data *head, int data) {if(head == NULL)return NULL;Data *p;Data *r = head ;while (r->next) {if (r-> next ->data == data) {p = r->next;break;}r = r->next;}r->next = p -> next;p->next->prev = r;p = NULL;return head;
}int main()
{printf("construct the double list tail\n");Data * head = insert_tail(5);print_list(head);printf("construct the double list head\n");Data * tail = insert_head(5);print_list(tail);printf("delete the double list node\n");Data * test = insert_head(5);Data *result = delete_list(test,2);print_list(result);return 0;
}

輸出結(jié)果如下:

construct the double list tail
1 2 3 4 5next 
1 2 3 4 5
prev 
5 4 3 2 1 construct the double list head
1 2 3 4 5next 
5 4 3 2 1
prev 
1 2 3 4 5 delete the double list node
1 2 3 4 5
next 
5 4 3 1
prev 
1 3 4 5 

總結(jié)

以上是生活随笔為你收集整理的C语言的双向链表头插法和尾插法，指定节点删除的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。