[資料結構] 雙向環狀鏈結串列教學[1]: 新增與印出
在之前的篇章中，介紹了鏈結串列、雙向鏈結串列以及環狀鏈結串列，這篇文章將介紹雙向環狀鏈結串列。所謂的雙向鏈結串列，英文名稱為doubly circular linked list，在這個資料結構中，串列的每個結點是可以前後互相連通的，並且當遍歷整個串列後，最後會回到最源頭的那個結點
完整程式碼
新增結點的函數: add_node
主函數
int main()
{
Node *head = NULL;
add_node(&head, 5);
inverse_print_list(head);
free_list(head);
return 0;
}這裡我們先建立第一個結點，這是第一個結點，所以這個不管是往前指還是往後指，都會是自己，也就是new_node->next = new_node，new_node->prev = new_node，最後再去確認，如果是新增第一個結點，也就是*start還沒有被真正設定，就讓設定的new_node等同於*start
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->next = new_node;
new_node->prev = new_node;
if(*start == NULL) {
*start = new_node;
return;
}
這時候創造完第一個結點後，就可以印出來確認是否創造doubly circular linked list成功
印出串列數值的函數: print_list
這邊的print_list函數，會讓第一個node先印出數值，接著讓指向下一個node，然後進入迴圈，這個迴圈地跳出條件為當node為第一個node的時候就會跳出，要不然就會印出目前的訊息，然後再往下指，跳出後還會再印出目前結點的數值，其實就是要印出第一個結點的數值。
void print_list(Node *node)
{
Node *first_node = node;
printf("%d ", node->data);
node = node->next;
while(node != NULL) {
if(node == first_node) break;
printf("%d ", node->data);
node = node->next;
}
printf("%d\n", node->data);
}對於只有一個結點的情況，印出數值5之後，由於是第一個結點，所以在迴圈的判斷中就會跳出，跳出迴圈後，接著再印出第一個結點的數值5
輸出結果
5 5反向印出串列數值的函數: inverse_print_list
其實調用的方法與print_list是一樣的，都是把第一個結點當作參數帶入到函數中，但是這邊將第一個結點命名為last_node，並且往前去走。這邊與print_list的方式一樣，先印出last_node的數值，接著將結點往前移，接著進入迴圈，如果是最後一個結點，就會跳出迴圈，如果不是的話，會印出結點內容，接著就會把結點往前移。
最後跳出迴圈的時候，會再印出最後一個結點的數值。
void inverse_print_list(Node *node)
{
Node *last_node = node;
printf("%d ", node->data);
node = node->prev;
while(node != NULL) {
if(node == last_node) break;
printf("%d ", node->data);
node = node->prev;
}
printf("%d\n", node->data);
}對於只有一個結點的情況，印出數值5之後，由於是最後一個結點，在迴圈的判斷中就會跳出，跳出迴圈後，會再印出最後一個結點的數值，其實數值就是5
5 5現在我們新增第二個數值為128的結點
int main()
{
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}新增第二個數值為128的結點後，此時在add_node的函數裡，因為不是屬於第一個結點，所以會執行else裡面的程式碼。
在else裡面的程式碼，其實就是宣告一個current的指標，並將*start設定為current，接下來就開始迭代這個鏈結串列，最後當迴圈走回到第一個結點的時候，就跳出迴圈。
這樣的程式碼就代表，經過迴圈的迭代之後，current會留在第一個結點的前一個結點
void add_node(Node **start, int value)
{
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->next = new_node;
new_node->prev = new_node;
if(*start == NULL) {
*start = new_node;
return;
}
else {
Node *current;
current = *start;
while(current->next != *start) {
current = current->next;
}
current->next = new_node;
new_node->prev = current;
new_node->next = *start;
(*start)->prev = new_node;
}
}此時就開始執行添加結點的第一個程式碼，將目前結點的下一個結點，指向new_node
current->next = new_node;
接著將這個數值為128的結點，往前指向數值為5的解點
new_node->prev = current;
新結點的下一個結點，將會指向第一個結點
new_node->next = *start;
第一個結點的前一個結點，會指向新結點
(*start)->prev = new_node;
最後執行程式碼，不管是正向印出，還是反向印出，都可以得到相同的結果
正向印出
5 128 5反向印出
5 128 5新增第三個數值為41的結點
int main()
{
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);
print_list(head);
inverse_print_list(head);
free_list(head);
return 0;
}新增完之後，doubly circular linked list的示意圖會如下
輸出結果為
正向印出
5 128 41 5反向印出
5 41 128 5釋放掉記憶體的函數: free_list
最後當所有鏈結串列都建置完成之後，就可以來釋放掉記憶體
這裡首先先設置一個total_node的變數，給予數值為1，接著開始使用迴圈迭代整個串列，以得到整個串列到底有多少結點
在確定有多少個結點之後，在這邊使用一個for迴圈，將current結點設定為第一個結點，並且讓current等同於temp，然後讓current變成下一個結點後，就釋放掉temp結點的記憶體，因為已經知道串列中到底有多少個結點，使用此方法讓迴圈整個走完之後，這樣就可以釋放掉整個雙向環狀鏈結串列的記憶體容量
void free_list(Node *node)
{
int total_node = 1;
Node *first = node;
node = node->next;
while(node != first) {
node = node->next;
total_node++;
}
Node *current = first;
Node *temp;
int i;
for(i = 0; i < total_node; i++) {
temp = current;
current = current->next;
free(temp);
}
}