首页 > 技术文章 > 跳表:给链表加索引

ttaall 2020-09-21 17:38 原文

跳表— 在顺序链表的基础上加索引

类似于给书加目录,把一些章节摘出来当目录

 

形式结构:最底层为全部链表 , 每上一层就将其中一部分当作索引

 

 

1. 每个节点保存上一个节点指针,下一个节点指针,上指针(他的索引地址),下指针(他作为索引指向的原节点地址)

2. 头节点尾节点都给无穷(Integer.maxInt)

3. 链表设置一个随机机制 每插入一个节点随机是否上升为索引

 

查找: 每次查找data在链表的位置,不用从头到尾遍历链表   从最高级索引往下遍历逐步确定范围

新增: 先通过索引查找 找到data在链表中应该存的位置,然后插入到链表中,然后判断是否上升索引 

删除: 先找到最高级索引位置,如果有就删除,依次往下进行直到将原链表节点删除

 

推荐阅读