许多编程问题，包括创建简单的链表和队列，都可以使用链表(指动态分配结构的序列链)和数组来处理。 每种形式都有其优缺点，必须根据具体问题的要求决定选择哪种形式。 表17.1总结了链表和数组的性质。
C语言的链表和数组
Comparing Arrays to Linked Lists
然后详细分析插入和删除元素的过程。 要在数组中插入元素，必须移动其他元素以释放空间并插入新元素，如图Inserting an element into an array所示。 新插入的元素越靠近数组的开头，移动的元素越多。 但是，要将节点插入链表中，只需为这两个指针赋值，如insertinganelementintoalinkedlist .所示。 同样，要从数组中删除一个元素，必须移动许多相关的元素。 但是，要从链表中删除节点，只需重新设置指针，释放删除节点消耗的内存即可。
C语言的链表和数组
Inserting an element into an array。
C语言的链表和数组
内嵌元素链接列表。
然后，考虑如何访问元素。 对于数组，可以使用数组下标直接访问数组中的任何元素。 这称为随机访问(random access )。 对于链表，必须从链表的起始节点开始，一次移动到要访问的节点。 这称为顺序访问(sequential-access )。 当然，也可以依次访问数组。 只需按顺序递增数组的下标即可。 在某些情况下，顺序访问就足够了。 例如，您可以查看链表中的每个项目，然后按顺序访问它们。 在其他情况下，随机接入更合适。 假设您要搜索链表中的特定项目。 一种算法是从列表的开头开始按顺序搜索，这称为顺序搜索(sequential-search )。 如果项目没有按特定顺序排列，则只能按顺序搜索。 如果要搜索的项目不在链表中，则必须搜索所有项目，然后才能知道该项目不在链表中。 在这种情况下，可以使用并发编程同时搜索列表的不同部分。
您可以先对列表进行排序，然后按改进顺序进行搜索。 这样就不需要搜索搜索项后面的项。 例如，假设您正在按字母顺序的列表中查找gxdmg。 从一开始就找了所有项目，直到Sylvia都找不到gxdmg。 此时可以结束搜索。 因为如果gxdmg在列表中，则必须排在Sylvia之前。 平均来说，用这种方法找没有列出的项目的时间减半。
在已排序的列表中，binary-search要比按顺序搜索好得多。 以下分析二分搜索的原理。 首先，假设要搜索的项目称为目标项目，并且列表中的项目按字母顺序排序。 然后将列表中的中间项与目标项进行比较。 如果两者相等，则搜索结束； 假设目标项目在列表中。 如果中间项目位于目标项目之前，则目标项目一定位于后半部分的项目中。 如果中间项在目标项之后，则目标项必须在前半项中。 在所有情况下，两个比较的结果都确认了下一个要搜索的范围只有列表的一半。 然后，继续该方法，将需要寻找的另一半中间项与目标项进行比较。 同样，此方法会确保下一个要搜索的范围是当前搜索范围的一半。 这样，直到发现目标项目，或者最终发现列表中没有目标项目为止(参照图17.11 )。 这个方法很有效率。 如果有127个项目，依次检索平均进行64次比较来找到目标项目，或者发现其中不存在。 但是，二分搜索最多只进行7次比较。 在第一次比较中，比较剩下的63个项目，在第二次比较中，比较剩下的31个项目，同样，比较第六次的最后一个项目，在第七次比较中，判断剩下的项目是否为目标项目。 一般来说，n次比较可以处理具有2n-1个元素的序列。 因此，项目数越多，越能显示二分搜索的优越性。
C语言的链表和数组
A binary search for gxdmg .
使用数组实现二分搜索很简单。 因为可以使用数组下标来确定数组中任意部分的中点。 将数组的第一个元素和最后一个元素的索引相加，得到的和除以2即可。 例如，对于包含100个元素的数组，如果第一个元素的下标为0，最后一个元素的下标为99，则用于第一个比较的中间项的下标为[099]/2，为49 (整数除法)。 如果比较结果是下标为49的要素位于目标项目之后，则目标项目的下标必须在0~48的范围内。 因此，第二次比较的中间项的下标为[048]/2，为24。 中间项和目标项的比较结果，如果中间项在目标项之前，则第三次比较的中间项下标为(25 48 )/2，为36。 它体现了随机访问的特性，可以从一个位置跳到另一个位置，不需要一次访问两个位置之间的项目。 但是，链表只支持顺序访问，不提供跳转到中间节点的方法。 因此，不能在链表中使用二叉树搜索。 如上所述，选择什么数据类型取决于特定的问题。 如果经常通过插入和删除项来调整大小，并且不需要频繁搜索，则选择链表可能会比较好。 如果您只是偶尔插入或删除项目，并希望经常进行搜索，则使用数组非常有用。 如果需要同时支持频繁插入和删除项以及频繁搜索的数据格式，并且数组和链表都不合适，该怎么办？ 在这种情况下，必须选择双叉搜索树。