1
\$\begingroup\$

I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!

Problem

Design a Skiplist without using any built-in libraries.

A Skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists are just simple linked lists.

For example: we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:

enter image description here

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add , erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).

To be specific, your design should include these functions:

  • bool search(int target): Return whether the target exists in the Skiplist or not.
  • void add(int num): Insert a value into the SkipList.
  • bool erase(int num): Remove a value in the Skiplist. If num does not exist in the Skiplist, do nothing and return false. If there exists multiple num values, removing any one of them is fine.

See more about Skiplist: https://en.wikipedia.org/wiki/Skip_list

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

Example:

Skiplist skiplist = new Skiplist();

skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // return false.
skiplist.add(4);
skiplist.search(1);   // return true.
skiplist.erase(0);    // return false, 0 is not in skiplist.
skiplist.erase(1);    // return true.
skiplist.search(1);   // return false, 1 has already been erased.

Constraints:

  • 0 <= num, target <= 20000
  • At most 50000 calls will be made to search, add, and erase.

Code

// The following block might trivially improve the exec time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return 0;
}();


// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <cstdlib>
#include <ctime>
#include <vector>

static const struct Skiplist {
    using SizeType = std::int_fast16_t;
    struct Node {
        SizeType val;
        Node* next{nullptr};
        Node* prev{nullptr};
        Node* down{nullptr};
        Node(SizeType val = 0) {
            this->val = val;
        }
    };

    Node* heads{nullptr};
    SizeType layers = 0;

    Skiplist() {
        std::srand(std::time(nullptr));
    }

    const bool search(const SizeType target) {
        if (heads == nullptr) {
            return false;
        }

        auto ptr = heads;

        while (ptr) {
            while (ptr->next && ptr->next->val < target) {
                ptr = ptr->next;
            }

            if (ptr->next && ptr->next->val == target) {
                return true;
            }

            ptr = ptr->down;
        }

        return false;
    }

    const void add(const SizeType num) {
        Node* ptr = heads;
        std::vector<Node*> path(layers, nullptr);

        for (SizeType layer = layers - 1; layer >= 0; --layer) {
            while (ptr->next && ptr->next->val < num) {
                ptr = ptr->next;
            }

            path[layer] = ptr;
            ptr = ptr->down;
        }

        for (SizeType layer = 0; layer <= std::size(path); ++layer) {
            ptr = new Node(num);

            if (layer == std::size(path)) {
                Node* last = heads;
                heads = new Node();
                heads->down = last;
                heads->next = ptr;
                ptr->prev = heads;
                ++layers;

            } else {
                ptr->next = path[layer]->next;
                ptr->prev = path[layer];
                path[layer]->next = ptr;

                if (ptr->next) {
                    ptr->next->prev = ptr;
                }
            }

            if (layer) {
                ptr->down = path[layer - 1]->next;
            }

            if (std::rand() & 1) {
                break;
            }
        }
    }

    const bool erase(const SizeType num) {
        auto ptr = heads;

        for (SizeType layer = layers - 1; layer >= 0; --layer) {
            while (ptr->next && ptr->next->val < num) {
                ptr = ptr->next;
            }

            if (ptr->next && ptr->next->val == num) {
                ptr = ptr->next;

                while (ptr) {
                    ptr->prev->next = ptr->next;

                    if (ptr->next) {
                        ptr->next->prev = ptr->prev;
                    }

                    ptr = ptr->down;
                }

                while (heads && heads->next == nullptr) {
                    heads = heads->down;
                    --layers;
                }

                return true;

            } else {
                ptr = ptr->down;

                if (ptr == nullptr) {
                    return false;
                }
            }
        }

        return false;
    }
};

LeetCode 1206 - Skip List Problem

References

\$\endgroup\$
1
\$\begingroup\$
  • SizeType looks like a misnomer. It feels more like ValueType. As a side note, consider making it a template <typename ValueType> struct SkipList.

  • Testing for heads == nullptr in search is redundant. The loop will take care of it immediately.

  • For DRY I recommend a helper method, akin to std::lower_bound, to be used in all interface methods (i.e. search, add, and erase). Yes it requires a very careful design of an iterator.

  • add may benefit from Node::Node(val, next, down) constructor.

  • No naked loops, please.

    The for (SizeType layer = 0; layer <= std::size(path); ++layer) loop particularly deserves to be a method on its own. Its intention is to promote a freshly inserted node, so promote_added_node looks like a good name.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.