太刺激了，面试官让我手写跳表，而我用两种实现方式吊打了TA！

首先，找到6的位置，走过的路径为 h1->3->3->4，发现应该插入到4和7之间，插入之：

然后，建立竖线，即向下的指针，一共有三层，因为超过了当前最高层级，所以，头节点也要相应地往上增加一层，如下：

此时，横向的指针是一个都没动的。

最后，修正横向的指针，即 h2->6、3->6、6->7，修正完成则表示插入元素成功：

这就是插入元素的整个过程，Show You the Code：

/**   * 添加元素   * 不能添加相同的元素   * @param value   */ public void add(T value) {     System.out.println("添加元素：u6b22u8fceu5173u6ce8u516cu4f17u53f7u5f64u54e5u8bfbu6e90u7801uff0cu83b7u53d6u66f4u591au67b6u6784u3001u57fau7840u3001u6e90u7801u597du6587uff01");     if (value == null) {         throw new NullPointerException();     }     Comparator cmp = this.comparator;     // 第一步：先找到前置的索引节点     Node preIndexNode = findPreIndexNode(value, true);     if (preIndexNode.value != null && cmp.compare(preIndexNode.value, value) == 0) {         return;     }      // 第二步：加入到链表中     Node q, n, t;     int c;     for (q = preIndexNode;;) {         n = q.next;         if (n == null) {             c = 1;         } else {             c = cmp.compare(n.value, value);             if (c == 0) {                 return;             }         }         if (c > 0) {             // 插入链表节点             q.next = t = new Node<>(value, n);             break;         }         q = n;     }      // 决定索引层数，每次最多只能比最大层数高1     int random = ThreadLocalRandom.current().nextInt();     // 倒数第一位是0的才建索引     if ((random & 1) == 0) {         int level = 1;         // 从倒数第二位开始连续的1         while (((random >>>= 1) & 1) != 0) {             level++;         }          HeadIndex oldHead = this.head;         int maxLevel = oldHead.level;         Index idx = null;         // 如果小于或等于最大层数，则不用再额外建head索引         if (level <= maxLevel) {             // 第三步1：先连好竖线             for (int i = 1; i <= level; i++) {                 idx = new Index<>(t, idx, null);             }         } else {             // 大于了最大层数，则最多比最大层数多1             level = maxLevel + 1;             // 第三步2：先连好竖线             for (int i = 1; i <= level; i++) {                 idx = new Index<>(t, idx, null);             }             // 新建head索引，并连好新head到最高node的线             HeadIndex newHead = new HeadIndex<>(oldHead.node, oldHead, idx, level);             this.head = newHead;             idx = idx.down;         }          // 第四步：再连横线，从旧head开始再走一遍遍历         Index qx, r, d;         int currentLevel;         for (qx = oldHead, currentLevel=oldHead.level;qx != null;) {             r = qx.right;             if (r != null) {                 // 如果右边的节点比value小，则右移                 if (cmp.compare(r.node.value, value) < 0) {                     qx = r;                     continue;                 }             }             // 如果目标层级比当前层级小，直接下移             if (level < currentLevel) {                 qx = qx.down;             } else {                 // 右边到尽头了，连上                 idx.right = r;                 qx.right = idx;                 qx = qx.down;                 idx = idx.down;             }             currentLevel--;         }     } } 

删除元素

经过了上面的插入元素的全过程，删除元素相对来说要容易了不少。

同样地，首先，找到要删除的元素，从链表中删除。

然后，修正向右的索引，修正了向右的索引，向下的索引就不用管了，相当于从整个跳表中把向下的那一坨都删除了，等着垃圾回收即可。

其实，上面两步可以合成一步，在寻找要删除的元素的同时，就可以把向右的索引修正了。

以下图为例，此时，要删除7这个元素：

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!