C / C++ / 系统课时

创建并遍历一个单链表

创建并遍历一个单链表

单链表的关键不是把节点连续存放,而是让每个节点通过指针找到下一个节点。本节从动态创建三个节点开始,完成节点连接、从头到尾遍历以及内存释放,建立对 head、临时遍历指针和 next 之间关系的直观认识。

学习目标

  • 能使用 malloc 动态创建节点并正确连接成单链表
  • 能使用临时指针从头节点遍历到 NULL
  • 能在遍历结束后安全释放链表占用的动态内存

节点如何连接成链表

一个单链表节点通常同时保存数据和指向下一个节点的指针。最后一个节点没有后继,因此它的 next 必须为 NULL。链表本身只需要保存第一个节点的地址,也就是头指针 head。

c
typedef struct Node {
    int value;
    struct Node *next;
} Node;

这里的 struct Node *next 不保存下一个节点本身,只保存下一个节点所在的地址。因此,各节点可以由多次 malloc 分散分配,只要指针关系正确,仍然能组成一条链。

头指针与三个单链表节点的连接关系

动态创建并连接节点

下面的完整程序使用 tail 记录当前尾节点。创建新节点后,如果链表为空,就让 head 和 tail 都指向它;否则通过 tail->next 接到链表末尾,再更新 tail。这种方式可以避免每添加一个节点都重新从头寻找尾部。

c
#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;
}

预期输出

text
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”这三个约束,单链表的创建与遍历就具有清晰且可验证的指针关系。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

创建并遍历一个单链表

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通