Definitions

Knowing that a linked list is a series of nodes that contain data and pointers to other nodes, a doubly-linked list not only has a pointer to the node after itself, but it also has a pointer to the node before itself.

A skip list is a doubly-linked list with multiple levels. Each of these levels are entire linked-lists unto themselves.

For our purposes, the number of nodes per level will differ. As you move up one level, the quantity reduces by half:

Specification

The purpose of this program is to utilize the structure of a linked-list with the search performance of an array. Being light-weight and able to retrieve searched entries quickly, arrays seem to have an advantage at first glance, but they are inefficient when it comes to inserting and removing elements. Linked-lists can perform insertions and removals with ease, however they require more time and memory.

The levels in the skip-list offer the possibility of better search time efficiency while offering the ease of insertion and removal at any point in the list. Starting from the highest level, if the searched entry is retrieved, we are able to save time due to having less elements at the upper levels (we are able to skip numbers to reach the target quicker). If however, the searched entry is only in the lowest level and at the very beginning, we risk the possibility of increased search time by a minuscule amount. Overall, however, we can safely conclude that skip-lists offer better search performance over a regular linked-list.

Input

In terms of input validity, only one positive integer as a single argument within the constructor is allowed.

If no arguments are entered, the constructor will initialize the maximum number of levels to 1.

0, negative integers, doubles, characters, strings, etc are not valid input. This integer will represent the maximum number of levels in the skip list. 

The input for values added to the list will be based on a random number generator. Only a single integer per insertion is valid.

The random number generator will also be used as a "coin-toss" measure, giving the value a 50% chance of being added to the next level up. The coin-toss will continue until the value reaches the highest level or falls in the 50% chance of not being added. 

A loop will also be used as input to demonstrate the accuracy of the coin toss over a series of added integers.

Duplicate values entered will be ignored.

Output

Using cout, a printout of the highest (Level n - 1) to lowest (Level 0) and the value entered or "empty" at each level will be shown. Each time a new number is added, the list will keep track of all previous entries. 

A brief example showing two numbers entered on a skip list with 4 levels:

After adding 5
Level: 3 -- empty
Level: 2 -- empty
Level: 1 -- empty
Level: 0 -- 5

After adding 79
Level: 3 -- empty
Level: 2 -- empty
Level: 1 -- 79
Level: 0 -- 5, 79

Error Handling

Although we expect the input to be in the form of integers, if a non-integer is used as an input, an error message prompting the user to only type an integer can be displayed.

Design

This program is composed of a SkipList::SkipListNode struct and a SkipList class

SkipList::SkipListNode

This struct is a private member, contained within the SkipList class that holds five data members.

Data members:

+data_: int

Stores information based on the what the list is for (for example: a list of ages, ID's, transactions, etc)

+next_: SkipListNode*

Pointer to the next node; contains the address of the next node (if exists, otherwise set to nullptr)

+prev_: SkipListNode*

Pointer to the previous node; contains the address of the previous node (if exists, otherwise set to nullptr)

+upLevel_: SkipListNode*

Pointer to the node above the current; contains the address of the node above current (if exists, otherwise set to nullptr). The data value of the node above will be exactly the same as the current.

+downLevel_: SkipListNode*

Pointer to the node below the current; contains the address of the node below current (if exists, otherwise set to nullptr). The data value of the node below will be exactly the same as the current.

The method is described below in UML notation for accessibility:

+explicit Constructor

+explicit SkipListNode(int data);

Single constructor that will allow the passage of a value to set the "data_" data member while initializing all pointers to nullptr.

Skiplist

This class houses and manages all of the nodes in the list. It also contains methods that allow the user to add, remove, or find data in the list.

Data members:

-maxLevels_: int

Determines the number of levels in SkipList; starting with Level 0 to Level (n - 1)

-heads_: SkipListNode**

A dynamically allocated array of pointers; includes all head pointers of each list; the number of elements will be determined by the constructor

-tails_: SkipListNode**

A dynamically allocated array of pointers; includes all tail pointers of each list; the number of elements will be determined by the constructor

The methods are described below in UML notation for accessibility:

explicit Constructor

+explicit SkipList(int maxLevels = 1);

Initializes an empty SkipList while setting maxLevels to 1 by default. Allows the default to be overwritten when passing an integer as an argument.

Destructor

+~SkipList( );

Responsible for cleaning out all the data and making sure all nodes are completely deallocated. Iterates through and remove all nodes.

-addBefore(newNode: SkipListNode*, nextNode: SkipListnode*, level: int): void

Utility function that assists with insertion; when given a pointer to a SkipListNode, place it before the given nextNode at every level.

-alsoHigher( ): bool

Returns true 50% of the time, assists in determining whether a node is added one step higher. The logic is based on "coin toss", where a random number generator decides the outcome. If a node has been added to the highest level, alsoHigher( ) will return false.

+insert(item: int): bool

Returns true if the node is successfully added to the list; no duplicates are allowed

Algorithm for insertion:

1. A vector is setup to hold references to the node before insertion at each level
2. A temporary pointer points to the highest level
3. A special case will apply to any empty lists (head pointer's next_ value is null)
4. Walk down the list until before any integer higher than the target or end of list, but if value is present, return false 
5. Add the reference to the node before any integer higher than the target to the vector
6. Go down to the next level after added to the vector
7. Repeat steps 4 - 7 until Level 0
8. Create and insert the new node
9. Check if alsoHigher is true and the highest level isn't reached
10. If true, move up one step higher and create a new node
11. Pass vector element pointers and the new node pointer to addBefore to finish the insertion at a higher level
12. Repeat steps 9 - 11 until alsoHigher is false or the highest level is reached

+erase(item: int): bool

Returns true if the node is successfully removed from the list

Algorithm for erasure:

1. A temporary pointer points to the highest level
2. Walk down the list until before any integer higher than the target or end of list, but if value is present, stop at the target value
3. Move down from the node before any integer higher than the target or Remove the node if present
4. Deallocate any upLevel_ pointers to deleted nodes
5. Repeat steps 3 & 4 until all instances of the target node are removed

+contains(item: int): bool

Returns true if the value is found in the list

Algorithm to find in list:

1. A temporary pointer points to the highest level
2. Walk down the list until before any integer higher than the target or end of list, but if value is present, return true
3. Return false if all levels have been traversed and no instances of the target value is found

Friend operator

operator<<(os: ostream& , list: SkipList&) : ostream&

Declared in the header file as a friend in order to access its private members

Implementation Plan

The strategy begins with the creation of the SkipList header file where we can make the declarations for all data members and methods, including the SkipListNode struct.

1. SkipList::SkipListNode

a. Create the explicit constructor that allows SkipListNode to set its data. Use an intializer list to set all pointers to nullptr.

SkipList::SkipListNode( )

2. SkipList

a. Create constructor and destructor, compile to test for any errors at this point. Since maxLevels will default to 1 upon initialization, early tests must be done without entering a specific value in the constructor's argument. 

Declare the friend ostream insertion operator in the header file (this can be commented out until it is needed later).

SkipList::SkipList( )
SkipList::~SkipList( )
// ostream& operator<<(ostream& os, const SkipList& list);

b. Approach building the SkipList as if building a basic linked list. Start with insert( ) method since we first need to be able to place items in the list. Use a temporary public print method for testing.

SkipList::insert( )

c. contains( ) would need to be created before we can do erase( ) since it is reliant upon contains( ). We will also need to rework insert( ) so that we can now avoid inserting duplicates.

SkipList::contains( )

d. After declaring and defining erase( ), more testing should be done to be sure the list is now functioning as a basic linked list.

SkipList::erase( )

e. Approaching the concept of levels will require reworking details within the constructor so that heads_ and tails_ are dynamically allocated.

SkipList::SkipList( ) 
SkipListNode** heads_
SkipListNode** tails_

f. alsoHigher( ) will need to be implemented so that we can pass the current level to addBefore( ).

SkipList::alsoHigher( )

g. Implementing addBefore( ), will assist insert( ) with adding nodes to each level. Begin testing with a driver that uses a random generator as input for the loop adding values to the list. Also test with different values for maxLevels_.

SkipList::addBefore( )