C / C++ / 系统课时
创建并遍历一个单链表
创建并遍历一个单链表
单链表的关键不是把节点连续存放,而是让每个节点通过指针找到下一个节点。本节从动态创建三个节点开始,完成节点连接、从头到尾遍历以及内存释放,建立对 head、临时遍历指针和 next 之间关系的直观认识。
学习目标
- 能使用
malloc动态创建节点并正确连接成单链表 - 能使用临时指针从头节点遍历到
NULL - 能在遍历结束后安全释放链表占用的动态内存
节点如何连接成链表
一个单链表节点通常同时保存数据和指向下一个节点的指针。最后一个节点没有后继,因此它的 next 必须为 NULL。链表本身只需要保存第一个节点的地址,也就是头指针 head。
typedef struct Node {
int value;
struct Node *next;
} Node;这里的 struct Node *next 不保存下一个节点本身,只保存下一个节点所在的地址。因此,各节点可以由多次 malloc 分散分配,只要指针关系正确,仍然能组成一条链。

动态创建并连接节点
下面的完整程序使用 tail 记录当前尾节点。创建新节点后,如果链表为空,就让 head 和 tail 都指向它;否则通过 tail->next 接到链表末尾,再更新 tail。这种方式可以避免每添加一个节点都重新从头寻找尾部。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
int main(void) {
Node *head = NULL;
Node *tail = NULL;
const int values[] = {10, 20, 30};
const size_t count = sizeof values / sizeof values[0];
for (size_t i = 0; i < count; ++i) {
Node *node = malloc(sizeof *node);
if (node == NULL) {
while (head != NULL) {
Node *next = head->next;
free(head);
head = next;
}
return 1;
}
node->value = values[i];
node->next = NULL;
if (head == NULL) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}
/* current 负责移动,避免破坏保存首节点地址的 head。 */
for (Node *current = head; current != NULL; current = current->next) {
printf("%d -> ", current->value);
}
puts("NULL");
/* 释放当前节点前,先保存后继地址。 */
while (head != NULL) {
Node *next = head->next;
free(head);
head = next;
}
return 0;
}预期输出
10 -> 20 -> 30 -> NULL遍历为什么要使用临时指针
遍历的核心条件是“当前指针不为 NULL”。访问完当前节点后执行 current = current->next,就能沿着链表逐个前进,直到越过最后一个节点。
如果直接使用 head = head->next 完成普通遍历,虽然也能看到所有节点,但遍历结束后 head 会变成 NULL,程序将失去原来的链表入口。除非操作本身就是删除并释放头节点,否则应让 head 保持不动,另外使用 current 一类临时指针。
创建和遍历时最容易出错的地方
新节点加入链表前应明确初始化 next。作为尾节点时,如果忘记设置为 NULL,遍历可能继续访问无效地址。动态分配还必须检查 malloc 是否返回 NULL,已经成功创建的节点也应在异常退出前释放。
释放链表时不能先 free(head) 再读取 head->next,因为释放后的内存已经不能继续访问。正确顺序是先保存后继地址,再释放当前节点,最后移动 head。只要始终维护“头指针保存入口、临时指针负责移动、尾节点的 next 为 NULL”这三个约束,单链表的创建与遍历就具有清晰且可验证的指针关系。