聊起 C语言线性表添加元素，我总感觉很多人把它想得太玄乎了。什么数据结构、算法复杂度，一堆名词砸过来，新手直接懵圈。说白了，不就是排队嘛！一帮数据，挨个站好。但关键是，这队怎么排，新来一个哥们儿，让他插哪，怎么插，这里面的门道，那可就深了。今天，咱们不扯那些虚的，就唠唠嗑，把这事儿给彻底盘明白。
线性表这玩意儿，在C语言里，主要就两大流派：一个是顺序表，另一个是链表。你可以把它们想象成两种完全不同性格的人。
顺序表，就是那个有强迫症的家伙。它的本质，说穿了，就是个数组。内存里，它要求所有兄弟必须肩并肩，整整齐齐地挨着，地址一个连着一个，谁也别想乱跑。这种结构，查东西那叫一个快！你想找第几个元素，直接 array[i]，一步到位，跟点名一样。
但问题来了，你要往这支纪律严明的队伍里 添加一个新元素，那可就得折腾了。
你想想这个画面：一排电影院的座位，坐得满满当登。现在，你要在中间插个人进去。怎么办？从那个位置开始，后面所有人都得站起来，很不情愿地往后挪一个座位，给你腾出个空来。这得多大动静？
在代码里，这个“挪窝”的过程，就是个循环。
c
// 假设要在第 i 个位置插入元素 e
// 顺序表长度为 length
for (j = length - 1; j >= i; j--) {
L.data[j + 1] = L.data[j]; // 元素向后移动
}
L.data[i] = e; // 新元素就位
L.length++; // 表长加一
你看，从最后一个元素开始，一直到你要插入的位置，挨个往后搬家。如果你的表有一万个元素，你要插在最前面，那就意味着后面九千九百九十九个元素都得动弹一下。这效率，简直是灾难。这就是所谓的 O(n) 复杂度，听着高大上，其实就是说，这活儿的累赘程度跟队伍长度成正比。
更要命的是，如果一开始申请的座位（数组空间）就不够了呢？电影院满座了，新来的观众没地方坐。顺序表就面临这个问题：空间溢出。
这时候，就得请出 C 语言里那个让人又爱又恨的函数了：realloc。
realloc 这哥们儿，像个房屋中介。你跟它说：“我这房子（内存空间）不够住了，帮我换个大的。” 它会尝试在原地给你扩建，如果原地扩不了，它就会在别处找一块更大的地，把你所有的家当（数据）原封不动地搬过去，然后把老房子的地址给你作废，给你一个新家的门牌号（新的内存地址）。
这个过程充满不确定性。首先，它可能失败，找不到那么大的地，返回一个 NULL。你要是不检查这个返回值，直接用，程序就崩了，这叫空指针解引用，新手最常踩的坑。其次，就算成功了，它也可能把你的数据乾坤大挪移。你之前记的老地址，瞬间就成了“拆迁区”，不能再用了。所以，用 realloc 就得打起十二分精神，它既是救星，也是魔鬼。
说完了“强迫症”顺序表，我们再来看看“自由散漫”的链表。
链表 这家伙，就随性多了。它的元素，在内存里是东一个西一个，散落在天涯海角。那怎么把它捏合成一个整体呢？靠的是指针。每个元素（我们叫它“节点”）除了装着自己的数据外，还揣着一张小纸条，上面写着下一个兄弟的地址。大家就靠着这张纸条，一个找一个，手拉手，形成了一条逻辑上的链。
往链表里 添加元素，那叫一个潇洒。
比如，你想在队头加一个新人。根本不需要任何人动地方。你只需要：
- 用
malloc申请一个新节点，让新来的哥们儿住进去。 - 让这个新节点的“小纸条”指向原来那个排在第一的“老大”。
- 最后，你更新一下队头标记，告诉所有人：“现在，这个新来的才是我们真正的老大！”
就这么两三下指针操作，完事儿了。原来的队伍，动都没动一下。这就是 O(1) 的优雅。代码写出来，也特别清爽。
c
// 在带头节点的链表头部插入
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = e;
newNode->next = head->next; // 新人指向原来的第一个节点
head->next = newNode; // 头节点指向这个新人
那要在中间插入呢？也简单。你只需要找到要插入位置的 前一个 节点，我们管它叫 p。然后，让新来的节点去牵 p 原本牵着的那个节点的手，再让 p 回过头来牵新节点的手。一个完美的“三角关系”就形成了，新人顺利入队。整个过程，还是只需要动几下指针，跟链表多长没半毛钱关系。
当然，链表也不是完美的。它的“自由”是有代价的。因为大家住得分散，你想找第 i 个元素，就没法像顺序表那样一步到位了。你只能从第一个开始，拿着“小纸条”，一个一个地往下数，直到数到第 i 个。这叫遍历，效率自然就低了。
所以，到底用哪个？
这根本不是个技术问题，这是个场景问题。如果你的数据，增删操作特别频繁，尤其是插入删除，那想都不用想，链表 绝对是你的菜。它那种“牵一发动全身”的反面——“只动局部，不扰全局”的特性，简直是为这种场景而生的。
但如果你的场景是，数据一旦初始化，就很少变动，主要就是查，各种姿势地查。那顺序表（数组）凭借其O(1)的随机访问速度，绝对能把你伺候得舒舒服服。
说到底，C语言线性表添加元素，你不能只盯着代码本身。你要去想象内存里到底发生了什么。是像顺序表那样，一大片数据在笨拙地平移、搬家？还是像链表那样，几根指针在灵活地穿针引线？
当你脑子里有了这幅动态的画面，理解了它们各自的脾气和秉性，你才能真正驾驭它们，在合适的场景，做出最漂亮的选择。这，比背一万行代码都管用。
发表回复