Двусвязный список со списком пропуска для вставки отсортированным способом

Прелесть skiplist в том, что он сортирует элементы данных, а также предлагает временную сложность вставки и удаления o (log n). Чтобы сделать его более понятным, представьте, что в вашем связанном списке есть ярлыки или якоря, так что вам не нужно перемещаться по всему списку, чтобы найти позицию для вставки элемента. Вы просто следуете якорям, поэтому это список с двумя ссылками и якорями быстрого доступа.

Что касается реализации, если вы не собираетесь использовать список пропуска для многопоточного доступа, то реализовать его становится тривиально. Нет причин комбинировать пропускаемый список с двусвязным списком, но вы можете реализовать skiplist как двусвязный список.

Посмотрите на http://www.sanfoundry.com/cpp-program-implement-skip-list/

Я надеюсь, это поможет вам.

#ifndef SkipList_h
#define SkipList_h
///////////////////////////////////////////////////////////////////////////////

template<typename K, typename V, int MAXLEVEL>
class SkipListNode
{

public:
    SkipListNode()
    {
        for(int i=1; i<=MAXLEVEL;i++){
            next[i] = nullptr;
            prev[i] = nullptr;
        }
    }

    SkipListNode(K searchKey):key(searchKey)
    {
        for(int i=1; i<=MAXLEVEL;i++){
            next[i] = nullptr;
            prev[i] = nullptr;
        }
    }

    SkipListNode(K searchKey, V val):key(searchKey),value(val)
    {
        for(int i=1; i<=MAXLEVEL;i++){
            next[i] = nullptr;
            prev[i] = nullptr;
        }
    }

    // custom memory management
   // static void * operator new(size_t size);

  //  static void operator delete( void *deadObject, size_t size );


    K key;
    V value;
    SkipListNode<K, V, MAXLEVEL>* next[MAXLEVEL+1];
    SkipListNode<K, V, MAXLEVEL>* prev[MAXLEVEL+1];
private:
   // static MemoryPool<SkipListNode> memPool; // memory pool for SkipListNode
};

// template<typename K, typename V, int MAXLEVEL>
// MemoryPool< SkipListNode<K, V, MAXLEVEL> > SkipListNode<K, V, MAXLEVEL>::memPool;

// template<typename K, typename V, int MAXLEVEL>
// inline void * SkipListNode<K, V, MAXLEVEL>::operator new ( size_t size )
// {
//     return memPool.allocate();
// }

// template<typename K, typename V, int MAXLEVEL>
// inline void SkipListNode<K, V, MAXLEVEL>::operator delete( void *p, size_t size )
 //{
 //    memPool.deallocate( static_cast<SkipListNode<K, V, MAXLEVEL> *>(p) );
 //}


///////////////////////////////////////////////////////////////////////////////

template<typename K, typename V, int MAXLEVEL = 16>
class SkipList
{
public:
    typedef K keyType;
    typedef V ValueType;
    typedef SkipListNode<K, V, MAXLEVEL> NodeType;
    const int maxLevel;

    SkipList(K min_key, K max_key)
                                :pHeader(nullptr), pTail(nullptr),
                                maxCurrLevel(1), maxLevel(MAXLEVEL),
                                minKey(min_key), maxKey(max_key)
    {
        pHeader = new NodeType(minKey);
        pTail = new NodeType(maxKey);

        for( int i = 1; i<=MAXLEVEL; i++){
            pHeader->next[i] = pTail;
            pTail->prev[i] = pHeader;
        }
    }

    virtual ~SkipList()
    {

        delete pHeader;
        delete pTail;
    }

    void removeAll()
    {
        NodeType* curNode = pHeader->next[1];
        while(curNode != pTail){
            NodeType* temp = curNode;
            curNode = curNode->next[1];
            delete temp;
        }
    }

    std::string printList()
    {
        std::stringstream sstr;
        NodeType* currNode = pHeader->next[1];
        while ( currNode != pTail ) {
            sstr << "(" << currNode->key << "," << currNode->value << ")" << std::endl;
            currNode = currNode->next[1];
        }
        return sstr.str();
    }

    NodeType* insert( K searchKey, V newValue );

    void removeKey( K searchKey );
    void removeKey( NodeType* curNode );

    NodeType* search(const K& key, NodeType** prev   );

private:
    K minKey;
    K maxKey;
    int maxCurrLevel;
    SkipListNode<K, V, MAXLEVEL>* pHeader;
    SkipListNode<K, V, MAXLEVEL>* pTail;

    double uniformRandom()
    {
        return rand() / double(RAND_MAX);
    }

    int randomLevel() {
        int level = 1;
        double p = 0.5;
        while ( uniformRandom() < p && level < MAXLEVEL ) {
            level++;
        }
        return level;
    }
};

template<typename K, typename V, int MAXLEVEL>
typename SkipList<K, V, MAXLEVEL>::NodeType* SkipList<K, V, MAXLEVEL>::search(const K& searchKey, NodeType** prev )
{
    NodeType* currNode = nullptr;

    currNode = pHeader;
    for (int level=maxCurrLevel; level>=1; level--) {
        // Start our search at previous level's predecessor

        while (currNode->next[level]->key < searchKey) {
            currNode = currNode->next[level];

        }
        if ( prev != nullptr) {
            prev[level] = currNode;
        }

        //currNode = currNode->next[level];
        /*
        if ( next != nullptr) {
            next[level] = currNode;
        }*/
    }

    currNode = currNode->next[1];
    return currNode;
}

template<typename K, typename V, int MAXLEVEL>
typename SkipList<K, V, MAXLEVEL>::NodeType*  SkipList<K, V, MAXLEVEL>::insert( K searchKey, V newValue )
{
    SkipListNode<K, V, MAXLEVEL>** next = nullptr;
    SkipListNode<K, V, MAXLEVEL>* prev[MAXLEVEL];

    auto foundNode = search(searchKey, prev);


    int newLevel = randomLevel();
    //std::cout<< "Level: "<<newLevel<< std::endl;

    if ( newLevel > maxCurrLevel ) {
        for ( int level = maxCurrLevel+1; level <= newLevel; level++ ) {
            prev[level] = pHeader;
        }

        maxCurrLevel = newLevel;
    }

    NodeType* curNode = new NodeType(searchKey, newValue);

    for ( int level = 1; level<=maxCurrLevel; level++ ) {
        curNode->next[level] = prev[level]->next[level];
        curNode->prev[level] = prev[level];
        prev[level]->next[level]->prev[level] = curNode;
        prev[level]->next[level] = curNode;
    }
    return curNode;
}

template<typename K, typename V, int MAXLEVEL>
void SkipList<K, V, MAXLEVEL>::removeKey( K searchKey)
{

    SkipListNode<K, V, MAXLEVEL>** prev1 = nullptr;

    auto curNode = search(searchKey, prev1);


    //std::cout<<curNode <<" -> "<< curNode->key<< std::endl;
    if ( curNode && curNode->key == searchKey ) {

        auto prev = curNode->prev;

        for ( int level = 1; level<=maxCurrLevel; level++ ) {

            if ( prev[level]->next[level] != curNode ) {
                break;
            }

            prev[level]->next[level] = curNode->next[level];
            curNode->next[level]->prev[level] = prev[level];
        }

        delete curNode;

        while ( maxCurrLevel > 1 && pHeader->next[maxCurrLevel] == pTail) {
            maxCurrLevel--;
        }

        //std::cout << "maxCurrLevel: "<<maxCurrLevel<<std::endl;
    }

}


template<typename K, typename V, int MAXLEVEL>
void SkipList<K, V, MAXLEVEL>::removeKey( typename SkipList<K, V, MAXLEVEL>::NodeType* curNode )
{
    if ( curNode && curNode == curNode->next[1]->prev[1] && curNode == curNode->prev[1]->next[1] ) {
       // std::cout<<curNode <<" -> "<< curNode->key<< std::endl;

        auto prev = curNode->prev;

        for ( int level = 1; level<=maxCurrLevel; level++ ) {

            if ( prev[level]->next[level] != curNode ) {
                break;
            }

            prev[level]->next[level] = curNode->next[level];
            curNode->next[level]->prev[level] = prev[level];
        }

        delete curNode;

        while ( maxCurrLevel > 1 && pHeader->next[maxCurrLevel] == pTail ) {
            maxCurrLevel--;
        }
    }
}


#endif