C / C++ / 系统课时

链表节点如何连接起来

链表节点如何连接起来

链表不要求所有元素位于连续内存中,每个节点可以单独分配,只要节点内部保存下一个节点的地址,就能把分散的内存块连接成有顺序的数据结构。本节从节点定义、指针连接到遍历与释放完整走一遍。

学习目标

  • 定义同时包含数据和 next 指针的链表节点
  • 理解多个独立节点怎样通过地址形成单向链
  • 能够连接、遍历并正确释放一条简单单链表

节点由两部分组成

一个单链表节点通常包含数据域和指针域。数据域保存当前元素,next 保存下一个节点的地址。因为结构体内部需要保存同类型对象的指针,所以成员类型写成 struct Node *,而不是直接嵌套一个完整的 struct Node。

c
struct Node {
    int data;
    struct Node *next;
};

这是结构定义,不是独立可执行程序。它声明了节点的内存布局:data 表示当前节点的数据,next 为 NULL 时表示当前节点后面没有其他节点。

next 如何形成一条链

假设程序分别申请了三个节点,它们在内存中的实际地址可以完全不连续。链表并不依赖地址大小或物理相邻关系,而是依赖 next 中明确保存的地址。

第一个节点的 next 指向第二个节点,第二个节点的 next 指向第三个节点,第三个节点的 next 设置为 NULL。只要保留第一个节点的地址,就可以沿着 next 逐个找到后续所有节点。

三个独立链表节点通过 next 指针连接成单链表

这也是链表与数组最重要的区别之一:数组通过下标和连续地址确定下一个元素,而链表通过当前节点中的指针确定下一个节点。

完整连接并遍历

下面的程序使用 malloc 分别创建三个节点,再通过 next 把它们连接起来。遍历时只维护一个当前指针,每访问一个节点后执行 current = current->next。

c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *create_node(int value) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        return NULL;
    }

    node->data = value;
    node->next = NULL;
    return node;
}

void print_list(const Node *head) {
    const Node *current = head;

    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }

    printf("NULL\n");
}

int main(void) {
    Node *first = create_node(10);
    Node *second = create_node(20);
    Node *third = create_node(30);

    if (first == NULL || second == NULL || third == NULL) {
        free(first);
        free(second);
        free(third);
        return 1;
    }

    /* 真正形成链表的是这些 next 指针,而不是节点的物理位置。 */
    first->next = second;
    second->next = third;

    print_list(first);

    free(third);
    free(second);
    free(first);
    return 0;
}

预期输出

text
10 -> 20 -> 30 -> NULL

遍历从 first 开始。第一次读取 10,然后跟随 first->next 到达保存 20 的节点;继续跟随指针到达 30;最后读到 next == NULL,循环结束。整个过程不需要知道三个节点实际位于哪些内存地址。

断链与释放

修改 next 就是在修改链表的逻辑连接关系。例如如果直接令 first->next = third,那么从 first 出发遍历时将跳过 second。如果此时又没有其他指针保存 second 的地址,之后就无法再通过链表访问它。

动态申请的节点还必须在不再使用时调用 free。释放整条链表时,实际项目通常会先保存当前节点的 next,再释放当前节点并移动到下一个节点,避免释放后继续读取已经失效的内存。

理解单链表时最关键的是把“物理内存位置”和“逻辑前后关系”分开:节点可以散落在不同位置,真正把它们组织成一条链的是每个节点内部保存的 next 地址。

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

目录与阅读设置

阅读设置

17

记录一个想法

链表节点如何连接起来

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

登录哪都通