Data structure: jump linked list

Pay attention to the official account and exchange with each other. Search by WeChat: Sneak ahead.

What is a jump list

The balance data structures often used in development include B number, red black number and AVL number. But if you implement one of them, it is very difficult and takes time to implement. The jump linked list is a fast search data structure based on the linked list array. At present, it is used by the open source software Redis and LevelDB. Its efficiency is comparable to that of red black tree and AVL tree

Jump linked list structure


public class SkipList<T> {
    //Head and tail of jump table
    private SkipListNode<T> head;
    //The length of the elements contained in the jump table
    private int length;
    //The historical maximum number of layers of the skip table
    public int maxLevel;
    public SecureRandom random;
    private static final int MAX_LEVEL = 31;
    public SkipList() {
        //Initialize the head and tail nodes and their relationship
        head = new SkipListNode<>(SkipListNode.HEAD_SCORE, null, MAX_LEVEL);
        //Initialization size, layer, random
        length = 0;
        maxLevel = 0; // The number of layers is calculated from zero
        random = new SecureRandom();
  • Header: points to the header node of the jump table
  • maxLevel: records the layers of the node with the largest number of layers in the current hop table
  • Length: the length of the elements in the linked list


The composition of the jump linked list node: the front node, the back node, the score (the key value of the map), and the storage object value

public class SkipListNode<T> {
    //Score value sorted in the skip table
    public double score;
    public T value;
    public int level;
    // Front and rear nodes
    public SkipListNode<T> next,pre;
    //Layer formed by upper and lower nodes
    public SkipListNode<T>[] levelNode;
    private SkipListNode(double score, int level){
        this.score = score;
        this.level = level;
    public SkipListNode(double score, T value, int level) {
        this.score = score;
        this.value = value;
        this.level = level;
        this.levelNode = new SkipListNode[level+1];
        //Initialize SkipListNode and node of each layer
        for (int i = level; i > 0; --i) {
            levelNode[i] = new SkipListNode<T>(score, level);
            levelNode[i].levelNode = levelNode;
        this.levelNode[0] = this;
    public String toString() {  return "Node[score=" + score + ", value=" + value + "]"; }

Jump table is to trade space for time

  • The jump linked list node I implemented includes a levelNode member attribute. It is the node layer. The key point of fast access to jump linked list is it
  • We usually access an array in order, and the efficiency of jump linked list is higher than that of array linked list, because it uses node layer to store multi-level indexes to form a sparse index, so it needs more memory space

How fast is the jump list

  • If a linked list has n nodes and one node is extracted from every two nodes to establish an index, the number of nodes of the first layer index is about n/2, the number of nodes of the second layer index is about n/4, and so on. The number of nodes of the m-layer index is about n/(2^m)
  • When accessing data, you can locate the m-1 layer index data from the m-layer index query. m-1 is about 1 / 2 of m layer. That is, the optimal time complexity is O(log/N)
  • Worst case scenario. In the actual implementation, each layer of index cannot be halved by the amount of data each time. Therefore, in a compromise way, the index of each layer is randomly built with full data. In other words, the worst-case time complexity is O(N), but the optimal time complexity remains unchanged


  • The query starts by traversing the index m of the highest maxLevel. Follow the steps below to find the left node equal to or closest to score
    • 1: If the next node score of the same layer index is less than the query score, skip to the next node. cur = next
    • 2: If next is empty. Or the score of the next node is greater than the query score. Then skip to the next layer m-1 index and cycle 2
    • Cycle steps 1 and 2 until the access node score is consistent with the query score, or the index layer is zero
// SkipList
    private SkipListNode<T> findNearestNode(double score) {
        int curLevel = maxLevel;
        SkipListNode<T> cur = head.levelNode[curLevel];
        SkipListNode<T> next =;
        // The score is the same as the current node or next is null
        while (score != cur.score && curLevel > 0) {
            // 1 right next traversal
            if (next != null && score >= next.levelNode[0].score) {
                cur = next;
            next = cur.levelNode[curLevel].next;
            // 2. Traverse down and reduce the number of layers by 1
            while ((next == null || score < next.levelNode[0].score) && curLevel > 0) {
                next = cur.levelNode[--curLevel].next;
        // The bottom node.
        return cur.levelNode[0];
    public SkipListNode<T> get(double score) {
        //Returns the node closest to the score at the bottom of the jump table
        SkipListNode<T> p = findNearestNode(score);
        //If the score is the same, this node is returned
        return p.score == score ? p : null;


  • If the score exists, replace value
  • If the node corresponding to the score does not exist, a random index level (value 0 ~ 31) is selected. Then add 0 to the index of the level layer by relying on the node attribute levelNode
    public T put(double score, T value) {
        //First, get the node closest to the key at the bottom of the hop table
        SkipListNode<T> p = findNearestNode(score);
        if (p.score == score) {
            // In the jump table, only the bottom node has a real value. Just modify the bottom value
            T old = p.value;
            p.value = value;
            return old;
        // nowNode is the newly created bottom node. Index levels 0 to 31
        int nodeLevel = (int) Math.round(random.nextDouble() * 32);
        SkipListNode<T> nowNode = new SkipListNode<T>(score, value, nodeLevel);
        //Initialize each layer and connect the nodes before and after each layer
        int level = 0;
        while (nodeLevel >= p.level) {
            for (; level <= p.level; level++) {
                insertNodeHorizontally(p.levelNode[level], nowNode.levelNode[level]);
            p = p.pre;
        // At this time, the number of layers of p is greater than that of nowNode before entering the cycle
        for (; level <= nodeLevel; level++) {
            insertNodeHorizontally(p.levelNode[level], nowNode.levelNode[level]);
        this.length ++ ;
        if (this.maxLevel < nodeLevel) {
            maxLevel = nodeLevel;
        return value;

    private void insertNodeHorizontally(SkipListNode<T> pre, SkipListNode<T> now) {
        //Consider now first =;
        now.pre = pre;
        //Consider the next node of pre
        if ( != null) {
   = now;
        //Finally, consider pre = now;


  • Use the get method to find the element, and then release the reference relationship between the node attribute levelNode and the index of each layer
    public T remove(double score){
        //Find the node corresponding to this key at the bottom
        SkipListNode<T> now = get(score);
        if (now == null) {
            return null;
        SkipListNode<T> curNode, next;
        //Dereference the node attribute levelNode before and after each layer index
        for (int i = 0; i <= now.level; i++){
            curNode = now.levelNode[i];
            next =;
            if (next != null) {
                next.pre = curNode.pre;
        this.length--; //Update size and return the old value
        return now.value;

Use example

    public static void main(String[] args) {
        SkipList<String> list=new SkipList<>();
        list.put(1, "csc");
        list.put(3, "lwl");
        list.put(2, "hello world!");


Welcome refers to an error in the text

Reference articles

Keywords: Java data structure Interview linked list

Added by brianb on Tue, 04 Jan 2022 02:51:34 +0200