NOI 集训队论文 对块状链表的一点研究

数组能够在O(1)的时间内找到所要执行操作的位置,但无论是插入或删除都要移动之后的所有数据,复杂度是O(n)的。 链表能够在O(1)的时间内插入和删除一段数据,但是在寻找操作位置时,却要遍历整个链表,复杂度同样时O(n)的。 这两种数据结构各有优缺点,我们尝试将两种数据结构融合成一个全新的数据结构:块状链表。