我们知道如果一个数组是有序的,查询的时候可以使用二分法进行查询,时间复杂度可以降到 O(logn) ,但如果链表是有序的,我们仍然是从前往后一个个查找,这样显然很慢,这个时候我们可以使用跳表(Skip list),跳表就是多层链表,每一层链表都是有序的,最下面一层是原始链表,包含所有数据,从下往上节点个数逐渐减少,如下图所示。 跳表的特性: 跳表节点的插入 如果是单链表只需要找出待插入节点的前一个节点即可,但在跳表中不光要插入到原始链表中,在他上面的某些层也有可能需要插入,实现方式有随机性和确定性两种选择,其中随机性一般比较常见。比如要在跳表中插入一个元素,可以随机生成一个数字 level ,从 level 层往下每层都要插入。所以跳表中节点不光有 next 属性,还有 down 属性,他指向下一个节点的引用,先来看下跳表的节点类。 // 跳表的节点类。 public class SkipListNode { // 跳表节点的值,在实际应用中节点类可以加个泛型,这里为了方便介绍,直接使用 int 类型。 public int val; public SkipListNode next;// 指向后面一个节点。 public SkipListNode down;// 指向下面一层的相同节点。 public SkipListNode(int val, SkipListNode next) { this.val = val; this.next = next; } }
在跳表中我们还需要定义一个最大值 MAX_LEVEL ,就是跳表的最大层级数不能超过这个值。我们再来看下索引层级的随机函数,他主要用于在插入节点的时候从第几层开始插入,他是随机的,越往上机率越小,这也符合跳表的特性,越往上节点越少,最大值不能超过 MAX_LEVEL 。 // 索引层级随机函数。 private int randLevel() { int level = 1;// 1 的概率是0.5,2的概率是0.25,3的概率是0.125,4的概率是0.0625,…… // Math.random()每次会生成一个 0 到 1 之间的随机数 while (Math.random() < 0.5f && level < MAX_LEVEL) level++; return level; }
在跳表中每一层都有一个头节点,头节点不存储任何数据,其中 head 是最上面一层的头节点,跳表的插入,删除以及查找都是从他开始的,如果想要获取下面一层的头节点,可以通过 head.down 获取。跳表的插入总共分为 3 步:
第一步:在跳表节点插入之前先判断上面的层级有没有创建,如果没有创建,需要先创建,如下图所示。 第二步:如果创建了层级或者插入的层级小于跳表的层数,需要找到每一层待插入节点的前一个节点,如下图所示。
第三步:从上往下插入节点,链表的插入可以参考单向链表,插入的节点除了连接 next 指针以外,还要连接 down 指针。 来看下代码: public void add(int num) { int level = randLevel();// 从第几层开始插入,随机数。 // 记录待插入节点的前一个节点。 SkipListNode[] preNodes = new SkipListNode[level]; // 第一步:如果跳表层数比较少,在上面添加,层数至少为 level 。 if (curLevelCount < level) { SkipListNode beforeHead = head; head = new SkipListNode(-1, null);// 更新 head 节点。 SkipListNode curHead = head; // 在上面添加每层的头节点。 for (int i = curLevelCount; i < level - 1; i++) { SkipListNode node = new SkipListNode(-1, null); curHead.down = node; curHead = node; } // 最后创建的链表头节点和之前的头节点连在一起。 curHead.down = beforeHead; } // 第二步:从上往下查找每层待插入节点的前一个节点。 SkipListNode pre = head; // 上层不需要插入的跳过。 for (int i = curLevelCount - 1; i >= level; i--) pre = pre.down; // 从当前层往下每层都要插入该节点,找出每层待插入节点的前一个节点。 for (int i = level - 1; i >= 0; i--) { while (pre.next != null && pre.next.val < num) pre = pre.next; preNodes[i] = pre;// 记录前一个节点。 pre = pre.down; } // 第三步:节点插入,插入的时候不光有 next 指针,而且还有 down 指针。 SkipListNode topNode = null; // 把新建节点 node 插到该层下面的每一层。 for (int i = level - 1; i >= 0; i--) { // 创建新节点。 SkipListNode node = new SkipListNode(num, preNodes[i].next); // 链表的插入,参见单向链表的插入。 preNodes[i].next = node; // 上下也要连接。 if (topNode != null) topNode.down = node; topNode = node; } if (level > curLevelCount)// 更新跳表的层级,用来记录当前跳表的层级。 curLevelCount = level; }
跳表的查询
跳表的查询从最上面一层开始,每层往后查找,如果后面没有节点了或者后面的节点值比要查找的大,就往下面查找,如果找到返回 true ,如果没找到返回 false ,如下图所示。 来看下代码: // 查找值为 target 的节点。 public boolean search(int target) { SkipListNode pre = head; while (pre != null) { // 如果当前节点值小于 target ,需要到右边查找,如果右边没有节点就到下边查找。 if (pre.val < target) { if (pre.next == null)// 右边没有节点,到下边查找 pre = pre.down; else pre = pre.next.val > target ? pre.down : pre.next; } else if (pre.val == target) {// 如果找到直接返回。 return true; } else { return false;// 如果当前节点值大于 target ,说明没有,直接返回 false 。 } } return false; }
跳表节点的删除 节点的删除和添加类似,也是先从上往下找到待删除节点的前一个节点,因为单链表中节点的添加和删除都需要前一个节点。找到之后从当前层往下每一层都要删除,如果上面一层的节点都被删除完了,还需要把上层的链表清空,如下图所示。 来看下代码: public boolean remove(int num) { // 删除链表和插入链表类似,都是需要先找到插入或删除链表的前一个节点。 int topIndex = -1;// 从当前层开始往下每层都要删除。 // 查找待删除节点的前一个节点,从上面一层开始查找。 SkipListNode pre = head; for (int i = curLevelCount - 1; i >= 0; i--) { while (pre.next != null && pre.next.val < num) pre = pre.next; // 如果找到就终止查找,表示在当前层以及他下面的所有层都要删除该节点。 if (pre.next != null && pre.next.val == num && topIndex == -1) { topIndex = i; break; } if (pre.down == null)// 如果跳表中没有要删除的节点,返回 false 。 return false; pre = pre.down;// 当前层没找到就往下一层继续查找。 } if (topIndex == -1)// 如果跳表中没找到要删除的节点,返回 false 。 return false; // 从 topIndex 层开始,他下面的每一层都要删除。 for (int i = topIndex; i >= 0; i--) { if (pre.next != null)// 节点删除,参考单向链表删除。 pre.next = pre.next.next; pre = pre.down;// 继续下一层的删除。 if (pre != null)// 找到待删除节点的前一个节点。 while (pre.next != null && pre.next.val != num) pre = pre.next; } // 如果上面一层的节点被删除完了,要更新 curLevelCount 的值 ,还要更新 head节点。 SkipListNode cur = head; while (curLevelCount > 1 && cur.next == null) { cur = cur.down; head = cur; curLevelCount--; } return true; }
最后我们再来看下完整代码: public class SkipList1 { // 打印跳表。 private static void printLinked(SkipList1 skipList) { SkipListNode cur = skipList.head; while (cur != null) { SkipListNode tmp = cur.next; while (tmp != null) { System.out.print(tmp.val + ","); tmp = tmp.next; } System.out.println(); cur = cur.down; } } // 跳表的最大层数。 private int MAX_LEVEL = 16; // 当前跳表的最大层级。 private int curLevelCount = 1; // 初始化定义一个头节点,指向最上面一层的第一个元素,头节点不存储任何数据。 private SkipListNode head; public SkipList1() {// 构造函数。 head = new SkipListNode(-1, null); } // 查找值为 target 的节点。 public boolean search(int target) { SkipListNode pre = head; while (pre != null) { // 如果当前节点值小于 target ,需要到右边查找,如果右边没有节点就到下边查找。 if (pre.val < target) { if (pre.next == null)// 右边没有节点,到下边查找 pre = pre.down; else pre = pre.next.val > target ? pre.down : pre.next; } else if (pre.val == target) {// 如果找到直接返回。 return true; } else { return false;// 如果当前节点值大于 target ,说明没有,直接返回 false 。 } } return false; } public void add(int num) { int level = randLevel();// 从第几层开始插入,随机数。 // 记录待插入节点的前一个节点。 SkipListNode[] preNodes = new SkipListNode[level]; // 第一步:如果跳表层数比较少,在上面添加,层数至少为 level 。 if (curLevelCount < level) { SkipListNode beforeHead = head; head = new SkipListNode(-1, null);// 更新 head 节点。 SkipListNode curHead = head; // 在上面添加每层的头节点。 for (int i = curLevelCount; i < level - 1; i++) { SkipListNode node = new SkipListNode(-1, null); curHead.down = node; curHead = node; } // 最后创建的链表头节点和之前的头节点连在一起。 curHead.down = beforeHead; } // 第二步:从上往下查找每层待插入节点的前一个节点。 SkipListNode pre = head; // 上层不需要插入的跳过。 for (int i = curLevelCount - 1; i >= level; i--) pre = pre.down; // 从当前层往下每层都要插入该节点,找出每层待插入节点的前一个节点。 for (int i = level - 1; i >= 0; i--) { while (pre.next != null && pre.next.val < num) pre = pre.next; preNodes[i] = pre;// 记录前一个节点。 pre = pre.down; } // 第三步:节点插入,插入的时候不光有 next 指针,而且还有 down 指针。 SkipListNode topNode = null; // 把新建节点 node 插到该层下面的每一层。 for (int i = level - 1; i >= 0; i--) { // 创建新节点。 SkipListNode node = new SkipListNode(num, preNodes[i].next); // 链表的插入,参见单向链表的插入。 preNodes[i].next = node; // 上下也要连接。 if (topNode != null) topNode.down = node; topNode = node; } if (level > curLevelCount)// 更新跳表的层级,用来记录当前跳表的层级。 curLevelCount = level; } public boolean remove(int num) { // 删除链表和插入链表类似,都是需要先找到插入或删除链表的前一个节点。 int topIndex = -1;// 从当前层开始往下每层都要删除。 // 查找待删除节点的前一个节点,从上面一层开始查找。 SkipListNode pre = head; for (int i = curLevelCount - 1; i >= 0; i--) { while (pre.next != null && pre.next.val < num) pre = pre.next; // 如果找到就终止查找,表示在当前层以及他下面的所有层都要删除该节点。 if (pre.next != null && pre.next.val == num && topIndex == -1) { topIndex = i; break; } if (pre.down == null)// 如果跳表中没有要删除的节点,返回 false 。 return false; pre = pre.down;// 当前层没找到就往下一层继续查找。 } if (topIndex == -1)// 如果跳表中没找到要删除的节点,返回 false 。 return false; // 从 topIndex 层开始,他下面的每一层都要删除。 for (int i = topIndex; i >= 0; i--) { if (pre.next != null)// 节点删除,参考单向链表删除。 pre.next = pre.next.next; pre = pre.down;// 继续下一层的删除。 if (pre != null)// 找到待删除节点的前一个节点。 while (pre.next != null && pre.next.val != num) pre = pre.next; } // 如果上面一层的节点被删除完了,要更新 curLevelCount 的值 ,还要更新 head节点。 SkipListNode cur = head; while (curLevelCount > 1 && cur.next == null) { cur = cur.down; head = cur; curLevelCount--; } return true; } // 索引层级随机函数。 private int randLevel() { int level = 1; // Math.random()每次会生成一个 0 到 1 之间的随机数 while (Math.random() < 0.5f && level < MAX_LEVEL) level++; return level; } // 跳表的节点类。 public class SkipListNode { // 跳表节点的值,在实际应用中节点类可以加个泛型,这里为了方便介绍,直接使用 int 类型。 public int val; public SkipListNode next;// 指向后面一个节点。 public SkipListNode down;// 指向下面一层的相同节点。 public SkipListNode(int val, SkipListNode next) { this.val = val; this.next = next; } } }
上面代码中虽然上下两个节点的值是一样的,但我们还是创建了不同的对象,实际上我们只需要创建一个对象即可,上下关系不在是 down ,而是一个数组。 来看下代码:
public class SkipList2 {
// 打印跳表的值,由于level是随机生成的,所以同样的数据每次打印都会不一样, // 如果想调试,可以让level变成一个固定值,这样同样的数据每次打印结果都会一样了。 private static void printLinked(SkipList2 skipList) { SkipListNode cur = skipList.head; for (int i = skipList.curLevelCount - 1; i >= 0; i--) { // 这里是横向查找,就是当前层往后面查找,这里是第 i 层。 SkipListNode pre = cur; while (pre.next[i] != null) { System.out.print(pre.next[i].val + ","); pre = pre.next[i]; } System.out.println(); }
}
// 跳表的最大层数。 private int MAX_LEVEL = 16;
// 当前跳表的最大层级。 private int curLevelCount = 1;
// 初始化定义一个头节点,指向最上面一层的第一个元素,头节点不存储任何数据。 private SkipListNode head;
public SkipList2() {// 构造函数。 head = new SkipListNode(-1); }
// 查找值为 target 的节点。 public boolean search(int target) { SkipListNode pre = head; // 这里for循环是逆序的,他是从最上面一层开始查找,for 循环是纵向查找,里面的while循环是横向查找。 for (int i = curLevelCount - 1; i >= 0; i--) { // 这里是横向查找,就是当前层往后面查找,这里是第 i 层。 while (pre.next[i] != null && pre.next[i].val < target) pre = pre.next[i]; // 如果在当前层查找到,直接返回true。 if (pre.next[i] != null && pre.next[i].val == target) return true; } return false;// 没查找到,返回false。 }
// 添加数据 public void add(int num) { int level = randLevel();// 需要插入第几层。 // 每一层初始化默认为head节点。 SkipListNode[] preNodes = new SkipListNode[level]; for (int i = 0; i < level; i++) preNodes[i] = head;
// 找到每一层待插节点的前一个节点。 SkipListNode pre = head; // 从当前层往下每层都要插入该节点。 for (int i = level - 1; i >= 0; i--) { while (pre.next[i] != null && pre.next[i].val < num) pre = pre.next[i]; preNodes[i] = pre; }
// 创建新节点。 SkipListNode node = new SkipListNode(num); // 把新建节点 node 插到该层以及下面的所有层。 for (int i = level - 1; i >= 0; i--) { // 链表的插入,参见单向链表的插入。 node.next[i] = preNodes[i].next[i]; preNodes[i].next[i] = node; } if (level > curLevelCount)// 更新跳表的层级。 curLevelCount = level; }
public boolean remove(int num) { // 删除链表和插入链表类似,都是需要先找到插入或删除链表的前一个节点。 SkipListNode[] preNodes = new SkipListNode[curLevelCount]; int topIndex = -1;// 从当前层往下都要移除。 // 查找待删除节点的前一个节点,从最上面一层开始查找。 SkipListNode pre = head; for (int i = curLevelCount - 1; i >= 0; i--) { while (pre.next[i] != null && pre.next[i].val < num) pre = pre.next[i]; if (pre.next[i] != null && pre.next[i].val == num && topIndex == -1) topIndex = i; preNodes[i] = pre;// 记录每层待删除节点的前一个节点。 } if (topIndex == -1)// 如果没找到,也就是待删除的节点在跳表中不存在,直接返回。 return false;
// 删除操作。 for (int i = topIndex; i >= 0; i--) preNodes[i].next[i] = preNodes[i].next[i].next[i]; // 更新索引层数,如果当前层消失了,curLevelCount要减 1 。 while (curLevelCount > 1 && head.next[curLevelCount - 1] == null) curLevelCount--; return true; }
// 索引层级随机函数。 private int randLevel() { int level = 1;// 1 的概率是0.5,2的概率是0.25,3的概率是0.125,4的概率是0.0625,…… // Math.random()每次会生成一个 0 到 1 之间的随机数 while (Math.random() < 0.5f && level < MAX_LEVEL) level++; return level; }
// 跳表的节点。 public class SkipListNode { // 跳表节点的值,在实际应用中节点类可以加个泛型,这里为了方便介绍,直接使用 int 类型。 public int val;
public SkipListNode(int val) { this.val = val; }
// 普通的链表这里是 next 节点,而跳表这里需要记录每一层的节点,所以是数组。 public SkipListNode[] next = new SkipListNode[MAX_LEVEL]; }
|