C 語言實現雙向循環鏈表：創建、遍歷、查找與內存管理完整教程

數據結構定義

typedef struct Node {
    char name[20];
    struct Node *llink;  // 前驅
    struct Node *rlink;  // 後繼
} Student;

帶頭結點的雙向循環鏈表：
head->rlink 指向首元結點，head->llink 指向尾結點。
首元結點 llink → head，尾結點 rlink → head。

核心操作實現

1. 創建鏈表（尾插法）

Student* create(int n) {
    Student *head = (Student*)malloc(sizeof(Student));
    if (!head) { perror("malloc"); exit(1); }
    head->name[0] = '\0';
    head->llink = head->rlink = NULL;
    Student *p = head;
    for (int i = 0; i < n; ++i) {
        Student *s = (Student*)malloc(sizeof(Student));
        if (!s) { perror("malloc"); exit(1); }
        printf("請輸入第 %d 個人的姓名: ", i+1);
        scanf("%19s", s->name);  // 防溢出
        // 尾插
        p->rlink = s;
        s->llink = p;
        s->rlink = NULL;  // 暫時
        p = s;
    }
    // 首尾閉環
    head->llink = p;
    p->rlink = head;
    return head;
}

2. 遍歷輸出

void print(Student *head) {
    Student *p = head->rlink;
    printf("數據信息為：\n");
    while (p != head) {
        printf("%s ", p->name);
        p = p->rlink;
    }
    printf("\n");
}

3. 按姓名查找

Student* search(Student *head, const char *target) {
    Student *p = head->rlink;
    while (p != head) {
        if (strcmp(p->name, target) == 0) return p;
        p = p->rlink;
    }
    printf("沒有查找到該數據！\n");
    return NULL;
}

主函數測試

int main() {
    int n = 10;
    Student *head = create(n);
    print(head);
    char target[20];
    printf("請輸入要查找的姓名: ");
    scanf("%19s", target);
    Student *found = search(head, target);
    if (found) printf("找到: %s\n", found->name);
    // 釋放內存（練習：編寫 destroy 函數）
    return 0;
}

關鍵點總結

• 頭結點不存放有效數據，簡化插入/刪除邊界條件。
• 雙向鏈表插入/刪除需同時維護 llink 和 rlink 四個指針關係。
• malloc 失敗必須檢查，教學代碼常省略但生產環境不可省。
• scanf("%19s", ...) 限制寬度防止緩衝區溢出。
• 循環鏈表遍歷終止條件：p != head。

進階擴展：插入與刪除

// 在 p 之後插入 s
s->rlink = p->rlink;
s->llink = p;
p->rlink->llink = s;
p->rlink = s;

// 刪除 p
p->llink->rlink = p->rlink;
p->rlink->llink = p->llink;
free(p);

雙向循環鏈表是實現 LRU Cache、雙端隊列、文本編輯器緩衝區的經典基礎結構。