链表的二分查找--跳表

前言：链表的二分查找

链表与数组相比，最大的优势在于插入和删除操作的时间复杂度是O(1)，但是查找操作的时间复杂度是O(n)。如果需要频繁进行查找操作，那么链表的时间复杂度就会很高。为了解决这个问题，我们可以使用二分查找的思想来优化链表的查找操作。

这里介绍一种基于链表和二分查找思想的跳表（Skip List）数据结构。跳表是一种随机化的数据结构，它通过在链表上建立多级索引来加速查找操作。跳表的时间复杂度是O(logn)，与平衡树的时间复杂度相当，但是实现起来更简单。

跳表的基本概念

跳表是一种随机化的数据结构，它通过在链表上建立多级索引来加速查找操作。跳表的基本思想是将链表分成多个层次，每一层都是一个有序的链表。在最高层，链表中的元素是全局有序的，而在低层，链表中的元素是有序的，但是排序的范围更小。通过这种方式，我们可以快速定位到目标元素所在的区间，从而加速查找操作。

跳表的实现

1，skipnode节点

struct SkipNode {
    int val;
    struct SkipNode *next;
    struct SkipNode *down;
};

2，skipList类

struct SkipList {
    struct SkipNode *head;
    int level;
};

3，创建跳表节点

struct SkipNode *createSkipNode(int val) {
    struct SkipNode *node = (struct SkipNode *)malloc(sizeof(struct SkipNode));
    node -> val = val;
    node -> next = NULL;
    node -> down = NULL;
    return node;
}

4，创建跳表

struct SkipList *createSkipList() {
    srand(time(NULL)); // 初始化随机数种子
    struct SkipList *list = (struct SkipList *)malloc(sizeof(struct SkipList));
    list -> head = createSkipNode(INT_MIN);
    list -> level = 1;
    return list;
}

5，生成随机层数

这里的MID_COUNT是一个经验值，可以根据实际情况进行调整（在一定数值时最快，一般在10到20之间最快速）。

const int MAX_LEVEL = 64;
const int MID_COUNT = 2; 

int randomLevel() {
    int level = 1;
    while (rand() % MID_COUNT == 0 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

6，插入节点

void insertSkipList(struct SkipList *list, int val) {
    int level = randomLevel();
    if( level > list -> level) {
        for(; list -> level < level; list -> level++){
            struct SkipNode *newNode = createSkipNode(list -> head -> val);
            newNode -> down = list -> head;
            list -> head = newNode;
        }
    } 
    struct SkipNode *update[list -> level];
    struct SkipNode *cur = list -> head;
    for(int i = list -> level - 1; i >= 0; i--) {
        while(cur -> next != NULL && cur -> next -> val < val) {
            cur = cur -> next;
        }
        update[i] = cur;
        cur = cur -> down;
    }
    cur = NULL;
    for(int i = 0; i < level; i++) {
        struct SkipNode *newNode = createSkipNode(val);
        newNode -> next = update[i] -> next;
        update[i] -> next = newNode;
        if(i > 0) {
            newNode -> down = cur;
        }
        cur = newNode;
    }
}

7，查找节点

bool searchSkipList(struct SkipList *list, int val) {
    struct SkipNode *cur = list -> head;
    for(int i = list -> level - 1; i >= 0; i--) {
        while(cur -> next && cur -> next -> val < val) {
            cur = cur -> next;
        }
        if(cur -> next && cur -> next -> val == val) {
            return true;
        }
        cur = cur -> down;
    }
    return false;
}

8，删除节点

void deleteSkipList(struct SkipList *list, int val) {
    struct SkipNode *cur = list -> head;    
    for(int i = list -> level - 1; i >= 0; i--) {
        while(cur -> next && cur -> next -> val < val) {
            cur = cur -> next;
        }
        if(cur -> next && cur -> next -> val == val) {
            struct SkipNode *temp = cur -> next;
            cur -> next = cur -> next -> next;
            free(temp);
        }
        cur = cur -> down;
    }
    cur = list -> head;
    while(cur -> next == NULL && list -> level > 1) {
        struct SkipNode *temp = cur;
        cur = cur -> down;
        free(temp);
        list -> level--;
    }
}

9，打印跳表

void printSkipList(struct SkipList *list) {
    struct SkipNode *cur = list -> head;
    for(int i = list -> level - 1; i > 0; i--) {
        cur = cur -> down;
    }
    for(; cur -> next != NULL; cur = cur -> next) {
        printf("%d ", cur -> next-> val);
    }
    printf("\n");
}

10，释放内存

void freeSkipList(struct SkipList *list) {
    struct SkipNode *cur = list -> head;
    struct SkipNode *temp;
    for(int i = list -> level - 1; i >= 0; i--) {
        temp = cur -> next;
        for(;temp; ) {
            struct SkipNode *temp2 = temp;
            temp = temp -> next;
            free(temp2);
        }
        struct SkipNode *temp3 = cur;
        cur = cur -> down;
        free(temp3);
    }
    free(list);
}