链表
链表
链表 是一种非常常见的数据结构，它是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。这给了链表非常大的灵活性，可以随意的在任意位置插入，删除，拼接等等。但这也使得链表的访问较为困难，因为链表的每个节点并不是连续存储的，所以不能像数组一样，通过下标就能访问到某个节点，必须从头开始遍历，直到找到目标节点。
链表和数组恰好是一对镜像：数组随机访问是 O(1)，但插入/删除要搬移元素；链表插入/删除只需修改指针（定位到位置后是 O(1)），但查找必须从头遍历，是 O(n)。
试一试，在下面的可视化组件中体验链表的随机读取、头部/末尾添加、查找、插入与删除。对比数组：链表按索引访问必须遍历，但头部添加通常是 O(1)；末尾添加是否 O(1) 取决于是否维护 tail 指针。
循环链表
循环链表是一种特殊的链表，它的最后一个节点的指针指向头节点，形成一个环。循环链表的优点是，可以方便的从任意节点开始遍历链表，而不需要知道链表的长度。循环链表的缺点是，由于需要维护一个指向头节点的指针，所以空间复杂度是 O(1)，而普通链表的空间复杂度是 O(n)。
试一试，注意尾节点 next 如何回指 head；按索引读取仍需遍历，末尾添加也需先找尾。
双向链表
双向链表是一种特殊的链表，它的每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。双向链表的优点是，可以方便的从任意节点开始遍历链表，而不需要知道链表的长度。双向链表的缺点是，由于需要维护两个指针，所以空间复杂度是 O(2n)，而普通链表的空间复杂度是 O(n)。
试一试，观察 prev / next；尝试读取靠后的下标（会从 tail 侧遍历），末尾添加可直接利用 tail 指针。
块状链表
块状链表是一种特殊的链表，它的每个节点都包含一个块，块中包含多个节点。块状链表的优点是，一个块内的操作是随机访问的，性能更好，缺点是，块的拆分和合并操作比较复杂，有时反复的删除添加可能会性能下降。
试一试，数据按块组织：定位块后块内随机读取为 O(1)；尾块有空间时末尾添加也无需遍历整条链。
双循环块状链表
将循环链表、双向链表和块状链表结合起来，就得到了双循环块状链表。双循环块状链表也同时保留了循环链表、双向链表和块状链表的优点和缺点。
试一试，三种特性同时开启：块内随机访问、双向 tail 指针、尾回指 head。
跳跃表
跳跃表是一种特殊的链表，它的每个节点包含一个跳过不同数目节点的指针。跳跃表的优点是，可以以 log(n) 的时间复杂度进行查找，插入，删除操作。缺点是，实现比较复杂，需要维护多个指针，所以空间复杂度是 O(nlogn)，而普通链表的空间复杂度是 O(n)。