面试被问「跳跃表」虐了？数据结构与算法中的跳跃表很难吗？

本文先介绍基本的两种数据存储结构，并着重介绍了其中的链表以及在这两种数据结构基础上优化所提出新的数据结构——跳跃表。内容和代码部分参考于跳跃表。

前言

对于一组有序的整型数据，首先能想到相对简单的数据结构就是数组与链表结构。下面就从对有序数据的基础操作进行讲解。

数组

数组是最常见的存储有序数据的集合，从以下操作进行分析。

• 查找

对数组进行二分法查找可以将时间复杂度为O(logn)。

• 插入，删除

在二分法的基础上，查找到目标位置用时O(logn)，而进行插入和删除操作耗时O(n)（因为插入或者删除后，需要将目标位置后的元素后移，耗时O(n)，总耗时即为O(n+lgn)=>O(n)）。

• 缺点

二分法查找将时间复杂度降到O(logn)但是数组是定长的，即使达到一定程度可以进行扩容操作，时间上花费的时间也很大。

链表

链表数据结构是以节点存储数据的一种链式结构，同样从以下操作进行分析。

• 查找

在链表中进行查询操作只能一个节点一个节点访问，因此时间复杂度为O(n)。

• 插入，删除

查找到目标位置后，插入和删除操作的时间复杂度仅有O(1)，但是查找操作耗时O(n) 因此总操作耗时O(n)。

• 优缺点

链表的缺点很明显，不像数组，查找操作必须一个节点一个节点去访问，同时影响了插入、删除操作。
优点也很明显则是需要一个节点时就会申请一个节点的空间，不会造成空间的浪费，并且不考虑查找过程，插入和删除的的时间复杂度为O(1)。

代码实现（Java+GO）

Java版本

class Node<T>{
    public T val;
    public Node<T> next;

    Node(){
        this.val = null;
        this.next = null;
    }

    Node(T val){
        this.val = val;
        this.next = null;
    }
}//节点结构体

public class myList<T>{
    private Node<T> Head;
    private int length;

    myList(){
        this.Head = new Node();
        this.length = 0;
    }

    myList(T val){
        this.Head = new Node(val);
        this.length = 1;
    }

    public Node<T> getHead(){
        return this.Head;
    }

    public void addAtTail(T data){
        Node<T> tmpNode=new Node(data);
        Node<T> point = this.Head;
        if (this.length == 0) {
            point.val = tmpNode.val;
            this.length++;
            System.out.printf("%d",point.val);
        }else{
            Node<T> prePoint = point;
            point = point.next;
            while(point!=null){
                prePoint = point;
                point = point.next;
            }
            prePoint.next = tmpNode;
            System.out.printf("->%d",prePoint.next.val);
            this.length++;
        }
    }//尾插操作

    public void addAtHead(T data){
        Node<T>tmpNode = new Node(data);
        if (this.length == 0){
            this.Head.val = tmpNode.val;
            this.length++;
        }else{
            tmpNode.next=this.Head;
            this.Head = tmpNode;
            this.length++;
        }
    }//头插操作

    public void addAtIndex(int index, T data){
        Node<T>tmpNode = new Node(data);
        Node<T>point   = this.Head;
        if(index==0){//头结点
            tmpNode.next = this.Head;
            this.Head = tmpNode;
            this.length++;
        }else {
            int count = 0;
            Node<T>prePoint = point;
            point = point.next;
            while(count<index-1){
                prePoint = point;
                point = point.next;
                count++;
            }
            prePoint.next = tmpNode;
            tmpNode.next = point;
        }
    }//位置插入

    public void delete(int index){
        if(index==0) {
            this.Head = this.Head.next;
            this.length--;
            return;
        }
        Node<T> prePoint = this.Head;
        Node<T> point = this.Head;
        for(int i=0;i<index;i++) {
            point = prePoint.next;
            if(i==index-1){
                prePoint.next = point.next;
                this.length--;
            }
            prePoint = prePoint.next;
        }
    }//删除某位置处节点

    public int search(T val){
        int index = 0;
        Node<T> point = this.Head;
        while(point!=null) {
            if(point.val == val)return index;
            point = point.next;
            index++;
        }
        return -1;
    }//查找某个值

    public T get(int index) {
        Node<T> point = this.Head;
        for(int i=0;i<index;i++) {
            point = point.next;
        }
        return point.val;
    }//获取第i个节点的位置

    public int getLength() {
        return this.length;
    }//获取第i个节点的位置

    public boolean isEmpty(){
        return this.length==0;
    }//判空

    public static<T> void printList(myList<T> list) {
        System.out.println("\nList Data:");
        Node<T>point = list.getHead();
        System.out.printf("%d",point.val);
        point = point.next;
        while(point!=null){
            System.out.printf("->%d",point.val);
            point = point.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        myList<Integer> list = new myList();
        System.out.printf("Now list is Empty? %s \n",list.isEmpty());
        int[] a = new int[]{1,2,3,4,5,6,7,8,9};
        for (int num:a){
            list.addAtTail(num);
        }
        //list.addAtIndex(2,1);
        printList(list);
        System.out.printf("Now list is Empty? %s \n",list.isEmpty());
        System.out.printf("the data in the index 2 of list is %d \n",list.get(2));
        System.out.printf("the length of list is %d \n",list.getLength());
        System.out.printf("search 3 in the list,index is %d \n",list.search(3));
        list.delete(list.search(2));
        System.out.println("After deleting data:2..........");
        printList(list);
        System.out.printf("the length of list is %d \n",list.getLength());
        System.out.printf("search 3 in the list,index is %d \n",list.search(3));
    }
}

Go版本

package main

import (
    "fmt"
)

//节点结构
type Node struct {
    Data interface{}
    Next *Node
}

//链表结构
type List struct {
    Head *Node
    Length int
}

//方法接口
type Method interface {
    addAtIndex(i int,data interface{})//在特定位置插入数据
    addAtTail(data interface{})//尾插
    addAtHead(data interface{})//头插
    get(index int)interface{}//获得index的节点数据
    search(data interface{}) int
    delete(i int)
    getLength() int
    isEmpty() bool
}

//创建节点
func createNode(data interface{})*Node{
    return &Node{data,nil}
}
//创建链表
func createList() *List{
    return &List{createNode(nil),0}
}

//从头部插入节点
func(list *List)addAtIndex(i int,data interface{}){
    tmpNode:=createNode(data)
    point := list.Head
    if i==0{//头结点
        tmpNode.Next = list.Head
        list.Head = tmpNode
        list.Length++
    }else {
        count:=0
        prePoint := point
        point = point.Next
        for count<i-1 {
            prePoint = point
            point = point.Next
            count++
        }

        prePoint.Next = tmpNode
        tmpNode.Next = point
    }

}

//从尾部插入节点
func(list *List)addAtTail(data interface{}){
    tmpNode:=createNode(data)
    point := list.Head
    if list.Length == 0 {
        point.Data = tmpNode.Data
        list.Length++
        fmt.Printf("%d",point.Data)
    }else{
        prePoint := point
        point = point.Next
        for point!=nil {
            prePoint = point
            point = point.Next
        }
        prePoint.Next = tmpNode
        fmt.Printf("->%d",prePoint.Next.Data)
        list.Length++
    }
}

//从头部插入节点
func(list *List)addAtHead(data interface{}){
    tmpNode:=createNode(data)
    if list.Length == 0 {
        list.Head.Data = tmpNode.Data
        list.Length++
    }else{
        tmpNode.Next=list.Head
        list.Head = tmpNode
        list.Length++
    }

}

//获取i节点
func(list *List)get(i int) interface{}{
    point := list.Head
    for index:=0;index<i;index++{
        point = point.Next
    }
    return point.Data

}

//找寻节点,如果没
func(list *List)search(data interface{}) int{
     point := list.Head
     index:=0
     for point!=nil{
        if point.Data == data{
            return index
        }
        index++
        point = point.Next
     }
     return -1
}

//删除第i处节点
func(list *List)delete(i int){
    if i==0{//头结点
        list.Head = list.Head.Next
        list.Length--
        return
    }
    prePoint := list.Head
    for count:=0;count<=i-1;count++{
        point := prePoint.Next
        if count==i-1{
            prePoint.Next = point.Next
            list.Length--
        }
        prePoint = prePoint.Next
    }
}

//获取链表长度
func(list *List)getLength()int{
    return list.Length
}

//链表判空
func(list *List)isEmpty()bool{
    point := list.Head
    if(point.Data==nil){
        return true
    }else{
        return false
    }
}

func printList(list *List){
    fmt.Println("\nList Data:")
    point := list.Head
    fmt.Printf("%d",point.Data)
    point = point.Next
    for point!=nil{
        fmt.Printf("->%d",point.Data)
        point = point.Next
    }
    fmt.Println()
}

func main(){
    list := createList()
    fmt.Printf("Now list is Empty? %t \n",list.isEmpty())
    a :=[]int{1,2,3,4,5,6,7,8,9}
    for _,num := range a{
        list.addAtTail(num)
    }
    list.addAtIndex(2,1)
    printList(list)
    fmt.Printf("Now list is Empty? %t \n",list.isEmpty())
    fmt.Printf("the data in the index 2 of list is %d \n",list.get(2))
    fmt.Printf("the length of list is %d \n",list.getLength())
    fmt.Printf("search 3 in the list,index is %d \n",list.search(3))
    list.delete(list.search(2))
    fmt.Printf("After deleting data:2..........")
    printList(list)
    fmt.Printf("the length of list is %d \n",list.getLength())
    fmt.Printf("search 3 in the list,index is %d \n",list.search(3))

}

跳跃表

在考虑链表优点的基础上，同时又考虑着数组在查找、插入和删除的优点上，即基于提高基础操作的速度，设计出了跳跃表这一数据结构。

• 查找

以如下链表为例：

查找元素8，正常的单链表需要遍历八个节点才能找到元素8，由于元素是有序的，那么可以考虑从基础链表中抽取一部分节点，增加链表路径来加快查找速度。如每隔一个节点增加新的链路。

如上图，建立双层链表，当查找元素8，从第二层开始，结合原有链表则只需要按照上图红色路径访问五个节点找寻到元素8。

面试被问「跳跃表」虐了？数据结构与算法中的跳跃表很难吗？

建立三层链表，当查找元素8，从第三层开始，结合原有链表则只需要按照上图红色路径访问访问四个节点找寻到元素8

建立四层，则查找元素8似乎没有帮助，但是如果查找元素9则只访问两个节点即可查询到该元素。

这种基于每层相对于上一层隔一个节点建立新的链路的方法，就类似于数组的二分查找法。最后能达到O(logn)的耗时。

• 插入

说完查找过程，接下来就是插入的操作，与链表插入相同又有些不同，相同的地方是与链表插入相同，每一层如果需要插入操作花费时间只 需要O(1)，不同的是，可能有多个链路需要进行插入操作。

那么，插入的节点要跨越多少层或者说插入到那些链路路径中？

抛硬币策略：通过抛硬币来决定新节点要插入的层——每次插入节点前抛硬币，正面则继续抛硬币，直到出现负面停止，出现正面的次数作为节点跨越的层数。

以下图链表为例：当要插入3,4元素时，依据抛硬币策略，得到3=>0,4=>2。

3=>0意味着跨越0层，即在原始链表路径添加3。

4=>2意味着跨越2层，即在原始链表、第一层、第二层路径添加4。如下图所示

面试被问「跳跃表」虐了？数据结构与算法中的跳跃表很难吗？

• 删除

删除操作则在含有要删除元素的链路层删除要删除的元素。

如删除4，原来每层含有4的将4全部删除。

结论

1. 跳跃表每层均是有序链表，最底层的链表为初始单链表。
2. 结合了数组和链表的特点，查找、插入、删除时间复杂度为O(logn)。
3. 跳跃表的层数与抛硬币策略有关，是一种随机化数据结构，每次运行结果都有所不同。

代码实现（Java+Go）

Java版本

class skipNode{
    int val = -1;
    skipNode[] next;//数组形式的下一个节点
    int layer;//跨越的层数
    public skipNode(int val,int layer){
        this.val = val;
        this.layer=layer;
        this.next = new skipNode[layer];
    }
}//节点结构体

public class SkipList {
    //最大层数
    public int maxLayer = 16;
    //头结点，不使用，辅助节点
    public skipNode head = new skipNode(-1,maxLayer);
    //跳跃表节点总个数
    public int skipListSize = 0;
    //最初跳跃层为原始链表
    public int layerCount = 1;

    //查找过程
    public skipNode search(int val) {
        skipNode point = this.head;
        for(int i = layerCount-1;i>=0;i--) {//从跳跃层
            while(point.next[i]!=null && point.next[i].val<val) {
                point = point.next[i];
            }
        }
        //判断元素存在与否
        if(point.next[0]!=null && point.next[0].val==val) {
            System.out.println(val+"查找成功");
            return point.next[0];
        }else {
            return null;
        }
    }
    public int tossCoins(){
        int layer = 1;
        while(true) {
            int t = (int)(Math.random()*10);
            if(t %2 == 0)layer++;
            else break;
        }
        System.out.println("该链表的跳跃表层数为："+layer);
        return layer;
    }//抛硬币策略
    public void add(int val) {
        int layer = tossCoins();//获得跨越层
        while(layer>this.layerCount*2.5){
            layer = tossCoins();//获得跨越层
        }
        skipNode point = new skipNode(val,layer);
        //记录需要插入节点前的节点位置
        skipNode[] prePoint = new skipNode[layer];
        skipNode tmp = this.head;
        int i;

        for(i=layer-1;i>=0;i--) {
            while(tmp.next[i]!=null&&tmp.next[i].val<val) {
                tmp = tmp.next[i];
            }
            prePoint[i]=tmp;
        }

        //插入
        for(i=0;i<layer;i++) {
            point.next[i] = prePoint[i].next[i];
            prePoint[i].next[i] = point;
        }

        if(layer> this.layerCount) {
            this.layerCount = layer;
        }
        this.skipListSize++;
        System.out.println(val+" 插入成功");
    }

    public void delete(int val) {
        skipNode[] prePoint = new skipNode[this.layerCount];
        skipNode point = this.head;
        int i=0;
        for(i=this.layerCount-1;i>=0;i--) {
            while(point.next[i]!=null && point.next[i].val<val) {
                point = point.next[i];
            }
            prePoint[i] = point;
        }
        if(point.next[0]!=null&&point.next[0].val == val) {
            this.skipListSize--;
            System.out.println(val+" 删除成功");
            for(i=this.layerCount-1;i>=0;i--) {
                if(prePoint[i].next[i]!=null && prePoint[i].next[i].val==val) {
                    prePoint[i].next[i] = prePoint[i].next[i].next[i];
                }
            }
        }
    }

    public static void printSkipList(SkipList list) {
        for(int i = list.layerCount-1;i>=0;i--) {
            skipNode point = list.head;
            while(point.next[i]!=null){
                System.out.print(point.next[i].val+"    ");
                point = point.next[i];
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        SkipList list = new SkipList();
        for(int i=0;i<6;i++) {
            list.add(i);
        }
        printSkipList(list);
        list.delete(4);
        printSkipList(list);
        System.out.println(list.search(3));
        System.out.printf("%d  %d",list.skipListSize,list.layerCount);
    }

}

Go版本

package main

import (
    "fmt"
    "math/rand"
    "time"
)

const MAX_LAYER  =  16
//节点结构
type skipNode struct {
    val     int
    layer   int
    Next    []*skipNode
}

//链表结构
type skipList struct {
    Head            *skipNode
    skipListSize    int
    maxLayer        int
    layerCount      int
}

//接口方法
type method interface {
    add(val int)                //增
    search(val int) *skipNode   //找
    delete(val int)             //删

}

//创建节点
func createSkipNode(val int,layer int) *skipNode{

    return &skipNode{
        val,
        layer,
        make([]*skipNode,layer),
    }
}

//创建跳跃表
func createSkipList()*skipList{
    head :=createSkipNode(-1,MAX_LAYER)
    return &skipList{
        Head:         head,
        skipListSize: 0,
        maxLayer:     MAX_LAYER,
        layerCount:   1,
    }
}

//抛硬币策略
func tossCoins() int{
    layer:=1
    for true{
        rand.Seed(time.Now().UnixNano())//随机数种子
        t := rand.Intn(10)
        if t%2==0{
            layer++
        }else{
            break
        }
    }
    fmt.Printf("该链表节点的跳跃表层数为：%d \n",layer)
    return layer
}

//查找
func(list *skipList)search(val int) *skipNode{
    point:=list.Head
    for i:=list.layerCount-1;i>=0;i--{
        for point.Next[i] !=nil && point.Next[i].val<val{
            point = point.Next[i]
        }
    }

    if point.Next[0]!=nil && point.Next[0].val == val{
        fmt.Printf("\n %d 查找成功 \n",val)
        return point.Next[0]
    }else {
        return nil
    }

}

//增
func(list *skipList)add(val int){
    layer := tossCoins()
    point := createSkipNode(val,layer)
    prePoint := [MAX_LAYER]*skipNode{}
    tmp := list.Head

    for i:=layer-1;i>=0;i--{
        for tmp.Next[i] !=nil && tmp.Next[i].val<val {
            tmp = tmp.Next[i]
        }
        prePoint[i] = tmp
    }
    //插入
    for i:=0;i<layer;i++{
        point.Next[i] = prePoint[i].Next[i]
        prePoint[i].Next[i] = point
    }

    if layer>list.layerCount{
        list.layerCount = layer
    }
    list.skipListSize++
    fmt.Printf("%d 插入成功\n",val)
}

//删
func(list *skipList)delete(val int){
    prePoint := make([]*skipNode,list.layerCount)
    point := list.Head

    for i:=list.layerCount-1;i>=0;i--{
        for point.Next[i] !=nil && point.Next[i].val<val{
            point = point.Next[i]
        }
        prePoint[i] = point
    }
    if point.Next[0] !=nil && point.Next[0].val==val{
        list.skipListSize--
        fmt.Printf("%d 删除成功 \n",val)
        for i:=list.layerCount-1;i>=0;i--{
            if prePoint[i].Next[i]!=nil && prePoint[i].Next[i].val==val{
                prePoint[i].Next[i]=prePoint[i].Next[i].Next[i]
            }
        }
    }
}

//输出跳跃表
func printSkipList(list *skipList){

    for i:=list.layerCount-1;i>=0;i--{
        point := list.Head
        for point.Next[i]!=nil{
            fmt.Printf("%d    ",point.Next[i].val)
            point = point.Next[i]
        }
        fmt.Println()
    }
}

func main(){
    list:= createSkipList()
    for i:=0;i<6;i++{
        list.add(i)
    }
    printSkipList(list)
    list.delete(0)
    printSkipList(list)
    list.search(3)
    fmt.Printf("%d  %d\n",list.skipListSize,list.layerCount)
}

作者：涓涓清泉
链接：https://juejin.cn/post/6919408749169868813
来源：掘金