环形链表 C语言实现

环形链表是一种特殊的链表结构，它的尾节点指向头节点，形成一个循环。在C语言中实现环形链表，你需要定义一个节点结构，并包含一个额外的指针字段用于存储前驱节点，同时更新头结点和尾节点的操作也需要特别处理。

下面是一个简单的环形链表节点定义以及基本操作的示例：

#include <stdio.h>
#include <stdlib.h>

// 定义环形链表节点
typedef struct Node {
    int data;
    struct Node* next; // 指向下一个节点
    struct Node* prev; // 指向前一个节点，环形链表特有的
} Node;

// 创建新节点并初始化
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    newNode->data = value;
    newNode->next = newNode->prev = NULL; // 初始化为环形
    return newNode;
}

// 插入节点到环形链表
void insertNode(Node** head, int value) {
    Node* newNode = createNode(value);
    if (*head == NULL) { // 链表为空，设置头尾为当前节点
        *head = newNode;
        newNode->prev = newNode->next = newNode;
    } else {
        newNode->next = *head; // 新节点的next指向头节点
        newNode->prev = (*head)->prev; // 新节点的prev指向头节点的前一个节点
        (*head)->prev->next = newNode;
        (*head)->prev = newNode;
        if ((*head)->prev == newNode) { // 如果插入后头节点变成新的头节点，则更新头结点
            *head = newNode;
        }
    }
}

// 打印环形链表
void printList(Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    Node* current = head;
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head); // 循环直到回到头节点
    printf("\n");
}

int main() {
    Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);

    printList(head);

    return 0;
}