← Back to COMP1511

Linked Lists - Core Notes

链表基础知识

链表是一种重要的动态数据结构，它通过指针将节点连接起来。与数组不同，链表的元素在内存中不必连续存储， 这使得插入和删除操作更加高效。本章将深入探讨链表的实现原理和C语言实现。

核心概念:
  • • 节点结构 (struct node)
  • • 指针操作
  • • 动态内存分配
  • • 链表遍历
学习目标:
  • • 理解链表的基本概念
  • • 掌握节点的创建和链接
  • • 实现基本的链表操作
  • • 分析链表的时间复杂度
前置知识:
  • • C语言基础
  • • 指针和内存管理
  • • 结构体 (struct)
  • • malloc 和 free

什么是链表？

链表是一种线性数据结构，其中的元素（称为节点）通过指针相互连接。每个节点包含两部分： 数据域（存储实际数据）和指针域（指向下一个节点）。

链表 vs 数组

数组特点:
  • 内存连续分配
  • 固定大小
  • 随机访问 O(1)
  • 插入删除 O(n)
链表特点:
  • 内存分散分配
  • 动态大小
  • 顺序访问 O(n)
  • 插入删除 O(1)

链表可视化:

10
→
20
→
30
NULL

head → [10|→] → [20|→] → [30|NULL]

节点的结构 (struct node)

在C语言中，我们使用结构体来定义链表节点。每个节点包含数据域和指向下一个节点的指针。 

// 定义链表节点结构
struct node {
    int data;           // 数据域：存储整数值
    struct node *next;  // 指针域：指向下一个节点
};

// 创建类型别名（可选）
typedef struct node Node;

关键要点：

  • 自引用结构： 结构体内部包含指向自身类型的指针
  • data字段： 可以是任何数据类型（int, char, struct等）
  • next指针： 指向链表中的下一个节点
  • NULL终止： 链表的最后一个节点的next指针指向NULL

创建和初始化节点

创建链表节点需要动态分配内存，并正确初始化节点的数据域和指针域。 

// 创建新节点的函数
struct node *create_node(int value) {
    // 1. 分配内存
    struct node *new_node = malloc(sizeof(struct node));
    
    // 2. 检查内存分配是否成功
    if (new_node == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    
    // 3. 初始化节点
    new_node->data = value;
    new_node->next = NULL;
    
    // 4. 返回新节点的地址
    return new_node;
}

内存管理要点：

  • malloc()： 动态分配内存，返回void*指针
  • sizeof()： 计算结构体的大小
  • 错误检查： 始终检查malloc是否返回NULL
  • 初始化： 设置data值，next指针置为NULL

链表遍历

遍历链表是最基本的操作，我们从头节点开始，依次访问每个节点，直到遇到NULL指针。 

// 打印链表中的所有元素
void print_list(struct node *head) {
    struct node *current = head;  // 从头节点开始
    
    printf("List: ");
    while (current != NULL) {
        printf("%d ", current->data);   // 打印当前节点的数据
        current = current->next;        // 移动到下一个节点
    }
    printf("-> NULL\n");
}

// 计算链表长度
int list_length(struct node *head) {
    int count = 0;
    struct node *current = head;
    
    while (current != NULL) {
        count++;
        current = current->next;
    }
    
    return count;
}

遍历过程演示:

Step 1: current → [10|→] → [20|→] → [30|NULL]
        打印: 10

Step 2: current -------→ [20|→] → [30|NULL]
        打印: 20

Step 3: current ---------------→ [30|NULL]
        打印: 30

Step 4: current → NULL (结束)

插入节点

链表的插入操作可以在不同位置进行：头部插入、尾部插入、或在指定位置插入。

1. 头部插入

// 在链表头部插入新节点
struct node *insert_at_head(struct node *head, int value) {
    // 1. 创建新节点
    struct node *new_node = create_node(value);
    
    // 2. 新节点指向原头节点
    new_node->next = head;
    
    // 3. 返回新的头节点
    return new_node;
}

头部插入过程:

原链表: head → [20|→] → [30|NULL]

Step 1: 创建新节点 [10|NULL]
Step 2: [10|→] → [20|→] → [30|NULL]
Step 3: head → [10|→] → [20|→] → [30|NULL]

2. 尾部插入

// 在链表尾部插入新节点
struct node *insert_at_tail(struct node *head, int value) {
    struct node *new_node = create_node(value);
    
    // 如果链表为空，新节点成为头节点
    if (head == NULL) {
        return new_node;
    }
    
    // 找到最后一个节点
    struct node *current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    // 连接新节点
    current->next = new_node;
    return head;
}

删除节点

删除节点需要小心处理指针，确保链表的连续性不被破坏，同时要释放被删除节点的内存。 

// 删除第一个包含指定值的节点
struct node *delete_node(struct node *head, int value) {
    if (head == NULL) {
        return head;  // 空链表，无需删除
    }
    
    // 如果要删除的是头节点
    if (head->data == value) {
        struct node *temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    
    // 找到要删除节点的前一个节点
    struct node *current = head;
    while (current->next != NULL && current->next->data != value) {
        current = current->next;
    }
    
    // 如果找到了要删除的节点
    if (current->next != NULL) {
        struct node *temp = current->next;
        current->next = temp->next;
        free(temp);
    }
    
    return head;
}

删除节点过程:

原链表: head → [10|→] → [20|→] → [30|NULL]
删除值为20的节点:

Step 1: 找到前驱节点 [10|→]
Step 2: temp → [20|→]
Step 3: [10|→] -------→ [30|NULL]
Step 4: free(temp)

结果: head → [10|→] → [30|NULL]

内存管理

正确的内存管理是链表编程的关键。我们必须确保所有动态分配的内存都被正确释放。 

// 释放整个链表的内存
void free_list(struct node *head) {
    struct node *current = head;
    struct node *next;
    
    while (current != NULL) {
        next = current->next;  // 保存下一个节点的地址
        free(current);         // 释放当前节点
        current = next;        // 移动到下一个节点
    }
}

// 主函数示例
int main() {
    struct node *head = NULL;
    
    // 插入节点
    head = insert_at_head(head, 10);
    head = insert_at_head(head, 20);
    head = insert_at_head(head, 30);
    
    // 打印链表
    print_list(head);
    
    // 删除节点
    head = delete_node(head, 20);
    print_list(head);
    
    // 释放内存
    free_list(head);
    
    return 0;
}

内存管理最佳实践：

  • 配对原则： 每个malloc()都要有对应的free()
  • 避免悬挂指针： free()后将指针设为NULL
  • 避免重复释放： 不要对同一指针多次调用free()
  • 程序结束前： 释放所有动态分配的内存

时间复杂度分析

理解链表各种操作的时间复杂度对于选择合适的数据结构非常重要。

访问操作

  • 按索引访问： O(n) - 需要遍历
  • 查找元素： O(n) - 线性搜索
  • 访问头节点： O(1) - 直接访问

修改操作

  • 头部插入/删除： O(1)
  • 尾部插入/删除： O(n)
  • 中间插入/删除： O(n)

常见错误和调试技巧

常见错误：

  1. 空指针解引用： 在使用指针前没有检查是否为NULL
  2. 内存泄漏： 忘记释放动态分配的内存
  3. 丢失链表头： 修改头指针时没有更新
  4. 循环链表： 错误的指针连接导致无限循环
// 安全的节点访问示例
void safe_print_data(struct node *node) {
    if (node != NULL) {           // 始终检查NULL
        printf("%d\n", node->data);
    } else {
        printf("Node is NULL\n");
    }
}

// 调试工具：打印链表结构
void debug_list(struct node *head) {
    printf("List structure: ");
    struct node *current = head;
    int count = 0;
    
    while (current != NULL && count < 10) {  // 防止无限循环
        printf("[%d|%p] -> ", current->data, (void*)current->next);
        current = current->next;
        count++;
    }
    printf("NULL\n");
}