单链表 - C语言实现

一、基本概念

单链表（Single Linked List）是一种线性表的链式存储结构。它由一系列节点组成，每个节点包含数据域和指向下一个节点的指针。

  • 链表的基本操作包括：初始化、头插法、尾插法、删除、插入、遍历
  • 与顺序表相比，链表的优势在于插入和删除操作不需要移动大量元素

二、结构体定义

1
2
3
4
5
typedef struct LNode
{
    int data;           // 节点的数据
    struct LNode* next; // 指针指向下一个节点
} * LinkNode;           // LinkNode 为结构体指针类型
成员 含义
data 节点的数据域，存储节点值
next 指向下一个节点的指针

说明： LinkNode 被定义为 struct LNode*，使用更方便

三、函数声明

1
2
3
4
5
6
void InistLinkNode(LinkNode *L);      // 初始化链表
void InsertLinkNode(LinkNode *L);     // 头插法插入节点
void TailInsertLinkNode(LinkNode *L);  // 尾插法插入节点
void DeleteLinkNode(LinkNode *L);     // 删除第i个元素
void IncreaseLinkNode(LinkNode *L);   // 在第i个位置插入元素
void PrintLinkNode(LinkNode *L);      // 遍历输出链表

四、功能函数实现

1. 初始化链表

1
2
3
4
5
void InistLinkNode(LinkNode *L)
{
    *L = (struct LNode *)malloc(sizeof(struct LNode));
    (*L)->next = NULL;
}
  • 通过 malloc() 分配头结点空间
  • 将头结点的 next 指针设为 NULL，表示空链表

2. 头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InsertLinkNode(LinkNode *L)
{
    int Length, x, j = 0;
    struct LNode* s;
    printf("Please num to insert :");
    scanf("%d", &Length);
    printf("Please Input what you want to insert :\n");

    for (j = 0; j < Length; j++)
    {
        s = (struct LNode*)malloc(sizeof(struct LNode));
        scanf("%d", &x);
        s->data = x;
        s->next = (*L)->next;
        (*L)->next = s;
    }
}

特点： 新插入的节点总是插入到链表头部，最后插入的节点在链表头部

3. 尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void TailInsertLinkNode(LinkNode *L)
{
    int Length, x, j = 0;
    struct LNode* s, *r = (*L); // r 为表尾指针
    printf("Please num to insert :");
    scanf("%d", &Length);
    printf("Please Input what you want to insert :\n");

    for (j = 0; j < Length; j++)
    {
        s = (struct LNode*)malloc(sizeof(struct LNode));
        scanf("%d", &x);
        s->data = x;
        r->next = s;
        r = s;
    }
}

特点： 需要维护一个尾指针 r，新节点插入到链表尾部，插入顺序与输入顺序一致

4. 删除第i个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void DeleteLinkNode(LinkNode *L)
{
    LinkNode p, q;
    int j = 0, x, e;
    printf("\n Please input Num of LinkNode : \n");
    scanf("%d", &x);

    p = *L;
    while (p != NULL && j < x - 1)
    {
        p = p->next;
        j++;
    }

    if (p == NULL)
    {
        printf("Error!");
        return;
    }
    if (p->next == NULL)
    {
        printf("NULL!");
        return;
    }

    q = p->next;         // q 为我们要删除的元素
    e = q->data;
    p->next = q->next;
    free(q);             // 及时释放被删除节点的空间
}

注意： 删除节点后一定要 free(q) 释放内存，避免内存泄漏

5. 在第i个位置插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void IncreaseLinkNode(LinkNode *L)
{
    printf("Please input what and num (e.g: what,num) : \n");
    int x, j = 0, e;
    scanf("%d,%d", &e, &x);

    LinkNode s = (*L);
    LinkNode r = (struct LNode *)malloc(sizeof(struct LNode));

    while (j < x - 1 && s != NULL)
    {
        j++;
        s = s->next;
    }

    r->data = e;
    r->next = s->next;
    s->next = r;
}

参数说明： e 为要插入的数据，x 为插入位置

6. 遍历输出

1
2
3
4
5
6
7
8
9
void PrintLinkNode(LinkNode *L)
{
    struct LNode *s = (*L)->next;
    while (s != NULL)
    {
        printf("%4d", s->data);
        s = s->next;
    }
}

五、使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
    LinkNode L;

    // 初始化链表
    InistLinkNode(&L);

    // 尾插法建立链表
    TailInsertLinkNode(&L);
    PrintLinkNode(&L);  // 输出: 1  2  3

    // 删除第i个元素
    DeleteLinkNode(&L);
    PrintLinkNode(&L);

    // 在第i个位置插入元素
    IncreaseLinkNode(&L);
    PrintLinkNode(&L);

    return 0;
}

六、图解头插法与尾插法

1
2
3
4
5
头插法过程（输入: 1 → 2 → 3）:
Head → [3] → [2] → [1] → NULL

尾插法过程（输入: 1 → 2 → 3）:
Head → [1] → [2] → [3] → NULL

七、涉及的头文件

头文件 作用
stdio.h 标准输入输出
stdlib.h malloc() 和 free() 函数

八、时间复杂度分析

操作 时间复杂度 说明
初始化 O(1) 只需分配头结点空间
头插法 O(n) 每次插入需要遍历链表（建表需n次）
尾插法 O(n) 每次插入需要遍历链表（建表需n次）
删除第i个元素 O(n) 需要找到第i-1个节点
在第i个位置插入 O(n) 需要找到第i-1个节点
遍历输出 O(n) 需遍历所有节点

九、关键知识点

  1. 链表的节点结构：data 存储数据，next 存储下一个节点的地址
  2. 头结点的作用：简化链表操作，头结点本身不存储有效数据
  3. 头插法与尾插法：头插法逆序，尾插法正序
  4. 内存管理：使用 malloc() 分配节点，free() 释放删除的节点
  5. 指针维护：插入时注意 s->next 和 p->next 的赋值顺序

十、完整代码下载

源代码文件：Single-Linked-List-from-Scratch-with-C.c