亲宝软件园·资讯

展开

Java跳跃表

Carol淋 人气:0

跳表全称叫做跳跃表,简称跳表,是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序列表上面增加多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也提高插入和删除的性能,redis中的有序集合set就是用跳表实现的,面试时候也经常会问。 

这里我们原始数据个数n=10,以间隔k=2建立索引,则第一层索引10/2=5个,第二层⌈10/2^2⌉=3个,第三层⌈10/2^3⌉=2个,第四层⌈10/2^4⌉=1个。根据上图我们来分析一下,跳表的结构是一棵树(除原始数据层外),树的左指针指向对应的下一层链表的节点,右指针指向当前链表的下一个节点,且树高为log(n),对于每一层需要比较的次数最多为k,则时间复杂度为O(k*log(n)),k为常数项,所以跳表查询时间复杂度为O(log(n))。因为需要额外的空间存储索引,是典型的以空间换时间,空间复杂度为O(n)。

接下来我们自己实现一个跳表:

节点数据结构定义:根据跳表结构,节点首先需要一个value存储当前节点值,需要一个next指针指向同一层的下一个节点,需要一个nodeValue指针指向下一层对应节点,但是这里为了插入删除方便,引入了一个prev指针,指向同一层的上一个节点。

class Node {
    //当前节点值
    private Integer value;
    //当前节点所属链表下一个节点
    private Node next;
    //当前节点所属链表上一个节点
    private Node prev;
    //当前节点指向的另一个索引链表/原始值链表节点
    private Node nodeValue;
    Node(Integer value) {
        this.value = value;
    }
}

初始化一个跳表:跳表的建立需要在数据有序的基础上,然后从下往上在下一层的基础上,间隔k生成当前层的节点,新生成的节点需要与当前层上一个节点连接起来,并且指向生成它的下一层节点。

/**
 * 原始数据链表
 */
private Node head ;
/**
 * 最终的跳表结构:保存索引链表及原始链表
 */
private List<Node> indexList;
/**
 * 跳表层数
 */
private int level;

/**
* 初始化
*/
public void init() {
    //带头节点的链表,便于操作
    head = new Node(-1);
    head.next = head;
    indexList = new ArrayList<>();
    level = 0;
}
/**
 * 初始化跳表
 * @param k 间隔
 * @param nums 原始数据(已排序)
 */
public void init(int k, int[] nums) {
    //初始化数据链表
    Node temp = head;
    for (int num : nums) {
        Node cur = new Node(num);
        cur.prev = temp;
        temp.next = cur;
        temp = temp.next;
    }
    //新节点保存(最底层)
    indexList.add(head);

    //循环生成索引结构,结束条件,当层仅一个元素
    temp = head.next;
    while (true) {
        //当前链表第几个元素
        int i = 0;
        //生成另一条链表长度
        int size = 0;
        Node indexNode = new Node(-1);
        indexNode.next = indexNode;
        Node indexNodeTemp = indexNode;
        while (null != temp) {
            //间隔k生成节点
            if (i % k == 0) {
                Node curNode = new Node(temp.value);
                curNode.nodeValue = temp;
                curNode.prev = indexNodeTemp;
                indexNodeTemp.next = curNode;
                indexNodeTemp = indexNodeTemp.next;
                ++ size;
            }
            ++ i;
            temp = temp.next;
        }
        indexList.add(indexNode);
        temp = indexNode.next;
        //当生成的索引链表仅1时不需要再继续生成
        if (size == 1) {
            break;
        }
    }
    level = indexList.size();
}

从跳表中查找元素:从最顶层索引链表开始查找,找到第一个大于当前节点的元素,则需要查找的元素在当前节点与之前节点之间,则从当前节点的上一个节点prev往下nodevalue继续进行查找,直到当前节点值与查找值相等,则直接返回当前节点,返回的节点可能是索引节点,也可能是原始数据节点,如果需要找到原始数据节点,则通过nodeValue继续往下找。

/**
 * 是否存在num
 * @param num
 * @return
 */
public boolean hasNum(int num) {
    Node result = this.findNum(num);
    return null != result;
}
/**
 * 查找num(返回的可能是索引,也可能是原始数据,根据nodeValue可以判断,也可以找到原始数据)
 * @param num
 */
public Node findNum(int num) {
    //跳表结构indexList是数据-》第一层索引-》第二层索引-》。。。。
    //1.直接匹配到
    //2.找到第一个大于当前元素的数,找前一个
    Node node = indexList.get(indexList.size() - 1).next;
    Node last = null;
    while (null != node) {
        if (node.value == num) {
            //已经找到元素
            return node;
        }
        if (node.value > num) {
            if (null == last) {
                //比最小值还小
                return null;
            }
            //找到了第一个大于num的索引node
            //到下一层去继续找
            node = last.nodeValue;
            last = null;
            continue;
        }
        last = node;
        node = null != node.next ? node.next : node.nodeValue;
    }
    return null;
}

删除节点:首先通过上面的查找方法找到目标节点,如果目标节点是索引值,则需要从当前索引层,层层往下删除包括原始数据链表,如果是原始数据值,则直接删除,暂不调整。

/**
 * 构建索引时:自底向上逐层构建,如果索引需要删除(当两个索引之间没有任何数据时候,删除)
 * @param num
 * @return
 */
public boolean remove(int num) {
    Node node = this.findNum(num);
    if (null == node) {
        //不需要移除
        return false;
    }
    if (null == node.nodeValue) {
        //数据链表,可以直接移除
        //是否最后一个节点
        if (null == node.next) {
            node.prev.next = null;
            return true;
        }
        node.next.prev = node.prev;
        node.prev.next = node.next;
        return true;
    }
    //当前在索引上,自上而下删除索引及数据
    while (null != node) {
        Node cur = node.nodeValue;
        if (null == node.next) {
            node.prev.next = null;
        } else {
            node.next.prev = node.prev;
            node.prev.next = node.next;
        }
        node = cur;
    }
    return true;
}

新增节点:新增节点时候,如果不对索引进行调整,极端情况下,每次新增的节点都在之前第一层两个节点之间,当这之间的链表越变越长,时间复杂度直接退化为O(n),所以需要同时新增索引,维持跳表的高效性。但是我们如何新增,有一个方法就是,在新增节点时,随机选择k,即第k级索引,从1~k新增索引。

/**
 * 首先需要查找插入位置,如果比最小的还小,直接在前面插入
 * 否则需要从最顶级一直查找到数据链表,找到插入位置,插入,在查找的过程中,就可以开始插入索引节点,
 * 从上往下进行插入
 * @param num
 */
public void add(int num) {
    int k = this.generatorLevelK();
    //寻找插入点的过程和查找过程基本一致
    //顶级索引链表
    Node node = indexList.get(indexList.size() - 1).next;
    int index = 1;
    while (null != node) {
        //找到第一个node.value >= num的元素,在前面插入
        if (node.value >= num) {
            //已经找到,前插
            if (index >= k) {
                Node newNode = new Node(num);
                Node temp = node.prev;
                newNode.next = temp.next;
                temp.next.prev = newNode;
                newNode.prev = temp;
                temp.next = newNode;
            }
            //找的时候往后面找的,但是当前已经先于num了,下一次再往后面找,就出现问题
            if (null == node.prev.prev) {
                //第一个节点就符合条件
                node = node.nodeValue;
                continue;
            }
            node = node.prev.nodeValue;
            ++ index;
            continue;
        }

        //没有找到,但是当前已经是链表最后一个元素了
        if (null == node.next) {
            if (index >= k) {
                Node newNode = new Node(num);
                newNode.prev = node;
                node.next = newNode;
            }
            if (null == node.prev.prev) {
                //第一个节点就符合条件
                node = node.nodeValue;
                continue;
            }
            node = node.prev.nodeValue;
            ++ index;
            continue;
        }

        node = node.next;
    }

}

private int generatorLevelK() {
    Random random = new Random();
    return random.nextInt(level);
}

至此,我们实现了一个跳表的定义,初始化,查找,节点新增与删除。

加载全部内容

相关教程
猜你喜欢
用户评论