在计算机科学中，数据结构是组织和存储数据的方式。线性表是最基本的一种数据结构，它表示一组元素的有序序列。本文将探讨线性表的链式存储及其运算实现，从单链表到循环列表，再到双向链表进行详细介绍。

一、单链表

1.1 定义与结构

单链表（Singly Linked List）是最简单的链表形式。它由一系列节点组成，每个节点包含数据部分和一个指向下一个节点的指针。以下是单链表的基本结构：

struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
};

typedef struct Node Node;

1.2 基本操作

1.2.1 初始化链表

void initList(Node **head) {
    *head = NULL;
}

1.2.2 插入节点

在链表头部插入一个新节点：

void insertAtHead(Node **head, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

1.2.3 删除节点

根据数据值删除一个节点：

void deleteNode(Node **head, int key) {
    Node *temp = *head, *prev;
    
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    if (temp == NULL) return;
    
    prev->next = temp->next;
    free(temp);
}

1.2.4 遍历链表

打印链表中的所有节点：

void printList(Node *node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

二、循环链表

2.1 定义与结构

循环链表（Circular Linked List）是一种特殊的单链表，其尾节点指向头节点。以下是循环链表的基本结构：

struct CircularNode {
    int data;
    struct CircularNode *next;
};

typedef struct CircularNode CircularNode;

2.2 基本操作

2.2.1 初始化循环链表

void initCircularList(CircularNode **head) {
    *head = NULL;
}

2.2.2 插入节点

在循环链表头部插入一个新节点：

void insertAtHeadCircular(CircularNode **head, int data) {
    CircularNode *newNode = (CircularNode *)malloc(sizeof(CircularNode));
    newNode->data = data;
    
    if (*head == NULL) {
        newNode->next = newNode; // 指向自己，形成循环
    } else {
        CircularNode *temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = *head;
    }
    
    *head = newNode;
}

2.2.3 删除节点

根据数据值删除一个节点：

void deleteNodeCircular(CircularNode **head, int key) {
    if (*head == NULL) return;
    
    CircularNode *temp = *head, *prev;
    
    if (temp->data == key && temp->next == temp) { // 只有一个节点的情况
        *head = NULL;
        free(temp);
        return;
    }
    
    while (temp->data != key) {
        prev = temp;
        temp = temp->next;
        
        if (temp == *head) {
            printf("Node not found\n");
            return;
        }
    }
    
    if (temp == *head && temp->next != temp) { // 头节点的情况
        while (prev->next != *head) prev = prev->next;
        prev->next = temp->next;
        *head = temp->next;
    } else {
        prev->next = temp->next;
    }
    
    free(temp);
}

三、双向链表

3.1 定义与结构

双向链表（Doubly Linked List）是一种更复杂但功能更强大的链表形式，每个节点包含两个指针：一个指向后继节点，另一个指向前驱节点。以下是双向链表的基本结构：

struct DoublyNode {
    int data;
    struct DoublyNode *next, *prev;
};

typedef struct DoublyNode DoublyNode;

3.2 基本操作

3.2.1 初始化双向链表

void initDoublyList(DoublyNode **head) {
    *head = NULL;
}

3.2.2 插入节点

在双向链表头部插入一个新节点：

void insertAtHeadDoubly(DoublyNode **head, int data) {
    DoublyNode *newNode = (DoublyNode *)malloc(sizeof(DoublyNode));
    newNode->data = data;
    
    if (*head == NULL) {
        newNode->next = NULL;
        newNode->prev = NULL;
    } else {
        newNode->next = *head;
        (*head)->prev = newNode;
    }
    
    *head = newNode;
}

3.2.3 删除节点

根据数据值删除一个节点：

void deleteNodeDoubly(DoublyNode **head, int key) {
    DoublyNode *temp = *head;
    
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        
        if (*head != NULL) {
            (*head)->prev = NULL;
        }
        
        free(temp);
        return;
    }
    
    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }
    
    if (temp == NULL) return;
    
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }
    
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    
    free(temp);
}

四、总结

本文从单链表开始，介绍了其基本结构和操作。接着引入了循环链表，展示了如何在头部插入节点以及删除节点的实现方法。最后，讨论了双向链表的特性和相关操作。通过这些内容的学习，读者可以掌握不同类型链表的基本原理及其应用场景。