链表对元素的追加和删除,接下来介绍的链表和二叉查找树,都是不用考虑索引的顺序就可以对数组元素进行读写的方式。通过使用链表,可以更加高效地对数组数据(元素)进行追加和删除处理。而通过使用二叉查找树,则可以更加高效地对数组数据进行检索。
在数组的各个元素中,除了数据的值之外,通过为其附带上下一个元素的索引,即可实现链表。数据的值和下一个元素的索引组合在一起,就构成了数组的一个元素。这样,数组元素相连就构成了念珠似的链表。由于链表末尾的元素没有后续的数据,因此就需要用别的值(在这里是-1)来填充(图4-10)。
图4-10 链表的示例(初始状态)
在需要追加或删除数据的情况下,使用链表是很高效的。首先,让我们来看一下删除的情况。在图4-10表示的链表中,假设要删除从起始位置开始的第3个元素。此时,我们只需要把第2个元素的“下一个元素:2”变成“下一个元素:3”即可。由于数组的元素通常是按照索引顺序来引用的,因此当我们需要引用构成链表的数组的某一个元素时,通过该元素的索引信息就可以找到下一个元素。当第2个元素的下一个元素变成第4个元素后,那么第3个元素就被删除了。虽然第3个元素在物理内存上还残留着,但在逻辑上则确实被删除了(图4-11)。
图4-11 删除链表的第3个元素的方法
接下来就让我们来看一下如何往链表中追加数据。假设要在图4-10的链表的第5位前追加一个新数据。此时,我们只需要在刚才消除的第3个元素的位置中保存新的数据,并将第4个元素的“下一个元素:5”变更成“下一个元素:2”,以使新追加的元素的索引信息变成“下一个元素: 5”即可。虽然新追加的元素在物理上是第3个,但从逻辑上看来则是第5个(图4-12)。
图4-12 链表中追加元素的方法
如果不使用链表数组,那么中途删除或追加元素时,其后的元素就必须要全部移动。示例中数组的元素只有6个,处理起来不会花费较多时间。而在实际的程序中,有时需要对包含数千至数万个元素的数组进行频繁的数据追加或删除操作。如果每次都需要移动数千至数万个元素,那么哪怕是高速计算机也会花费很长时间(图4-13、图4-14)。反之,使用链表来追加或删除数据则毫不费事。
图4-13 单纯使用数组的情况下的元素删除
图4-14 单纯使用数组的情况下的元素追加
酷客网相关文章:
评论前必须登录!
注册