数据结构之单链表

目录

1 简介

2 单链表的基本概念

2.1 节点结构

 2.2 头插法与尾插法

3 代码实现 

3.1 头插法实现

3.2 尾插法实现

4 代码解析（部分）

4.1 头插法插入节点

4.2 尾插法插入节点

4.3 按索引插入节点

4.4 按索引删除节点

4.5 获取节点

4.6 核心操作分析

4.7 头插法与尾插法对比 

5 关键问题与优化 

5.1 内存泄漏预防

 5.2 错误处理

 5.3 反转链表算法

6 总结

1 简介

单链表是最基础的数据结构之一，它以动态存储的方式高效处理数据的插入和删除。本文将通过C语言代码实现两种单链表（头插法和尾插法），分析它们的核心操作，并对比其性能差异。

2 单链表的基本概念

2.1 节点结构

单链表的每个节点包含：

• 数据域：存储数据

• 指针域：指向下一个节点的地址

typedef struct node {
    int val;           // 数据域
    struct node* next; // 指针域
} ListNode;

 2.2 头插法与尾插法

• 头插法：新节点插入链表头部，时间复杂度为O(1)

• 尾插法：新节点插入链表尾部，需维护尾指针，时间复杂度为O(1)

3 代码实现 

3.1 头插法实现

// link.c
// 基于头插法的单链表
#include <stdio.h>
#include <stdlib.h>


// 节点
// 存储密度 4/12 = 33%
// 顺序表 > 单链表 > 双链表
// 哈希表(散列表) 存储密度比较小
typedef struct node
{
    int val;                // 数据域
    struct node *next;      // 指针域,当前节点的后继元素
} ListNode;

// 操作
void add(ListNode *list, int val);                  // 头插
void show(ListNode *list);                          // 打印链表
void insert(ListNode *list, int index, int val);    // 插入
void del(ListNode *list, int index);                // 删除
ListNode *get(ListNode *list, int index);           // 
int len(ListNode *list);                            // 计算链表长度

int size = 0;

int main(int argc, char const *argv[])
{
    // 头指针
    ListNode *head;
    head = malloc(sizeof(ListNode));
    // 空表
    head->next = NULL;

    add(head, 10);
    add(head, 20);
    add(head, 30);
    show(head);
    printf("大小:%d\n", size);
    // 在索引为2的位置插入666
    insert(head, 2, 666);
    show(head);
    printf("大小:%d\n", size);

    del(head, 0);
    show(head);

    printf("%d\n", get(head, 2)->val);
    return 0;
}

ListNode *get(ListNode *list, int index)
{
    ListNode *l = list;

    for (int i = index; i <= size; i++)
    {
        l = l->next;
    }
    return l;
}

void del(ListNode *list, int index)
{
    if (index == 0)
    {
        return;
    }

    ListNode *l = list;
    for (int i = index; i < size; i++)
    {
        l = l->next;
    }
    ListNode *temp = l->next;
    l->next = l->next->next;
    free(temp);
}

int len(ListNode *list)
{
    int len = 0;
    ListNode *n = list->next;
    while (n)
    {
        len++;
        n = n->next;
    }
    return len;
}

void insert(ListNode *list, int index, int val)
{
    ListNode *n = malloc(sizeof(ListNode));
    // free(n);
    n->val = val;
    for(int i = 0; i < size - index; i++)
    {
        list = list->next;
    }
    n->next = list->next;
    list->next = n;
    size++;
}

void show(ListNode *list)
{
    printf("--------------------\n");
    printf("链表:");
    ListNode *n = list->next;
    while (n)
    {
        printf("->%d", n->val);
        // 获得后继节点
        n = n->next;
    }
    printf("\n");
}

// O(1)
void add(ListNode *list, int val)
{
    ListNode *node;
    node = malloc(sizeof(ListNode));
    node->val = val;
    // 新节点指向头指针的后继节点
    node->next = list->next;
    // 头指针指向新节点
    list->next = node;
    size++;
}

3.2 尾插法实现

// link2.c
// 基于尾插法的单链表
#include <stdio.h>
#include <stdlib.h>

// 定义节点
struct node
{
    char data;         // 数据域
    struct node *next; // 指针域(后继节点)
};

typedef struct node Node;

// 定义链表
typedef struct list
{
    Node *head; // 头指针
    Node *tail; // 尾指针
    int size;   // 大小
} List;

void init(List *list);
void show(List *list);
void add(List *list, char ch);
void insert(List *list, int index, char ch);
void del(List *list, int index);
Node *get(List *list, int index);
void reverse(List *list);

int main(int argc, char const *argv[])
{
    List *list;
    list = malloc(sizeof(List));
    init(list);
    show(list);
    add(list, 'a');
    add(list, 'b');
    add(list, 'c');
    add(list, 'd');
    show(list);
    insert(list, 2, 'x');
    insert(list, 5, 'y');
    show(list);
    del(list, 0);
    show(list);
    reverse(list);
    show(list);
    return 0;
}

void reverse(List *list)
{
    Node *node = list->head->next; // 从头指针的下一个节点开始(第一个节点)
    Node *prev = NULL;             // 前一个节点
    Node *next = NULL;             // 下一个节点
    while (node != NULL)
    {
        next = node->next; // 保存下一个节点
        node->next = prev; // 当前节点的指针域指向前一个节点
        prev = node;       // 前一个节点指向当前节点
        node = next;       // 当前节点指向下一个节点
    }
    list->head->next = prev; // 头指针的下一个节点指向前一个节点
}

Node *get(List *list, int index)
{
    if (index < 0 || index > list->size)
    {
        printf("无法获取, 位置不合法\n");
        return NULL;
    }

    Node *node = list->head; // 从头指针开始
    for (int i = 0; i < index; i++)
    {
        node = node->next; // 指向下一个节点
    }

    return node;
}

void init(List *list)
{
    list->head = malloc(sizeof(Node));
    list->tail = malloc(sizeof(Node));
    list->head->next = NULL;       // 头指针指向空
    list->tail->next = list->head; // 尾指针指向头指针
    list->size = 0;
}

void add(List *list, char ch)
{
    Node *node = malloc(sizeof(Node));
    node->data = ch;               // 新节点的数据域赋值
    node->next = NULL;             // 新节点的指针域指向空
    list->tail->next->next = node; // 尾指针的下一个节点指向新节点
    list->tail->next = node;       // 尾指针指向新节点
    list->size++;                  // 节点大小自增
}

void show(List *list)
{
    printf("链表大小: %d\n", list->size); // 打印链表大小
    printf("遍历:");
    Node *node = list->head->next; // 从头指针的下一个节点开始(第一个节点)
    while (node != NULL)
    {
        printf("->%c", node->data); // 打印节点数据
        node = node->next;          // 指向下一个节点
    }

    // for (int i = 0; i < list->size; i++)
    // {
    //     printf("%c,", node->data); // 打印节点数据
    //     node = node->next;        // 指向下一个节点
    // }
    printf("\n");
}

// O(1)
void insert(List *list, int index, char ch)
{
    Node *node = get(list, index); // 获取指定位置的节点(前一个节点)

    Node *newNode = malloc(sizeof(Node));
    newNode->data = ch;         // 新节点的数据域赋值
    newNode->next = node->next; // 新节点的指针域指向当前节点的下一个节点
    node->next = newNode;       // 当前节点的指针域指向新节点
    list->size++;               // 节点大小自增
}

void del(List *list, int index)
{
    Node *node = get(list, index); // 获取指定位置的节点(前一个节点)

    Node *temp = node->next;       // 临时节点指向当前节点的下一个节点(待删除节点)
    node->next = node->next->next; // 当前节点的指针域指向当前节点的下一个节点的下一个节点
    free(temp);                    // 释放临时节点
    list->size--;                  // 节点大小自减
}

4 代码解析（部分）

4.1 头插法插入节点

void add(ListNode *list, int val) {
    ListNode *node = malloc(sizeof(ListNode));
    node->val = val;            // 新节点赋值
    node->next = list->next;    // 新节点指向原首节点
    list->next = node;          // 头节点指向新节点
    size++;                     // 链表长度+1
}

首先为新节点分配内存，然后将新节点的next指针指向原链表的第一个节点，接着将头节点的next指针指向新节点，最后更新链表长度。

4.2 尾插法插入节点

void add(List *list, char ch) {
    Node *node = malloc(sizeof(Node));
    node->data = ch;
    node->next = NULL;             // 新节点作为尾节点
    list->tail->next->next = node; // 原尾节点指向新节点
    list->tail->next = node;       // 更新尾指针
    list->size++;
}

首先为新节点分配内存，然后将新节点的next指针置为NULL，接着将原尾节点的next指针指向新节点，最后更新尾指针指向新节点并增加链表长度。

4.3 按索引插入节点

void insert(ListNode *list, int index, int val) {
    ListNode *n = malloc(sizeof(ListNode));
    n->val = val;
    for(int i = 0; i < size - index; i++) {
        list = list->next;
    }
    n->next = list->next;
    list->next = n;
    size++;
}

首先为新节点分配内存并赋值，然后遍历链表到目标位置的前驱节点，接着将新节点的next指针指向原位置节点，再将前驱节点的next指针指向新节点，最后更新链表长度。

4.4 按索引删除节点

void del(ListNode *list, int index) {
    ListNode *l = list;
    for (int i = index; i < size; i++) {
        l = l->next;
    }
    ListNode *temp = l->next;
    l->next = l->next->next;
    free(temp);
    size--;
}

首先遍历链表到目标位置的前驱节点，然后保存待删除节点的指针，接着将前驱节点的next指针指向待删除节点的下一个节点，最后释放待删除节点的内存并更新链表长度。

4.5 获取节点

ListNode *get(ListNode *list, int index) {
    ListNode *l = list;
    for (int i = index; i <= size; i++) {
        l = l->next;
    }
    return l;
}

首先从头节点开始遍历链表，直到移动到目标位置的前驱节点，然后返回该节点的指针。

4.6 核心操作分析

4.7 头插法与尾插法对比 

5 关键问题与优化 

5.1 内存泄漏预防

• 每次调用malloc后需在删除操作中调用free

void del(List* list, int index) {
    Node* temp = node->next;
    node->next = node->next->next;
    free(temp); // 释放节点内存
}

 5.2 错误处理

• 插入/删除时需验证索引合法性

if (index < 0 || index >= list->size) {
    printf("Error: Invalid index!\n");
    return;
}

 5.3 反转链表算法

void reverse(List* list) {
    Node *prev = NULL, *current = list->head->next, *next = NULL;
    while (current) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    list->head->next = prev;
}

6 总结

单链表作为动态存储结构的代表，通过头插法和尾插法展现了不同的数据管理策略。**头插法**以`O(1)`的时间复杂度在链表头部快速插入节点，适合逆序构建数据（如撤销操作），但会导致数据存储顺序与插入顺序相反。**尾插法**通过维护尾指针实现尾部`O(1)`插入，能严格保持数据顺序，适用于日志记录等场景。两种方法在删除、查找等操作上均需`O(n)`时间，体现了链表的遍历特性。

代码实现中，**头插法**通过直接操作头节点简化插入逻辑，而**尾插法**通过尾指针优化尾部操作，并支持高效反转（三指针法）。关键优化点包括：内存泄漏防护（及时释放删除节点）、索引合法性校验（避免越界错误）和反转算法设计。实际开发中，若需频繁尾部操作或顺序维护，尾插法更具优势；而头插法则在逆序场景中表现更优。理解两者的核心差异，结合具体需求选择实现方式，是提升程序效率的关键。