企业官网建设流程全解析

在开源项目中（如 Linux Kernel, Redis, GNOME GLib 等）

1. 极少使用“按索引插入” (Insert at Index)

在高性能 C 编程中，链表主要用于O ( 1 ) O(1)O(1)的头插、尾插或特定节点前后的插入。
如果你频繁需要“在第i ii个位置插入”，说明你选错了数据结构——这种场景应该使用数组 (Array)或动态数组 (Vector)。链表的“按索引访问”是O ( N ) O(N)O(N)的，效率极低。

因此，很多开源库甚至不提供insert_at_index(i)这种 API。

2. Linux Kernel (list.h)

Linux 内核使用的是双向循环链表，它的设计极其精简，不存储长度。

• 越界判断：它没有“越界”的概念，因为它的 API 是list_add(new, head)（插到头）或list_add(new, prev_node)（插到某节点后）。
• 设计哲学：这里的假设是调用者已经持有了一个有效的节点指针。

3. Redis (adlist.c)

Redis 实现了一个通用的双向链表，它的结构体明确包含了长度：

// Redis 的 list 定义typedefstructlist{listNode*head;listNode*tail;unsignedlonglen;// <--- 这里保存了长度// ... 函数指针等 ...}list;

• 做法：Redis 确实维护了长度。
• 但注意：即使有了len，Redis 的核心 API 依然主要是listAddNodeHead和listAddNodeTail。如果它要实现Index操作（如listIndex获取节点），它会利用len来决定是从头遍历更快还是从尾遍历更快（优化），但插入操作依然很少基于索引。

4. 总结建议

1. 如果是刷题/简单练习：不要维护length。在遍历寻找插入点的while循环中判断p是否为NULL，以此作为越界判断。
2. 如果是工程项目：建议定义一个struct List { Node* head; int len; }。
   • 这样你可以在开头判断i > len。
   • 这能让调用者快速获取链表长度（O(1)），非常实用。

只有当你将链表长度缓存在结构体中时，才能在函数开头判断越界。否则，必须通过遍历来检测。