[資料結構] 雙向環狀鏈結串列教學[2]: 插入結點
6 min readDec 27, 2023
在雙向環狀鏈結串列教學[1]: 新增與印出這一篇中,講述了如何在雙向環狀鏈結串列中新增結點,這一篇會介紹插入結點的方法
完整程式碼
插入結點的函數: insert_node
主函數
現在插入第一個結點,插在數值為45的結點之後
int main()
{
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);
insert_node(&head, 45, 62);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}
在insert_node中,如果找不到結點有這個數值,也就是if(insert_after_value == current->data)這個條件式不成立,那麼結點就會不斷的往下走一個,直到結點又走回第一個結點*start,就會離開迴圈
do {
if(insert_after_value == current->data) {
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->next = current->next;
current->next->prev = new_node;
current->next = new_node;
new_node->prev = current;
break;
}
current = current->next;
}while(current!=*start);
根據目前的鏈結串列,由於找不到數值為45的結點,所以這裡並不會插入數值為45的結點
新增數值為23的結點在數值為5的結點之後
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);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}
現在新增一個數值為23的結點
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
接著目前結點的下一個結點,會變成新結點的下一個結點
new_node->next = current->next;
目前結點的下一個結點的前一個結點,會是新結點
current->next->prev = new_node;
目前結點的下一個結點,會是新結點
current->next = new_node;
新結點的前一個結點,會是目前的結點
new_node->prev = current;
重新整理成橫向的鏈結串列是意圖,整個串列的數值為5 23 128 41
執行結果
正向輸出
5 23 128 41 5
反向輸出
5 41 128 23 5
新增數值為57的結點在數值為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);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}
輸出結果
正向輸出
5 23 128 57 41 5
反向輸出
5 41 57 128 23 5
新增數值為30的結點在數值為41的結點之後
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);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}
輸出結果
正向輸出
5 23 128 57 41 30 5
反向輸出
5 30 41 57 128 23 5