C语言怎么确定list的size

在C语言里，我们常说的list通常指自定义实现的链表结构，因为C标准库没有提供像其他高级语言那样的通用list容器，所以确定list的size需要开发者自己实现对应的逻辑。常见的实现方式有两种，分别是遍历计数法和维护长度变量法。

遍历计数法

遍历计数法是最基础的实现思路，不需要额外修改链表的结构定义，只需要从头节点开始依次遍历每个节点，每访问一个节点就计数加一，直到遍历到尾节点为止。这种方式的时间复杂度是O(n)，适合对性能要求不高或者链表长度较小的场景。

首先我们定义链表节点的结构：

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

// 定义链表节点结构
typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

接下来实现遍历统计size的函数：

// 遍历计数法获取链表size
int get_list_size_by_traverse(ListNode* head) {
    int count = 0;
    ListNode* current = head;
    // 遍历所有节点，每有一个节点计数加一
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

我们可以测试这个函数的效果：

// 创建链表节点并测试
int main() {
    // 创建三个节点：1->2->3->NULL
    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    
    node1->data = 1;
    node1->next = node2;
    node2->data = 2;
    node2->next = node3;
    node3->data = 3;
    node3->next = NULL;
    
    int size = get_list_size_by_traverse(node1);
    printf("链表size为：%dn", size); // 输出3
    
    // 释放内存
    free(node1);
    free(node2);
    free(node3);
    return 0;
}

维护长度变量法

如果我们需要频繁获取list的size，遍历计数法的O(n)时间复杂度会带来性能损耗，这时候可以在链表的结构定义中增加一个记录长度的变量，每次插入或删除节点时同步更新这个变量，获取size的时候直接返回该变量即可，时间复杂度为O(1)。

首先定义带长度记录的链表结构：

// 定义带长度记录的链表结构
typedef struct List {
    ListNode* head;
    int size; // 记录链表长度
} List;

实现链表的初始化、插入节点和获取size的函数：

// 初始化链表
List* list_init() {
    List* list = (List*)malloc(sizeof(List));
    list->head = NULL;
    list->size = 0;
    return list;
}

// 链表头部插入节点
void list_insert_head(List* list, int data) {
    ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->data = data;
    new_node->next = list->head;
    list->head = new_node;
    list->size++; // 插入节点后长度加一
}

// 直接返回链表长度
int get_list_size(List* list) {
    return list->size;
}

测试带长度记录的链表获取size的效果：

int main() {
    List* list = list_init();
    // 插入三个节点
    list_insert_head(list, 3);
    list_insert_head(list, 2);
    list_insert_head(list, 1);
    
    int size = get_list_size(list);
    printf("链表size为：%dn", size); // 输出3
    
    // 释放内存（实际开发中需要遍历释放所有节点，这里简化示例）
    free(list->head);
    free(list);
    return 0;
}

两种方式的对比

我们可以通过表格对比两种方式的差异：

在实际开发中，开发者可以根据具体的业务场景选择合适的实现方式，确定list的size。如果选择维护长度变量法，需要注意在删除节点的时候也要同步将size减一，避免出现长度统计错误的问题。

C语言list_size链表数据结构遍历统计修改时间：2026-06-25 13:09:29