C 语言链表入门详解

一、链表定义

1.什么是链表

链表是一种动态数据结构，由一系列节点组成，每个节点包含两部分：

• 数据域：存储实际数据
• 指针域：存储指向下一个节点的地址

与数组不同。例如，在定义一个班级的人数时，如果小班是 30 人，普通班级是 50 人，且定义班级人数时使用的是数组，那么定义数组的大小应为最大人数，也就是最少为 50 个元素，否则不满足最大时的情况，这种方式非常浪费空间。

这时就希望有一种存储方式，其存储元素的个数是不受限制的，当添加元素时存储元素的个数就会随之改变，这种存储方式就是链表。链表的元素在内存中不是连续存储的，而是通过指针连接起来。

链表结构的示意图如下图所示：

图 1 链表结构的示意图

从图 1 可以看到，head（头）节点指向第 1 个元素，第 1 个元素中的指针又指向第 2 个元素的地址，第 2 个元素的指针又指向第 3 个元素的地址，第 3 个元素的指针指向空。

注意，链表这种数据结构必须利用指针才能实现，因此链表中的节点应该包含一个指针变量来保存下一个节点的地址。

例如，设计一个链表表示一个班级，其中链表中的节点表示学生，代码如下：

struct Student { 
    char cName[20]; /*姓名*/ 
    int iNumber; /*学号*/ 
    struct Student* pNext; /*指向下一个节点的指针*/ 
};

可以看到学生的姓名和学号属于数据部分，而 pNext 就是指针部分，用来保存下一个节点的地址。

2.链表与数组对比

特性	数组	链表
内存分配	静态，编译时确定	动态，运行时分配
内存连续性	连续	不连续
插入/删除效率	O(n)	O(1)（已知位置）
访问效率	O(1)	O(n)
大小	固定	可动态调整

二、链表基本结构

1.链表类型

1. 单向链表：每个节点只有一个指向下一个节点的指针
2. 双向链表：每个节点有指向前一个和后一个节点的指针
3. 循环链表：尾节点指向头节点形成环

2.节点定义

// 定义链表节点
struct ListNode {
    int data; // 数据域
    struct ListNode *next; // 指针域，指向下一个节点
};
// 为了方便，通常使用 typedef
typedef struct ListNode {
    int data;
    struct ListNode *next;
} Node;

三、基本操作

1.创建链表

从前面的讲解不难看出，链表并不是一开始就设定好大小的，而是根据节点的多少确定的，因此链表的创建过程是一个动态的过程。

1) 基本方法创建链表

定义一个 Create() 函数，用来创建链表。该函数会返回链表的头指针，代码如下：

int iCount; /*全局变量表示链表长度*/
struct Student* Create() {
    struct Student* pHead = NULL; /*初始化链表头指针，使其为空*/
    struct Student* pEnd, *pNew;
    iCount = 0; /*初始化链表长度*/
    pEnd = pNew = (struct Student*)malloc(sizeof(struct Student));
    printf("please first enter Name ,then Number\n");
    scanf("%s", &pNew->cName);
    scanf("%d", &pNew->iNumber);
    while (pNew->iNumber != 0) {
        iCount++;
        if (iCount == 1) {
            pNew->pNext = pHead; /*使得指向为空*/
            pEnd = pNew; /*跟踪新加入的节点*/
            pHead = pNew; /*头指针指向首节点*/
        } else {
            pNew->pNext = NULL; /*新节点的指针为空*/
            pEnd->pNext = pNew; /*原来的尾节点指向新节点*/
            pEnd = pNew; /*pEnd 指向新节点*/
        }
        pNew = (struct Student*)malloc(sizeof(struct Student)); /*再次分配节点内存空间*/
        scanf("%s", &pNew->cName);
        scanf("%d", &pNew->iNumber);
    }
    free(pNew); /*释放没有用到的空间*/
    return pHead;
}

从上述代码中可以看出以下内容：

1. Create() 函数的功能是创建链表，在 Create() 的外部有一个整型的全局变量 iCount，这个变量的作用是表示链表中节点的数量。在 Create() 函数中，首先定义需要用到的指针变量，pHead 表示头节点，pEnd 指向原来的尾节点，pNew 指向新创建的节点。
2. 使用 malloc() 函数分配内存，先使 pEnd 和 pNew 两个指针都指向第一个分配的内存，然后输出提示信息，先输入一个学生的姓名，再输入学生的学号。使用 while 语句进行判断，如果学号为 0，则不执行循环语句。
3. 在 while 循环语句中，iCount++ 自加操作表示链表中节点的增加。然后要判断新加入的节点是否为第一次加入的节点，如果为第一次加入的则运行 if 语句块中的代码，否则运行 else 语句块中的代码。
4. 在 if 语句块中，因为第一次加入节点时其中没有节点，所以新节点即首节点，也为最后一个节点，并且要将新加入的节点的指针指向空，即 pHead 的指向。else 语句块实现的是链表中已经有节点存在时的操作。
5. 首先将新节点 pNew 的指针指向空，然后将原来最后一个节点的指针指向新节点，最后将 pEnd 的指针指向最后一个节点。这样节点创建完之后，要再次分配内存，然后向其中输入数据，通过 while 语句再次判断输入的数据是否符合节点的要求。当不符合要求时，调用 free() 函数将不符合要求的节点空间进行释放。

这样，链表就通过动态分配内存空间的方式创建完成了。

2）其他方法

首先先创建节点

#include <stdio.h>
#include <stdlib.h>
// 节点定义
typedef struct Node {
    int data;
    struct Node *next;
} Node;
// 创建新节点
Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

*1.头插法创建链表

// 头插法 - 新节点插入在链表头部
Node* insertAtHead(Node *head, int data) {
    Node *newNode = createNode(data);
    newNode->next = head;
    return newNode; // 返回新的头节点
}

*2.尾插法创建链表

// 尾插法 - 新节点插入在链表尾部
Node* insertAtTail(Node *head, int data) {
    Node *newNode = createNode(data);
    // 如果链表为空，新节点就是头节点
    if (head == NULL) {
        return newNode;
    }
    // 找到最后一个节点
    Node *current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

2.链表的输出

链表已经被创建出来，构建数据结构就是为了使用它，以将保存的信息进行输出。接下来介绍如何将链表中的数据输出。代码如下：

void print(struct Student* pHead) {
    struct Student *pTemp; /*循环所用的临时指针*/
    int iIndex = 1; /*表示链表中节点的序号*/
    printf("----the List has %d members:----\n", iCount); /*提示信息*/
    printf("\n"); /*换行*/
    pTemp = pHead; /*指针得到首节点的地址*/
    while (pTemp != NULL) {
        printf("the NO%d member is:\n", iIndex);
        printf("the name is: %s\n", pTemp->cName); /*输出姓名*/
        printf("the number is: %d\n", pTemp->iNumber); /*输出学号*/
        printf("\n"); /*换行*/
        pTemp = pTemp->pNext; /*移动临时指针到下一个节点*/
        iIndex++; /*进行自加运算*/
    }
}

结合创建链表和输出链表的过程，运行程序，结果为：

please first enter Name ,then Number
dahua 1
xiaoning 2
daxhuang 3
lucy 4
exit 0
----the List has 4 members:----
the N01 member is:
the name is: dahua
the number is: 1
the N02 member is:
the name is: xiaoning
the number is: 2
the N03 member is:
the name is: daxhuang
the number is: 3
the N04 member is:
the name is: lucy
the number is: 4

printf() 函数用来将链表中的数据进行输出。在函数的参数中，pHead 表示一个链表的头节点。在函数中，定义一个临时的指针 pTemp 用来进行循环操作。定义一个整型变量表示链表中的节点序号。然后使用临时指针变量 pTemp 保存首节点的地址。

使用 while 语句将所有节点中保存的数据都输出。每输出一个节点的数据后，就移动 pTemp 指针指向下一个节点的地址。当为最后一个节点时，其所有的指针指向空，此时循环结束。

3.链表的插入和删除

1）链表的插入操作

链表的插入操作可以在链表的头节点位置进行，也可以在某个节点的位置进行，或者可以像创建结构一样在链表的后面添加节点。这 3 种插入操作的思路都是一样的。

下面主要介绍第一种插入操作，即在链表的头节点位置插入节点，如下图所示：

图 2 插入节点

插入节点的过程就如手拉手的小朋友连成一条线，这时又来了一个小朋友，他要站在第一位小朋友的前面，那么他只需要牵原来第一位小朋友的手就可以了。这样，这条连成的线还是连在一起的。

设计一个函数用来向链表中添加节点，代码如下：

struct Student* Insert(struct Student* pHead) {
    struct Student* pNew; /*指向新分配的空间*/
    printf("----Insert member at first----\n"); /*提示信息*/
    pNew = (struct Student*)malloc(sizeof(struct Student)); /*分配内存空间，并返回指向该内存空间的指针*/
    scanf("%s", &pNew->cName);
    scanf("%d", &pNew->iNumber);
    pNew->pNext = pHead; /*新节点指针指向原来的首节点*/
    pHead = pNew; /*头指针指向新节点*/
    iCount++; /*增加链表节点数量*/
    return pHead; /*返回头指针*/
}

上述代码插入节点的步骤如下：

• 为要插入的新节点分配内存，然后向新节点中输入数据，这样一个节点就创建完成了。
• 将新节点的指针指向原来的首节点，保存首节点的地址，然后将头指针指向新节点，这样就完成了节点的连接操作。

主函数 main() 的代码如下：

int main() {
    struct Student* pHead; /*定义头节点*/
    pHead = Create(); /*创建节点*/
    pHead = Insert(pHead); /*插入节点*/
    print(pHead); /*输出链表*/
    return 0; /*程序结束*/
}

运行程序，结果为：

please first enter Name ,then Number
liuwen 2
suyunjing 3
exit 0
----Insert member at first----
wangjiashen 1
----the List has 3 members:----
the N01 member is:
the name is: wangjiashen
the number is: 1
the N02 member is:
the name is: liuwen
the number is: 2
the N03 member is:
the name is: suyunjing
the number is: 3

2）链表的删除操作

之前介绍的操作是向链表中添加节点，当希望删除链表中的节点时，应该怎么办呢？还是通过前文中小朋友手拉手的例子进行介绍，队伍中的一个小朋友想离开，使这个队伍不会断开的方法是他两边的小朋友将手拉起来。

例如，在一个链表中删除其中的一个节点，如下图所示：

图 3 删除节点

通过图 3 可以发现，要删除一个节点，先要找到这个节点的位置。例如要删除 NO2 节点，首先要找到 NO2 节点，然后删除该节点，将 NO1 节点的指针指向 NO3 节点，最后释放 NO2 节点的内存空间，这样就完成了节点的删除。

根据这种思想编写删除链表节点的函数，代码如下：

void Delete(struct Student* pHead, int iIndex) /*pHead 表示头节点，iIndex 表示要删除的节点索引*/ {
    int i; /*控制循环的变量*/
    struct Student* pTemp; /*临时指针*/
    struct Student* pPre; /*表示要删除的节点前的节点*/
    pTemp = pHead; /*得到头节点*/
    pPre = pTemp;
    printf("----delete NO%d member----\n", iIndex); /*提示信息*/
    /*for 循环使得 pTemp 指向要删除的节点*/
    for (i = 1; i<iIndex; i++) {
        pPre = pTemp;
        pTemp = pTemp->pNext;
    }
    pPre->pNext = pTemp->pNext; /*连接要删除的节点两边的节点*/
    free(pTemp); /*释放要删除的节点的内存空间*/
    iCount--; /*减少链表中的元素个数*/
}

为 Delete() 函数传递两个参数，pHead 表示链表的头节点，iIndex 表示要删除的节点的索引。定义整型变量 i 用来控制循环的次数，然后定义两个指针，分别用来表示要删除的节点和这个节点之前的节点。

输出一行提示信息表示要进行删除操作，之后利用 for 语句进行循环操作，找到要删除的节点，使用 pTemp 保存要删除节点的地址，pPre 保存前一个节点的地址。找到要删除的节点后，连接要删除的节点两边的节点，并使用 free() 函数将 pTemp 指向的内存空间释放。

接下来在 main() 函数中添加代码执行删除操作，将链表中的第二个节点删除。代码如下：

int main() {
    struct Student* pHead; /*定义头节点*/
    pHead = Create(); /*创建节点*/
    pHead = Insert(pHead); /*插入节点*/
    Delete(pHead, 2); /*删除第二个节点的操作*/
    print(pHead); /*输出链表*/
    return 0; /*程序结束*/
}

运行程序，通过运行结果可以看到第二个节点中的数据被删除，结果为：

please first enter Name ,then Number
WangJun 2
LiXin 3
exit 0
----Insert member at first----
XuMing 1
----delete N02 member----
----the List has 2 members:----
the N01 member is:
the name is: XuMing
the number is: 1
the N02 member is:
the name is: LiXin
the number is: 3

4.相关操作

1）遍历列表

// 遍历链表并打印
void printList(Node *head) {
    Node *current = head;
    printf("链表内容：");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

2）查找结点

// 查找节点
Node* searchNode(Node *head, int data) {
    Node *current = head;
    while (current != NULL) {
        if (current->data == data) {
            return current;
        }
        current = current->next;
    }
    return NULL; // 未找到
}

3）获取链表长度

// 获取链表长度
int getLength(Node *head) {
    int length = 0;
    Node *current = head;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

4）释放链表内存

// 释放整个链表
void freeList(Node *head) {
    Node *current = head;
    while (current != NULL) {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
    printf("链表已释放\n");
}

完整操作示例

#include <stdio.h>
#include <stdlib.h>
// 节点定义
typedef struct Node {
    int data;
    struct Node *next;
} Node;
// 函数声明
Node* createNode(int data);
Node* insertAtHead(Node *head, int data);
Node* insertAtTail(Node *head, int data);
Node* insertAtPosition(Node *head, int data, int position);
Node* deleteNode(Node *head, int data);
Node* searchNode(Node *head, int data);
void printList(Node *head);
int getLength(Node *head);
void freeList(Node *head);

int main() {
    Node *head = NULL;
    printf("=== 链表操作演示 ===\n");
    // 尾插法创建链表
    head = insertAtTail(head, 10);
    head = insertAtTail(head, 20);
    head = insertAtTail(head, 30);
    printf("初始链表：");
    printList(head);
    // 头插法
    head = insertAtHead(head, 5);
    printf("头插入 5 后：");
    printList(head);
    // 在指定位置插入
    head = insertAtPosition(head, 15, 2);
    printf("在位置 2 插入 15 后：");
    printList(head);
    // 删除节点
    head = deleteNode(head, 20);
    printf("删除 20 后：");
    printList(head);
    // 查找节点
    Node *found = searchNode(head, 15);
    if (found != NULL) {
        printf("找到节点：%d\n", found->data);
    } else {
        printf("未找到节点\n");
    }
    // 获取长度
    printf("链表长度：%d\n", getLength(head));
    // 释放内存
    freeList(head);
    return 0;
}
// 函数实现（前面已经给出，此处省略重复代码）

四、重要应用

1.栈的实现

// 使用链表实现栈
typedef struct Stack {
    Node *top;
} Stack;
Stack* createStack() {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->top = NULL;
    return stack;
}
void push(Stack *stack, int data) {
    stack->top = insertAtHead(stack->top, data);
}
int pop(Stack *stack) {
    if (stack->top == NULL) {
        printf("栈为空！\n");
        return -1;
    }
    int data = stack->top->data;
    stack->top = deleteNode(stack->top, data);
    return data;
}
int peek(Stack *stack) {
    if (stack->top == NULL) {
        printf("栈为空！\n");
        return -1;
    }
    return stack->top->data;
}

2.队列的实现

// 使用链表实现队列
typedef struct Queue {
    Node *front;
    Node *rear;
} Queue;
Queue* createQueue() {
    Queue *queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    return queue;
}
void enqueue(Queue *queue, int data) {
    Node *newNode = createNode(data);
    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
        return;
    }
    queue->rear->next = newNode;
    queue->rear = newNode;
}
int dequeue(Queue *queue) {
    if (queue->front == NULL) {
        printf("队列为空！\n");
        return -1;
    }
    int data = queue->front->data;
    Node *temp = queue->front;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return data;
}

3.多项式运算

// 多项式节点
typedef struct PolyNode {
    int coeff; // 系数
    int exp; // 指数
    struct PolyNode *next;
} PolyNode;
// 多项式加法
PolyNode* addPolynomials(PolyNode *poly1, PolyNode *poly2) {
    PolyNode *result = NULL;
    PolyNode *tail = NULL;
    while (poly1 != NULL && poly2 != NULL) {
        PolyNode *newNode = (PolyNode*)malloc(sizeof(PolyNode));
        if (poly1->exp == poly2->exp) {
            newNode->coeff = poly1->coeff + poly2->coeff;
            newNode->exp = poly1->exp;
            poly1 = poly1->next;
            poly2 = poly2->next;
        } else if (poly1->exp > poly2->exp) {
            newNode->coeff = poly1->coeff;
            newNode->exp = poly1->exp;
            poly1 = poly1->next;
        } else {
            newNode->coeff = poly2->coeff;
            newNode->exp = poly2->exp;
            poly2 = poly2->next;
        }
        newNode->next = NULL;
        if (result == NULL) {
            result = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    // 处理剩余节点
    while (poly1 != NULL) {
        PolyNode *newNode = (PolyNode*)malloc(sizeof(PolyNode));
        newNode->coeff = poly1->coeff;
        newNode->exp = poly1->exp;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
        poly1 = poly1->next;
    }
    while (poly2 != NULL) {
        PolyNode *newNode = (PolyNode*)malloc(sizeof(PolyNode));
        newNode->coeff = poly2->coeff;
        newNode->exp = poly2->exp;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
        poly2 = poly2->next;
    }
    return result;
}

五、常见易错点

1.内存错误管理

错误示例

// 错误：忘记分配内存
Node *newNode;
newNode->data = 10; // 未分配内存就使用
// 错误：内存泄漏
void addNode(Node *head, int data) {
    Node *newNode = createNode(data);
    // 忘记将新节点连接到链表
}

正确做法

// 正确：分配内存并检查
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
    // 处理内存分配失败
}
// 正确：确保新节点被正确连接
newNode->next = head->next;
head->next = newNode;

2.指针操作错误

错误示例

// 错误：丢失头指针
void wrongDelete(Node *head, int data) {
    // 如果删除的是头节点，头指针会丢失
    if (head->data == data) {
        Node *temp = head;
        head = head->next; // 这个修改不会影响外部的 head
        free(temp);
    }
}

正确做法

// 正确：返回新的头指针
Node* correctDelete(Node *head, int data) {
    if (head->data == data) {
        Node *temp = head;
        head = head->next;
        free(temp);
        return head; // 返回新的头指针
    }
    // ... 其他删除逻辑
    return head;
}

总结

1. 始终检查 malloc 返回值
2. 及时释放内存
3. 处理所有边界条件
4. 使用 typedef 简化代码
5. 保持函数功能单一
6. 编写测试用例验证
7. 使用调试工具检查内存泄漏

六、预防、检测与调试

1.边界条件处理

// 处理各种边界条件
Node* safeInsert(Node *head, int data, int position) {
    // 1. 检查位置是否合法
    if (position < 0) {
        printf("位置不能为负数\n");
        return head;
    }
    // 2. 空链表且位置不为 0
    if (head == NULL && position != 0) {
        printf("位置超出链表长度\n");
        return head;
    }
    // 3. 位置为 0（头插）
    if (position == 0) {
        return insertAtHead(head, data);
    }
    // 4. 正常插入逻辑
    // ...
}

2.循环列表检测

// 检测链表是否有环
int hasCycle(Node *head) {
    if (head == NULL || head->next == NULL) {
        return 0;
    }
    Node *slow = head;
    Node *fast = head->next;
    while (slow != fast) {
        if (fast == NULL || fast->next == NULL) {
            return 0;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return 1;
}

3.打印链表信息

// 详细的链表打印函数
void debugPrintList(Node *head, const char *listName) {
    printf("=== 调试信息：%s ===\n", listName);
    printf("头节点地址：%p\n", (void*)head);
    Node *current = head;
    int count = 0;
    while (current != NULL) {
        printf("节点 [%d]: 地址=%p, data=%d, next=%p\n", count, (void*)current, current->data, (void*)current->next);
        current = current->next;
        count++;
        // 防止无限循环
        if (count > 100) {
            printf("警告：可能存在循环链表！\n");
            break;
        }
    }
    printf("链表长度：%d\n", count);
    printf("========================\n");
}