Skip List Implementation in C++

An efficient C++ implementation of a Skip List data structure supporting fast insertion, search, and deletion operations with probabilistic balancing.

A linked list is a fundamental data structure and can be used to implement other common data structures such as a Skip List. It represents a linear collection of data items whose order is not given by their physical placement in memory. While an array keeps a linear set of items in contiguous memory, a Linked List has each item in the list point to the next. The Linked List is a data structure consisting of a collection of nodes (objects) which together represent a sequence.

A Skip List allows faster traversal of a list by compiling several different Linked Lists with varying granularity in terms of the number of nodes. At the base level, all nodes may be visited while at higher levels fewer nodes can be visited before traversing the entire list. This allows traversal at higher levels before moving to lower levels, resulting in increased efficiency.

Objectives

• Use pointers to manage an ordered set of data objects.
• Manually allocate and reclaim memory used by those pointers.
• Understand the complexity of inserting, deleting, and traversing a Linked List.
• Leverage a Linked List to construct a Skip List of ordered items by priority.

Features

• Insert integers into the Skip List
• Search for values
• Remove Values
• Print the structure level by level
• Use probabilistic height assignment (0.5) for balancing
• Max level set to 4

How to Build and Run the Project

Prerequisites

• C++11 or later
• g++ or another compatible C++ compiler

Build

g++ main.cpp SkipList.cpp -o skiplist

Usage

In this example, I'll add a few numbers to the list, display the structure, remove an element, and display the structure again.

SkipList* test1 = new SkipList(); // New object
    test1->insert(25);
    test1->insert(34);
    test1->insert(15);
    test1->insert(26);
    test1->insert(100);
    test1->display();
    test1->remove(25);
    test1->display();

    delete test1; // Free memory

Output:

_______ Skip List _______
Level 2: 15 -> 25 -> nullptr
Level 1: 15 -> 25 -> 26 -> 34 -> 100 -> nullptr

_______ Skip List _______
Level 2: 15 -> nullptr
Level 1: 15 -> 26 -> 34 -> 100 -> nullptr

Project Structure

• main.cpp — entry point and test functions
• SkipList.h — class declarations
• SkipList.cpp — method definitions

License

MIT License. See LICENSE file for details.

Video Demo

YouTube

Author

[Morgan]