一、链表概述

链表是一种常见的线性数据结构，它通过指针将一系列动态分配的节点（Node）串联起来。每个节点通常包含两部分：数据域（Data Field）和指针域（Pointer Field）。数据域存储实际数据，而指针域存储指向下一个节点的指针（对于双向链表，还会有一个指向前一个节点的指针）。相比数组，链表在插入、删除元素时具有更好的灵活性，因为不需要移动元素，只需更改相应节点的指针即可。

二、链表类型

1. 单链表（Singly Linked List） 每个节点只有一个指针，指向下一个节点。最后一个节点的指针通常设置为NULL，表示链表的结尾。

2. 双链表（Doubly Linked List） 每个节点有两个指针，一个指向前一个节点（前驱指针），一个指向后一个节点（后继指针）。双链表在双向遍历、插入和删除操作中更为方便。

3. 循环链表（Circular Linked List） 单链表或双链表的一种变体，其特点是最后一个节点的指针不再指向NULL，而是指向链表的头节点，形成一个环形结构。循环链表适用于需要循环遍历的场景。

三、链表操作

1. 创建链表 初始化链表头节点（通常包含一个空指针），然后通过动态内存分配（如malloc）创建新节点，并将新节点插入到链表中。

2. 插入节点

   • 头插法：在链表头部创建新节点，更新头节点指针。

   • 尾插法：找到链表尾部，创建新节点并更新尾节点的指针。

   • 指定位置插入：找到指定位置的前一个节点，创建新节点并更新前后节点的指针。

3. 删除节点

   • 删除头节点：更新头节点指针，释放头节点内存。

   • 删除指定节点：找到指定节点的前一个节点，更新其指针以跳过待删除节点，然后释放待删除节点内存。

   • 删除尾节点：找到倒数第二个节点，更新其指针为NULL，释放尾节点内存。

4. 遍历链表 从头节点开始，沿着指针逐个访问节点。对于单链表，只能向前遍历；对于双链表，可以向前或向后遍历。

5. 查找节点 从头节点开始，按照一定的查找条件（如根据节点数据或索引）遍历链表，找到满足条件的节点。

6. 合并链表 将两个已排序的链表合并为一个有序链表。

7. 反转链表 改变节点指针方向，使得链表的遍历顺序反转。

四、链表优缺点

优点：

• 动态分配内存，空间利用率高。

• 插入、删除操作（除头节点外）时间复杂度为O(1)，优于数组。

• 适用于频繁插入、删除的场景。

缺点：

• 需要额外的内存空间存储指针。

• 遍历效率相对数组较低，无法随机访问。

• 易于产生内存泄漏，需要仔细管理内存。

五、编程实践要点

1. 内存管理：使用malloc动态分配节点内存，操作完成后使用free释放。避免内存泄漏和悬挂指针。

2. 空指针检查：对链表操作中涉及的指针进行非空检查，防止空指针解引用引发程序崩溃。

3. 边界条件处理：在插入、删除、查找等操作中，考虑链表为空、只有一个节点等边界情况。

4. typedef 定义节点结构体：使用typedef定义节点结构体类型，提高代码可读性。

5. 函数封装：将链表的创建、插入、删除、遍历等操作封装为函数，提高代码复用性。

六、示例

• 单链表

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建链表
Node* create_list() {
    return NULL;
}

// 插入节点（尾插法）
void insert(Node** head, int value) {
    Node* new_node = (Node*) malloc(sizeof(Node));
    new_node->data = value;
    new_node->next = NULL;

    if (*head == NULL) {
        *head = new_node;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
    }
}

// 遍历链表
void traverse(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    puts("NULL");
}

int main() {
    Node* list = create_list();
    insert(&list, 1);
    insert(&list, 2);
    insert(&list, 3);

    printf("Traversing the list:\n");
    traverse(list);

    return 0;
}

• 双链表

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

// 双链表节点结构定义
typedef struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
} DNode;

// 创建空双链表
DNode* create_dlist() {
    return NULL;
}

// 创建新节点
DNode* create_node(int value) {
    DNode* new_node = (DNode*) malloc(sizeof(DNode));
    new_node->data = value;
    new_node->prev = NULL;
    new_node->next = NULL;
    return new_node;
}

// 头部插入节点
void insert_front(DNode** head, int value) {
    DNode* new_node = create_node(value);

    if (*head == NULL) {
        *head = new_node;
    } else {
        new_node->next = *head;
        (*head)->prev = new_node;
        *head = new_node;
    }
}

// 尾部插入节点
void insert_back(DNode** head, int value) {
    DNode* new_node = create_node(value);

    if (*head == NULL) {
        *head = new_node;
    } else {
        DNode* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
        new_node->prev = temp;
    }
}

// 遍历双链表（正向）
void traverse_forward(DNode* head) {
    DNode* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    puts("NULL");
}

// 遍历双链表（反向）
void traverse_backward(DNode* head) {
    DNode* temp = head;
    if (temp != NULL) {
        while (temp->next != NULL) {
            temp = temp->next;
        }
    }
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->prev;
    }
    puts("NULL");
}

int main() {
    DNode* dlist = create_dlist();
    insert_back(&dlist, 1);
    insert_back(&dlist, 2);
    insert_back(&dlist, 3);

    insert_front(&dlist, 4);
    insert_front(&dlist, 5);
    insert_front(&dlist, 6);

    printf("Forward traversal:\n");
    traverse_forward(dlist);

    printf("\nBackward traversal:\n");
    traverse_backward(dlist);

    return 0;
}

• 循环链表

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

// 双链表节点结构定义
typedef struct DNode
{
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

// 创建空循环双链表
DNode *create_circular_dlist()
{
    return NULL;
}

// 创建新节点
DNode *create_node(int value)
{
    DNode *new_node = (DNode *)malloc(sizeof(DNode));
    new_node->data = value;
    new_node->prev = NULL;
    new_node->next = NULL;
    return new_node;
}

// 头部插入节点
void insert_front(DNode **head, int value)
{
    DNode *new_node = create_node(value);

    if (*head == NULL)
    {
        *head = new_node;
        new_node->next = new_node; // 创建单节点循环链表
        new_node->prev = new_node; // 更新新节点的prev指针，指向自身
    }
    else
    {
        new_node->next = *head;
        new_node->prev = (*head)->prev; // 更新新节点的prev指针，指向原头节点的前一个节点
        (*head)->prev->next = new_node; // 更新原头节点前一个节点的next指针，指向新节点
        (*head)->prev = new_node;       // 更新原头节点的prev指针，指向新节点
        *head = new_node;               // 更新头指针为新节点
    }
}

// 尾部插入节点
void insert_back(DNode **head, int value)
{
    DNode *new_node = create_node(value);

    if (*head == NULL)
    {
        *head = new_node;
        new_node->next = new_node; // 创建单节点循环链表
    }
    else
    {
        DNode *temp = *head;
        while (temp->next != *head)
        {
            temp = temp->next;
        }
        temp->next = new_node;
        new_node->prev = temp;
        new_node->next = *head;
        (*head)->prev = new_node;
    }
}

// 遍历循环双链表（正向）
void traverse_forward(DNode *head)
{
    if (head == NULL)
    {
        return;
    }

    DNode *temp = head;
    do
    {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);

    puts("");
}

// 遍历循环双链表（反向）
void traverse_backward(DNode *head)
{
    if (head == NULL)
    {
        return;
    }

    DNode *temp = head->prev; // 从头节点的前一个节点开始反向遍历
    do
    {
        printf("%d -> ", temp->data);
        temp = temp->prev;
    } while (temp != head->prev);

    puts("");
}

int main()
{
    DNode *cdlst = create_circular_dlist();
    insert_front(&cdlst, 1); // 头部插入节点
    insert_front(&cdlst, 2); // 头部插入节点
    insert_front(&cdlst, 3); // 头部插入节点
    insert_back(&cdlst, 4);  // 尾部插入节点
    insert_back(&cdlst, 5);  // 尾部插入节点
    insert_back(&cdlst, 6);  // 尾部插入节点

    printf("Forward traversal:\n");
    traverse_forward(cdlst);

    printf("\nBackward traversal:\n");
    traverse_backward(cdlst);

    return 0;
}