data_structure_and_algorithm -- 跳表：python & java & c-cpp 实现

from typing import Optional
import random

class ListNode:

    def __init__(self, data: Optional[int] = None):
        self._data = data
        self._forwards = []   # Forward pointers

class SkipList:

    _MAX_LEVEL = 16

    def __init__(self):
        self._level_count = 1
        self._head = ListNode()
        self._head._forwards = [None] * type(self)._MAX_LEVEL

    def find(self, value: int) -> Optional[ListNode]:
        p = self._head
        for i in range(self._level_count - 1, -1, -1):   # Move down a level
            while p._forwards[i] and p._forwards[i]._data < value:
                p = p._forwards[i]   # Move along level
        
        return p._forwards[0] if p._forwards[0] and p._forwards[0]._data == value else None

    def insert(self, value: int):
        level = self._random_level()
        if self._level_count < level: self._level_count = level
        new_node = ListNode(value)
        new_node._forwards = [None] * level
        update = [self._head] * level     # update is like a list of prevs

        p = self._head
        for i in range(level - 1, -1, -1):
            while p._forwards[i] and p._forwards[i]._data < value:
                p = p._forwards[i]
            
            update[i] = p     # Found a prev

        for i in range(level):
            new_node._forwards[i] = update[i]._forwards[i]   # new_node.next = prev.next
            update[i]._forwards[i] = new_node     # prev.next = new_node
        
    def delete(self, value):
        update = [None] * self._level_count
        p = self._head
        for i in range(self._level_count - 1, -1, -1):
            while p._forwards[i] and p._forwards[i]._data < value:
                p = p._forwards[i]
            update[i] = p
        
        if p._forwards[0] and p._forwards[0]._data == value:
            for i in range(self._level_count - 1, -1, -1):
                if update[i]._forwards[i] and update[i]._forwards[i]._data == value:
                    update[i]._forwards[i] = update[i]._forwards[i]._forwards[i]     # Similar to prev.next = prev.next.next

    def _random_level(self, p: float = 0.5) -> int:
        level = 1
        while random.random() < p and level < type(self)._MAX_LEVEL:
            level += 1
        return level

    def __repr__(self) -> str:
        values = []
        p = self._head
        while p._forwards[0]:
            values.append(str(p._forwards[0]._data))
            p = p._forwards[0]
        return "->".join(values)


if __name__ == "__main__":
    l = SkipList()
    for i in range(10):
        l.insert(i)
    print(l)
    p = l.find(7)
    print(p._data)
    l.delete(3)
    print(l)

package skiplist;

import java.util.Random;

/**
 * 跳表的一种实现方法。
 * 跳表中存储的是正整数，并且存储的是不重复的。
 *
 * Author：ZHENG
 */
public class SkipList {

  private static final int MAX_LEVEL = 16;

  private int levelCount = 1;

  private Node head = new Node();  // 带头链表

  private Random r = new Random();

  public Node find(int value) {
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      return p.forwards[0];
    } else {
      return null;
    }
  }

  public void insert(int value) {
    int level = randomLevel();
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    Node update[] = new Node[level];
    for (int i = 0; i < level; ++i) {
      update[i] = head;
    }

    Node p = head;
    for (int i = level - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;
    }

    for (int i = 0; i < level; ++i) {
      newNode.forwards[i] = update[i].forwards[i];
      update[i].forwards[i] = newNode;
    }

    if (levelCount < level) levelCount = level;
  }

  public void delete(int value) {
    Node[] update = new Node[levelCount];
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      for (int i = levelCount - 1; i >= 0; --i) {
        if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
          update[i].forwards[i] = update[i].forwards[i].forwards[i];
        }
      }
    }
  }

  private int randomLevel() {
    int level = 1;
    for (int i = 1; i < MAX_LEVEL; ++i) {
      if (r.nextInt() % 2 == 1) {
        level++;
      }
    }

    return level;
  }

  public void printAll() {
    Node p = head;
    while (p.forwards[0] != null) {
      System.out.print(p.forwards[0] + " ");
      p = p.forwards[0];
    }
    System.out.println();
  }

  public class Node {
    private int data = -1;
    private Node forwards[] = new Node[MAX_LEVEL];
    private int maxLevel = 0;

    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();
      builder.append("{ data: ");
      builder.append(data);
      builder.append("; levels: ");
      builder.append(maxLevel);
      builder.append(" }");

      return builder.toString();
    }
  }

}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>

// https://www.youtube.com/watch?v=2g9OSRKJuzM&t=17s

#define MAX_LEVEL 15

struct node {
	int val;
	int max_level;
	struct node *forward[MAX_LEVEL];
};

struct skip_list {
	struct node head;
	int max_level;
	int max_level_nodes;
};

void node_init(struct node* node)
{
	memset(node, 0, sizeof(struct node));
}

void skip_list_init(struct skip_list* sl)
{
	node_init(&sl->head);
	sl->max_level = 0;
	sl->max_level_nodes = 0;
}

void random_init()
{
	static bool done = false;

	if (done)
		return;

	srandom(time(NULL));
	done = true;
}

int random_level(void)
{
    int i, level = 1;

    random_init();

    for (i = 1; i < MAX_LEVEL; i++)
	    if (random() % 2 == 1)
		    level++;

    return level;
}

void random_level_test()
{
	printf("random level %d\n", random_level());
	printf("random level %d\n", random_level());
	printf("random level %d\n", random_level());
	printf("random level %d\n", random_level());
	printf("random level %d\n", random_level());
}

void insert(struct skip_list *sl, int val)
{
	int level = random_level();
	struct node *update[MAX_LEVEL];
	struct node *new, *p;
	int i;

	new = (struct node*)malloc(sizeof(struct node));
	if (!new)
		return;

	new->max_level = level;
	new->val = val;

	for (int i = 0; i < MAX_LEVEL; i++)
		update[i] = &sl->head;

	p = &sl->head;
	for (i = level - 1; i >= 0; i--) {
		while(p->forward[i] && p->forward[i]->val < val)
			p = p->forward[i];

		update[i] = p;
	}

	for (i = 0; i < level; i++) {
		new->forward[i] = update[i]->forward[i];
		update[i]->forward[i] = new;
	}

	if (sl->max_level < level) {
		sl->max_level = level;
		sl->max_level_nodes = 1;
	} else if (sl->max_level == level)
		sl->max_level_nodes++;
}

struct node *find(struct skip_list* sl, int val)
{
	struct node *node = &sl->head;
	int i;

	for (i = sl->max_level - 1; i >= 0; i--) {
		while (node->forward[i] && node->forward[i]->val < val)
			node = node->forward[i];
	}

	if (node->forward[0] && node->forward[0]->val == val) {
		return node->forward[0];
	}
	else
		return NULL;
}

void delete(struct skip_list* sl, int val)
{
	struct node *update[MAX_LEVEL];
	struct node *p;
	int i;

	p = &sl->head;

	for (i = sl->max_level; i >= 0; i--) {
		while (p->forward[i] && p->forward[i]->val < val)
			p = p->forward[i];

		update[i] = p;
	}

	if (p->forward[0] == NULL || p->forward[0]->val != val)
		return;

	if (p->forward[0]->max_level == sl->max_level)
		sl->max_level_nodes--;

	for (i = sl->max_level-1; i >= 0; i--) {
		if (update[i]->forward[i] && update[i]->forward[i]->val == val)
			update[i]->forward[i] = update[i]->forward[i]->forward[i]; 
	}

	// fixup max_level and max_level_nodes
	if (sl->max_level_nodes == 0) {
		//sl->max_level--;
		p = &sl->head;
		// skip (max_level - 1), direct test (max_level - 2)
		// since no nodes on (max_level - 1)
		for (i = sl->max_level - 2; i >= 0; i--) {
			while (p->forward[i]) {
				sl->max_level_nodes++;
				p = p->forward[i];
			}

			if (sl->max_level_nodes) {
				sl->max_level = i + 1;
				break;
			} else
				sl->max_level = i;
		}
	}
}


void print_sl(struct skip_list* sl)
{
	struct node *node;
	int level;

	printf("%d level skip list with %d nodes on top\n",
		sl->max_level, sl->max_level_nodes);
	
	for (level = sl->max_level - 1; level >= 0; level--) {
		node = &sl->head;
		printf("Level[%02d]:", level);
		while (node->forward[level]) {
			printf("%4d", node->forward[level]->val);
			node = node->forward[level];
		}
		printf("\n");
	}
}

int main()
{
	struct skip_list sl;
	struct node *node = NULL;
	int i;

	skip_list_init(&sl);
	print_sl(&sl);

	for (i = 0; i < 10; i++)
		insert(&sl, i);
	print_sl(&sl);

	node = find(&sl, 8);
	if (node)
		printf("find 8 in sl %d\n", node->val);
	else
		printf("8 not in sl\n");

	for (i = 0; i < 10; i++) {
		delete(&sl, i);
		print_sl(&sl);
	}

	return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <cstring>
#include <random>
#include <ctime>
using namespace std;

/**
 * 跳表的一种实现方法。
 * 跳表中存储的是正整数，并且存储的是不重复的。
 *
 * 跳表的C++版本.
 * 翻译JAVA版本 原作者 Author：ZHENG
 * 
 * Author：puhuaqiang
 * 
 *  跳表结构:
 * 
 *  第K级           1           9
 *  第K-1级         1     5     9
 *  第K-2级         1  3  5  7  9
 *  ...             ....
 *  第0级(原始链表)  1  2  3  4  5  6  7  8  9
 */

const int MAX_LEVEL = 16;

/**
 * @brief 节点
*/
class CNode
{
public:
    CNode();
    ~CNode();

    std::string toString();
    /**
     * @brief 获取索引链表
    */
    CNode** GetIdxList();

    /**
     * @brief 设置数据
    */
    void SetData(int v);
    /**
     * @brief 获取数据
    */
    int GetData();
    /**
    * @brief 设置最大索引级别
    */
    void SetLevel(int l);
private:
    /**当前节点的值*/
    int m_data;
    /** 
     * 当前节点的每个等级的下一个节点.
     * 第2级 N1 N2
     * 第1级 N1 N2
     * 如果N1是本节点,则 m_lpForwards[x] 保存的是N2
     * 
     * [0] 就是原始链表.
     */
    CNode* m_lpForwards[MAX_LEVEL];
    /**当前节点的所在的最大索引级别*/
    int m_iMaxLevel;
};

/**
 * @brief 跳表
*/
class CSkipList
{
public:
    CSkipList();
    ~CSkipList();
    /**
     * @brief 查找指定的值的节点
     * @param v 正整数
    */
    CNode* Find(int v);
    /**
     * @brief 插入指定的值
     * @param v 正整数
    */
    void Insert(int v);
    /**
     * @brief 删除指定的值的节点
     * @param v 正整数
    */
    int Delete(int v);
    void PrintAll();
    /**
     * @brief 打印跳表结构
     * @param l 等于-1时打印所有级别的结构 >=0时打印指定级别的结构
    */
    void PrintAll(int l);
    /**
     * @brief 插入节点时,得到插入K级的随机函数
     * @return K
    */
    int RandomLevel();

private:
    int levelCount;
    /**
     * 链表
     * 带头/哨所(节点)
    */
    CNode* m_lpHead;
};

int main()
{
    CSkipList skipList;
    /// 插入原始值
    for(int i=1; i< 50; i++){
        if((i%3) == 0){
            skipList.Insert(i);
        }
    }
    for(int i=1; i< 50; i++){
        if((i%3) == 1){
            skipList.Insert(i);
        }
    }
    skipList.PrintAll();
    std::cout<<std::endl;
    /// 打印所有等级结构
    skipList.PrintAll(-1);
    /// 查找
    std::cout<<std::endl;
    CNode* lpNode = skipList.Find(27);
    if(NULL != lpNode){
        std::cout<<"查找值为27的节点,找到该节点,节点值:"<<lpNode->GetData()<<std::endl;
    }else{
        std::cout<<"查找值为27的节点,未找到该节点"<<std::endl;
    }
    /// 删除
    std::cout<<std::endl;
    int ret = skipList.Delete(46);
    if(0 == ret){
        std::cout<<"查找值为46的节点,找到该节点,并删除成功"<<std::endl;
    }else{
        std::cout<<"查找值为46的节点,找到该节点,删除失败"<<std::endl;
    }
    std::cout<<std::endl;
    //打印所有等级结构
    skipList.PrintAll(-1);
    std::cin.ignore();
    return 0;
}

CNode::CNode()
{
    m_data = -1;
    m_iMaxLevel = 0;
    for(int i=0; i<MAX_LEVEL; i++){
        m_lpForwards[i] = NULL;
    }
}
CNode::~CNode()
{

}
CNode** CNode::GetIdxList()
{
    return m_lpForwards;
}

void CNode::SetData(int v)
{
    m_data = v;
}
int CNode::GetData()
{
    return m_data;
}
void CNode::SetLevel(int l)
{
    m_iMaxLevel = l;
}
std::string CNode::toString()
{
    char tmp[32];
    std::string ret;

    ret.append("{ data: ");
    sprintf(tmp, "%d", m_data);
    ret.append(tmp);
    ret.append("; levels: ");
    sprintf(tmp, "%d", m_iMaxLevel);
    ret.append(tmp);
    ret.append(" }");
    return ret;
}

CSkipList::CSkipList()
{
    levelCount = 1;
    m_lpHead = new CNode();
}
CSkipList::~CSkipList()
{

}
CNode* CSkipList::Find(int v)
{
    CNode* lpNode = m_lpHead;
    /**
     * 从 最大级索引链表开始查找.
     * K -> k-1 -> k-2 ...->0
    */
    for(int i=levelCount-1; i>=0; --i){
        /**
         * 查找小于v的节点(lpNode).
        */
        while((NULL != lpNode->GetIdxList()[i]) && (lpNode->GetIdxList()[i]->GetData() < v)){
            lpNode = lpNode->GetIdxList()[i];
        }
    }
    /**
     * lpNode 是小于v的节点, lpNode的下一个节点就等于或大于v的节点
    */
    if((NULL != lpNode->GetIdxList()[0]) && (lpNode->GetIdxList()[0]->GetData() == v)){
        return lpNode->GetIdxList()[0];
    }
    return NULL;
}
void CSkipList::Insert(int v)
{
    /// 新节点
    CNode* lpNewNode = new CNode();
    if(NULL == lpNewNode){
        return;
    }

    /**
     * 新节点最大分布在的索引链表的上限
     * 如果返回 3,则 新的节点会在索引1、2、3上的链表都存在
    */
    int level = RandomLevel();
    lpNewNode->SetData(v);
    lpNewNode->SetLevel(level);

    /**
     * 临时索引链表
     * 主要是得到新的节点在每个索引链表上的位置
    */
    CNode *lpUpdateNode[level];
    for(int i=0; i<level; i++){
        /// 每个索引链表的头节点
        lpUpdateNode[i] =m_lpHead;
    }
    CNode* lpFind = m_lpHead;
    for(int i= level-1; i >= 0; --i){
        /**
         * 查找位置
         *   eg.  第1级  1  7  10
         *   如果插入的是 6
         *   lpFind->GetIdxList()[i]->GetData() : 表示节点lpFind在第1级索引的下一个节点的数据
         *   当 "lpFind->GetIdxList()[i]->GetData() < v"不成立的时候,
         *   新节点就要插入到 lpFind节点的后面, lpFind->GetIdxList()[i] 节点的前面
         *   即在这里 lpFind就是1  lpFind->GetIdxList()[i] 就是7
        */
        while((NULL != lpFind->GetIdxList()[i]) && (lpFind->GetIdxList()[i]->GetData() < v)){
            lpFind = lpFind->GetIdxList()[i];
        }
        /// lpFind 是新节点在 第i级索引链表的后一个节点
        lpUpdateNode[i] = lpFind;
    }

    for(int i=0; i<level; ++i){
        /**
         * 重新设置链表指针位置
         *   eg  第1级索引 1  7  10
         *      插入6.
         *      lpUpdateNode[i] 节点是1; lpUpdateNode[i]->GetIdxList()[i]节点是7
         *  
         *  这2句代码就是 把6放在 1和7之间
        */
        lpNewNode->GetIdxList()[i] = lpUpdateNode[i]->GetIdxList()[i];
        lpUpdateNode[i]->GetIdxList()[i] = lpNewNode;
    }
    if(levelCount < level){
        levelCount = level;
    }
}
int CSkipList::Delete(int v)
{
    int ret = -1;
    CNode *lpUpdateNode[levelCount];
    CNode *lpFind = m_lpHead;
    for(int i=levelCount-1; i>= 0; --i){
        /**
         * 查找小于v的节点(lpFind).
        */
        while((NULL != lpFind->GetIdxList()[i]) && (lpFind->GetIdxList()[i]->GetData() < v)){
            lpFind = lpFind->GetIdxList()[i];
        }
        lpUpdateNode[i] = lpFind;
    }
    /**
     * lpFind 是小于v的节点, lpFind的下一个节点就等于或大于v的节点
    */
    if((NULL != lpFind->GetIdxList()[0]) && (lpFind->GetIdxList()[0]->GetData() == v)){
        for(int i=levelCount-1; i>=0; --i){
            if((NULL != lpUpdateNode[i]->GetIdxList()[i]) && (v == lpUpdateNode[i]->GetIdxList()[i]->GetData())){
                lpUpdateNode[i]->GetIdxList()[i] = lpUpdateNode[i]->GetIdxList()[i]->GetIdxList()[i];
                ret = 0;
            }
        }
    }
    return ret;
}
void CSkipList::PrintAll()
{
    CNode* lpNode = m_lpHead;
    while(NULL != lpNode->GetIdxList()[0]){
        std::cout<<lpNode->GetIdxList()[0]->toString().data()<<std::endl;
        lpNode = lpNode->GetIdxList()[0];
    }
}
void CSkipList::PrintAll(int l)
{
    for(int i=MAX_LEVEL-1; i>=0;--i){
        CNode* lpNode = m_lpHead;
        std::cout<<"第"<<i<<"级:"<<std::endl;
        if((l < 0) || ((l >= 0) && (l == i))){
            while(NULL != lpNode->GetIdxList()[i]){
                std::cout<<lpNode->GetIdxList()[i]->GetData()<<" ";
                lpNode = lpNode->GetIdxList()[i];
            }
            std::cout<<std::endl;
            if(l >= 0){
                break;
            }
        }
    }
}
int GetRandom()
{
    static int _count = 1;
	std::default_random_engine generator(time(0) + _count);
	std::uniform_int_distribution<int> distribution(1,99999/*0x7FFFFFFF*/);
	int dice_roll = distribution(generator);
    _count += 100;
	return dice_roll;
}
int CSkipList::RandomLevel()
{
    int level = 1;
    for(int i=1; i<MAX_LEVEL; ++i){
        if(1 == (GetRandom()%3)){
            level++;
        }
    }
    return level;
}