单链表的基本概念

单链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指针域。数据域存储元素值，指针域存储下一个节点的地址。单链表通过指针将节点串联起来，形成链式结构。头指针指向链表的第一个节点，尾节点的指针域为NULL，表示链表结束。

单链表的节点结构

单链表的节点通常用结构体或类实现。以C语言为例，节点结构体定义如下：

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

单链表的基本操作

创建节点

动态分配内存创建新节点，并初始化数据域和指针域：

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

插入操作

在链表头部插入新节点：

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

在链表尾部插入新节点：

void insertAtTail(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

删除操作

删除指定值的节点：

void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;
    
    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);
}

遍历链表

打印链表所有节点值：

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

单链表的应用场景

单链表适用于频繁插入和删除操作的场景，因为其时间复杂度为O(1)。常见应用包括：

• 实现栈和队列
• 哈希表的链地址法解决冲突
• 图的邻接表表示
• 多项式运算

单链表的优缺点

优点：

• 动态大小，无需预先分配内存
• 插入和删除操作高效
• 内存利用率高

缺点：

• 不支持随机访问，查找效率低
• 需要额外空间存储指针
• 访问元素需要从头遍历

单链表的变体

为克服单链表的局限性，衍生出多种变体：

• 双向链表：每个节点包含前驱和后继指针，支持双向遍历
• 循环链表：尾节点指向头节点，形成环状结构
• 静态链表：用数组实现链表，通过游标代替指针

单链表的算法应用

反转链表

迭代法反转单链表：

struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* current = head;
    struct Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

检测环

使用快慢指针检测链表是否有环：

bool hasCycle(struct Node* head) {
    if (head == NULL) return false;
    
    struct Node* slow = head;
    struct Node* fast = head->next;
    
    while (fast != NULL && fast->next != NULL) {
        if (slow == fast) return true;
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

单链表的复杂度分析

| 操作 | 时间复杂度 | 空间复杂度 | |-------------|------------|------------| | 访问 | O(n) | O(1) | | 插入/删除头 | O(1) | O(1) | | 插入/删除尾 | O(n) | O(1) | | 查找 | O(n) | O(1) |

单链表的实现示例（完整代码）

以下是C语言实现的完整单链表示例：

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

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

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

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

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

int main() {
    struct Node* head = NULL;
    insertAtHead(&head, 5);
    insertAtHead(&head, 4);
    insertAtHead(&head, 3);
    printList(head);
    return 0;
}