链表的分类

单向链表

• Head → [A|→] → [B|→] → [C|→] → null

双向链表

• Head ⇄ [A|⇄] ⇄ [B|⇄] ⇄ [C|⇄] ⇄ Tail

循环链表

• 分为单向和双向
• Head → [A|→] → [B|→] → [C|→] → Head

跳跃链表

• https://zhuanlan.zhihu.com/p/634954147
• 根据节点数量将链表分为多级，每个节点包含自身级数的指针数组，其中的元素分别指向同级的下一个节点。从最低的0级到最高级分别可以形成一个独立的子链
• 跳跃链表一定是有序的，通常使用Root数组保存每一级的根节点，每一级子链中的元素都存在于其下一级的子链中，其中0级节点包含所有的元素。链表的级数maxLevel于链表节点数n之间的关系为maxLevel = [lg 2 n] + 1。为了避免在插入和删除节点的时候重新够着链表，放弃对不同级上节点的位置要求，仅保留不同级上的节点数目要求，这样的链表又称为随机跳跃链表。通过choosePowers()函数生成powers数组，然后通过chooseLeves()函数确定当前插入节点的级数。

稀疏表

• 当一个表只有一小部分空间被使用的时候成为稀疏表。其中很多稀疏表都可以使用链表的数据结构方式解决。例如当储存一个学校所有学生成绩时。如果用二维数组，课程作为行，学生作为列，这时很多学生并不会选修所有的课，这会造成大量的空间浪费。此时，使用Class和Student两个数组，其中class数组每个元素记录选修这门课程的链表，Student中每个元素记录这个学生所修课程的链表，这样会大量节约所需的内存空间。
   数组的优点是随机访问，因此需要直接访问某个元素，数组是更好的选中，如二分查找法和大多数排序算法。当只需要固定的访问某些元素（如第一个和最后一个），并且结构的改变是算法的核心则链表是更好的选则，如队列。另外数组的另一个优点是空间，链表本身还会花空间存储指向节点的指针。