说起顺序表这东西，刚接触那会儿，觉得它简直是线性表里最憨厚老实的一个了。数组嘛，内存里排排坐，多简单。查找快、访问快，像个直肠子朋友。但你真要玩点“动态”的，比如在中间删除元素，嘿，它的“老实”劲儿就暴露了，得算法来救场，而且这救场方式，透着一股子原始的、不得不为之的挪动劲儿。
想想看，顺序表，它的核心卖点不就是数据挨得紧紧的吗？就像图书馆里一整排挨在一起的书。你想把中间某本拿掉（删除），那空出来的位置咋办？你不能让它就这么杵在那儿啊，中间多个窟窿可就乱套了。所以，顺序表删除元素的算法，它干的最主要的事儿，就是把那个被删掉元素后面的所有元素，一个接一个地，往前挪一个位置。对，就是这么朴实无华，甚至有点笨拙的操作。
具体怎么做呢？假设我们的顺序表里有 n 个元素，你想删掉位于第 i 个位置（索引 i-1）的那个元素。你找到了它，好了，现在这个位置空了。接下来的步骤是，从第 i+1 个元素（索引 i）开始，把它的值复制到第 i 个位置（索引 i-1）。然后呢？把第 i+2 个元素（索引 i+1）的值复制到第 i+1 个位置（索引 i）。就这么挨个儿来，一直循环到表尾那个元素（索引 n-1），把它复制到倒数第二个位置（索引 n-2）。瞧见没？后面的元素都往前赶了一步。
这个过程，用代码的思路来想，无非就是个循环：从 i 开始（或者说从删除位置的后一个位置开始），一直到表的末尾。在循环里，就是执行list[j-1] = list[j]这样的赋值操作，或者更直观地说，list[当前位置-1] = list[当前位置]。每一次赋值，都像是在说：“你，往左边空位站！”
那删完之后呢？整个表的有效长度就减少了 1。原来最后一个元素所在的那个位置，现在其实存的是倒数第二个元素的原值，已经是个“无效”或者说冗余的数据了。虽然物理内存可能还在那里，但从逻辑上看，表的末尾往前缩了一格。
这就是最常见的按位置删除元素的算法。如果是按值删除呢？那就多一步：你得先遍历整个顺序表，找到那个值在哪儿。如果找到了，比如在位置 i，那就套用上面的按位置删除算法；如果表里有好几个相同的值，是只删第一个出现的，还是全删？这又引申出不同的算法策略。全删的话，效率问题就更突出了，可能需要更巧妙的一次遍历来完成，而不是每删一个就挪动一次。
所以你看，尽管顺序表删除元素的算法听起来直白，背后其实是数据存储方式决定的必然。它不像链表，删一个节点只需要改改指针，效率很高（O(1)）。在顺序表里，因为连续存储的要求，你动了中间一个，后面一串都得跟着“搬家”。这个“搬家”的代价，随着表长度的增加，线性增长。这就是为什么说，它的时间复杂度通常是 O(n)——在平均和最坏情况下，都可能需要移动大约一半甚至全部的元素。只有当你要删除的是表尾元素时，才最快，基本就是 O(1)，因为后面没东西需要移动了。
回想起刚学这块儿，写代码调 bug，就卡在那个循环的起始和结束条件上，以及索引和位置之间的转换（0-based vs 1-based）。那感觉就像在指挥一队木头人往前稍息立正，得一点儿都错不得。但正是这种“体力活”式的操作，让你真切地感受到顺序表数据结构的物理特性，以及算法如何弥补甚至说是应对这种物理特性带来的操作上的局限。理解了它删除时的算法，也就更懂了顺序表的优点和缺点，知道什么时候该用它，什么时候得换个思路，比如用链表，或者更高阶的数据结构。这是一个看似简单，实则意味深长的算法，是深入理解数据结构精髓的重要一环。
发表回复