我是不是应该说，如果事先知道“n”（要存储的元素数）的话，像数组这样的跳过列表会非常有效？
跳过列表的maxlevel是(log n + 1)，由于我需要在创建跳过列表之前知道maxlevel，这意味着我应该知道将要存储的元素的数量。
最佳答案
只要你准备动态地调整头部的大小（头部的大小正好maxlevel），就不需要在创建之前知道skiplist的最大级别。由于maxlevel近似log N，头部的大小调整很少发生，当它发生时，它涉及的工作量很小。如果你真的想避免这一点，你可以先创建一个容量足以容纳整个可用存储空间的头部，尽管如果你的大部分技巧是几百个元素，那将是浪费空间。
这一切之所以有效，是因为搜索技能专家的过程从不向上移动一个级别；只向下移动一个级别。因此，插入比任何现有节点更高级别的新节点不需要修改除头部之外的任何现有节点，必须修改该节点以指向其最高级别的新节点。（否则，新级别将毫无用处。）
作为一个奇怪的实现细节，不需要存储节点的大小；节点被指向i级别的事实足以证明节点至少有i级别，因此不需要将i与节点的大小进行比较。只需要知道头部的大小。