前導
環狀鏈結串列是一種特殊的鏈結串列，其最後一個節點的指標指向第一個節點，而非 NULL，形成一個循環結構。如下圖所示:
一、環狀鏈結串列的插入（Insertion）
插入新節點時，可能發生在：
- 空串列時的插入
- 頭部插入（Head insertion）
- 尾部插入（Tail insertion）
- 中間插入（After a given node）
1. 插入至空的環狀鏈結串列
當鏈結串列為空時，插入的節點既是head 也是 tail，並且它的 next 指向自己。- 創建新節點
newNode - 設定
newNode->next = newNode形成環狀 head = newNode，tail = newNode
2. 在頭部插入節點
- 創建新節點
newNode newNode->next = head（新節點指向當前頭部）tail->next = newNode（尾部節點指向新頭部）- 更新
head = newNode
👉 效果：新節點變成 head，但環狀結構保持不變。
3. 在指定節點後插入
- 找到目標節點
X newNode->next = X->nextX->next = newNode
👉 效果：新節點插入 X 之後，環狀結構保持。
4. 在尾部插入節點
- 創建新節點
newNode tail->next = newNode（當前尾部指向新節點）newNode->next = head（新節點指向head）- 更新
tail = newNode - 讀者可以自行思考並繪圖。
👉 效果：新節點變成 tail，環狀結構保持。
二、環狀鏈結串列的刪除（Deletion）
刪除節點時，可能發生在：
- 刪除頭部節點
- 刪除中間節點
- 刪除尾部節點
- 刪除最後一個節點（使串列變空）
1. 刪除頭部節點
head = head->next（更新head指向下一個節點）tail->next = head（尾部保持指向新的head）
👉 效果：原head 被移除，環狀結構保持。
2. 刪除中間節點
- 找到
X的前一個節點prev prev->next = X->next
👉 效果：節點 X 被移除，環狀結構保持。
3. 刪除尾部節點
- 找到
tail的前一個節點prev prev->next = head- 更新
tail = prev - 讀者可以自行思考並繪圖。
👉 效果：新 tail 成為 prev，環狀結構保持。
C語言實作
#include <stdio.h>
#include <stdlib.h>
// 定義節點結構
typedef struct Node {
int data;
struct Node* next;
} Node;
// 創建新節點
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = newNode; // 初始指向自己
return newNode;
}
// 插入到空的環狀鏈結串列
void insertEmpty(Node** head, int data) {
if (*head != NULL) return;
*head = createNode(data);
}
// 在頭部插入節點
void insertHead(Node** head, int data) {
if (*head == NULL) {
insertEmpty(head, data);
return;
}
Node* newNode = createNode(data);
newNode->next = *head;
// 找到 tail
Node* temp = *head;
while (temp->next != *head) temp = temp->next;
temp->next = newNode;
*head = newNode; // 更新 head
}
// 在尾部插入節點
void insertTail(Node** head, int data) {
if (*head == NULL) {
insertEmpty(head, data);
return;
}
Node* newNode = createNode(data);
Node* temp = *head;
while (temp->next != *head) temp = temp->next;
temp->next = newNode;
newNode->next = *head;
}
// 在指定節點後插入
void insertAfter(Node* prevNode, int data) {
if (prevNode == NULL) return;
Node* newNode = createNode(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
// 刪除頭部節點
void deleteHead(Node** head) {
if (*head == NULL) return;
// 只有一個節點
if ((*head)->next == *head) {
free(*head);
*head = NULL;
return;
}
Node* temp = *head;
while (temp->next != *head) temp = temp->next;
Node* toDelete = *head;
*head = (*head)->next;
temp->next = *head;
free(toDelete);
}
// 刪除尾部節點
void deleteTail(Node** head) {
if (*head == NULL) return;
// 只有一個節點
if ((*head)->next == *head) {
free(*head);
*head = NULL;
return;
}
Node* temp = *head;
Node* prev = NULL;
// 找到尾部與前一個節點
while (temp->next != *head) {
prev = temp;
temp = temp->next;
}
prev->next = *head; // 讓前一個節點變成新的尾部
free(temp);
}
// 刪除指定值的節點
void deleteNode(Node** head, int key) {
if (*head == NULL) return;
Node *curr = *head, *prev = NULL;
while (curr->data != key) {
if (curr->next == *head) return; // 沒找到
prev = curr;
curr = curr->next;
}
if (curr == *head) { // 如果刪除的是頭部
deleteHead(head);
return;
}
prev->next = curr->next;
free(curr);
}
// 列印環狀鏈結串列
void printList(Node* head) {
if (head == NULL) {
printf("什麼都沒有啦~哥!!");
return;
}
Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(head)\n");
}
// 主程式
int main() {
Node* head = NULL;
insertHead(&head, 10);
insertHead(&head, 20);
insertTail(&head, 30);
insertTail(&head, 40);
printList(head); // 20 -> 10 -> 30 -> 40 -> (head)
deleteHead(&head);
printList(head); // 10 -> 30 -> 40 -> (head)
deleteTail(&head);
printList(head); // 10 -> 30 -> (head)
insertAfter(head, 25); // 在 10 之後插入 25
printList(head); // 10 -> 25 -> 30 -> (head)
deleteNode(&head, 25);
printList(head); // 10 -> 30 -> (head)
deleteHead(&head); // 30 -> (head)
printList(head);
//deleteHead(&head); // 什麼都沒有啦~哥!!
//deleteTail(&head); // 什麼都沒有啦~哥!!
deleteNode(&head, 30); // 什麼都沒有啦~哥!!
printList(head);
return 0;
}
輸出:
20 -> 10 -> 30 -> 40 -> (head)
10 -> 30 -> 40 -> (head)
10 -> 30 -> (head)
10 -> 25 -> 30 -> (head)
10 -> 30 -> (head)
30 -> (head)
什麼都沒有啦~哥!!
主程式使用的函式總結
插入
insertHead(&head, data)→ 在頭部插入，當鏈結串列為空時呼叫insertEmpty(&head, data)。insertTail(&head, data)→ 在尾部插入insertAfter(Node* prevNode, data)→ 在指定節點後插入
刪除
deleteHead(&head)→ 刪除頭部節點deleteTail(&head)→ 刪除尾部節點deleteNode(&head, key)→ 刪除指定值的節點
額外
printList(head)→ 列印環狀鏈結串列
