链表和而叉查找树，但是不用考虑索引的顺序就可以对数组元素进行读写的方式。
链表，可以更加高效的对数组元素进行追加和删除处理。
二叉查找树，可以更加高效的对数组数据进行索引。
在数组的各个元素中，除了数据的值之外，通过为其附带上下一个元素的索引，即可实现链表。（ 数据的值+下一个元素的索引=一个元素），数组元素相连就构成了念珠似的链表。由于链表末尾的元素没有后续的数据，因此就需要用别的值(在这里是-1)来填充(图4-10)。
链表的删除：
在图4-10表示的链表中，假设要删除从起始位置开始的第3个元素。此时，我们只需要把第2个元素的“下一个元素：2”变成“下一个元素：3”即可。由于数组的元素通常是按照索引顺序来引用的，因此当我们需要引用构成链表的数组的某一个元素时，通过该元素的索引信息就可以找到下一个元素。当第2个元素的下一个元素变成第4个元素后，那么第3个元素就被删除了。虽然第3个元素在物理内存上还残留着，但在逻辑上则确实被删除了(图4-11)。
链表的追加：
假设要在图4-10的链表的第5位前追加一个新数据。此时，我们只需要在刚才消除的第3个元素的位置中保存新的数据，并将第4个元素的“下一个元素：5”变更成“下一个元素：2”，以使新追加的元素的索引信息变成“下一个元素：5”即可。虽然新追加的元素在物理上是第3个，但从逻辑上看来则是第5个(图4-12)。
如果不使用链表数组，那么中途删除或追加元素时，其后的元素就必须要全部移动。在实际的程序中，有时需要对包含数千至数万个元素的数组进行频繁的数据追加或删除操作。如果每次都需要移动数千至数万个元素，那么哪怕是高速计算机也会花费很长时间(图4-13、图4-14)。反之，使用代码清单来追加或删除数据则毫不费事。
标签：4.6,删除,元素,链表,索引,追加,数组 From： https://www.cnblogs.com/ttmeng/p/17107032.html