[資料結構] 雙向環狀鏈結串列教學[3]: 刪除結點
在雙向環狀鏈結串列教學[2]: 插入結點的這一篇中,講述了如何在串列中的某一個結點之後插入結點,本篇介紹如何在串列中刪除結點
完整程式碼
刪除結點的函數: delete_node
主函數
首先這邊,我們調用delete_node的函數,首先刪掉第一個結點
int main()
{
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);
insert_node(&head, 45, 62);
insert_node(&head, 5, 23);
insert_node(&head, 128, 57);
insert_node(&head, 41, 30);
delete_node(&head, 5);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}
在delete_node函數這邊,會先去檢查第一個結點是否就是要刪除的數值,如果是的話,這裡會先把*start設定給第一個結點的下一個結點
這邊之所以要特別把第一個結點的處理與其他結點的處理分開的原因是如果第一個結點被釋放掉的話,需要再特別記錄目前的第一個結點的位置是什麼,如此程式碼在調用head的時候,可以正確地指出目前第一個結點的位置為何
if(value == current->data) {
*start = current->next;
do {
current = current->next;
}while(current->next !=ori_start);
current->next = *start;
(*start)->prev = current;
free(ori_start);
return;
}
接下來確認要刪除的數值是第一個結點,也就是if(value == current->data),這裡會先把*start,設定給current->next,也就是讓目前第一個結點的下一個結點,成為新的第一個結點
接著使用do-while的迴圈,走到最後一個結點,而這邊ori_start的設定就是第一個結點,所以確保current會停留在最後一個結點
這時候,由於*start已經是新的第一個結點了,將最後一個結點,也就是current的next,指向*start
current->next = *start;
而新的第一個結點*start的前一個結點,這時候會指向最後一個結點
(*start)->prev = current;
最後釋放舊的第一個結點,完成刪除第一個結點的動作
free(ori_start);
最後將示意圖變成更好讀的樣式
正向的執行結果
23 128 57 41 30 23
反向的執行結果
23 30 41 57 128 23
這個時候,如果在執行刪除第一個結點前後,印出第一個結點的位址
printf("Old first node address: %p\n", head);
delete_node(&head, 5);
printf("New first node address: %p\n", head);
可以看出head指向的位址的改變,注意這邊是使用筆者某一次的編譯結果,根據不同機器環境,不同次的執行結果,所被分配到記憶體位址的執行結果會不盡相同
Old first node address: 0x563ae72472a0
New node address: 0x563ae7247300
刪除數值為128的結點數值
int main()
{
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);
insert_node(&head, 45, 62);
insert_node(&head, 5, 23);
insert_node(&head, 128, 57);
insert_node(&head, 41, 30);
delete_node(&head, 5);
delete_node(&head, 128);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}
這時候,在delete_node函數中,由於不是第一個結點,所以執行的程式部分為以下這個區塊
當current的next的數值,如果等同於要刪掉的數值,就會開始執行相關的程式碼
do {
if(current->next->data == value) {
temp = current->next;
current->next = current->next->next;
current->next->prev = current;
free(temp);
return;
}
current = current->next;
}while(current != *start);
首先current的下一個結點,會被設定給temp,接著current的下下一個結點,會變成current的下一個結點
current->next = current->next->next;
接著current下一個結點的前一個結點,會變成current,注意這邊由於上一個程式碼的影響,所以current的下一個結點已經變成了數值為57的結點
current->next->prev = current;
最後就是釋放掉欲刪除的結點
free(temp);
正向輸出結果
23 57 41 30 23
反向輸出結果
23 30 41 57 23
刪除數值為30的結點
int main()
{
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);
insert_node(&head, 45, 62);
insert_node(&head, 5, 23);
insert_node(&head, 128, 57);
insert_node(&head, 41, 30);
delete_node(&head, 5);
delete_node(&head, 128);
delete_node(&head, 30);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}
輸出結果
正向輸出結果
23 57 41 23
反向輸出結果
23 41 57 23