Skip list representation

A Skip List is an advanced data structure that allows for fast search within an ordered sequence of elements, providing a clever alternative to balanced trees. It is effectively a linked-list that adds multiple layers on top of the standard list to enable faster search times.

Here's how a Skip List is typically represented:

• Base Layer:
  The bottom layer is a standard linear linked list that contains all the elements in the set, sorted by key.
• Express Layers:
  Above the base layer are one or more layers of "express lanes." Each layer is a linked list that skips over some elements from the list below it. The topmost layer has the fewest elements, and each layer doubles (or varies by some factor) the number of elements it skips compared to the layer directly beneath it.

A Skip List is an efficient, probabilistic data structure that enables fast search, insertion, and deletion operations, akin to balanced trees like AVL or Red-Black trees. Here's a step-by-step explanation of how a Skip List is used to represent a dictionary:

Step 1: Understanding the Structure

A Skip List is composed of several layers of linked lists, where each higher layer provides a "shortcut" through the lower layers. The bottom layer (Layer 0) contains all the elements, and each successive layer contains a subset of these elements, chosen randomly.

Step 2: Layered Links

Each node in the Skip List contains pointers to the next node in the same layer and down to the same node in the layer immediately below it.

Step 3: Initialization

When initializing a Skip List:

• Create a "head" node with pointers set to NULL for each layer.
• Set a maximum level for the list, which determines how many layers the list can have.
• Optionally, set a "tail" node with maximum possible key value to mark the end of each level.

Step 4: Insertion

To insert a key-value pair:

• Find the Position: Start from the topmost layer and move forward until you find a node with a greater key or reach the end of the layer. Then, move down one layer and continue. Record the nodes where you move down a level.
• Choose a Random Level: For the new node, randomly decide the number of layers (level) it will participate in (usually done with a coin flip algorithm).
• Rearrange Pointers: For each level up to the chosen level, update the pointers of the recorded nodes to include the new node.

Step 5: Search

To search for a key:

• Start from the topmost layer of the head node.
• Move forward in the current layer until you find a node with a greater key or reach the end.
• If you find a greater key, move down one layer.
• Repeat until you reach the bottom layer. If the key matches, return the value; otherwise, the key is not in the list.

Step 6: Deletion

To delete a key-value pair:

• Perform a search for the key, keeping track of the predecessors at each level.
• If the key is found, update the pointers of these predecessor nodes to skip the node being deleted.
• Remove the node and deallocate its memory.

Step 7: Random Level Generation

The level for a new node is typically determined using a random process. A common method is a coin flip algorithm: a random level is generated, and as long as a coin flip results in heads (or a random value meets a certain condition), you increase the level.

Step 8: Traversal

To traverse the Skip List, simply follow the bottom layer from the head node to the end, processing or printing the values.

Algorithm for Implementing Skip List

Algorithm 1: Randomly Selecting a New Node's Level
Data: p- the probability to advance a node from one level to the next, max Level - the maximal allowed level, ∞ if unrestricted.
Result: the randomly selected level of a new node. 
Function  RANDOM-LEVEL (p, maxLevel) :
    Level 	←  1
    // RANDOM draws a random number from the uniform distribution over [0,1]
    while (RANDOM() ≤ p) and (level < maxLevel) do 
        level	← level + 1
    end
        return level
end


Algorithm 2: Inserting a Value Into a Skip List
Data: list the skip list, v- the value to insert, maxLevel - the maximal level of a new node
Result: v is inserted into the list
function INSERT ( head, v, maxLevel): 
    level←RANDOM-LEVEL (maxLevel)
    if level > list.max Level then
        for klist.max Level, list.max Level 1,..., level do 
            list.heads[k] ← make an empty node (NULL)
        end
            list.max Level ← level
    end
    update ← make an empty array with level reserved elements
    y← make a node whose value is v
    for k←list.max Level, list.maxLevel – 1,...,1 do
        x←list.heads[k]
        if x is empty then
            list.heads[k] ← y
        else
            z← x.successors[k]
            while (z ≠ NULL) and (v > z.value) do
                x ← z
                z← z.pointers[k]
            end
            x.successors[k] ← y
            y.successors[k] ← z
        end
    end
end


Algorithm 3: Searching a Skip List
Data: list - the skip list to search, v - the value to find
Result: x- the node containing v, or failure if v isn't in the list.
function SEARCH ( list, v):
    x←list.heads [list.max Level]
    for k←list.max Level, list.max Level - 1,..., 1 do 
        if x = NULL then
            x←list.heads[k]
        end
        while (x.successors[k] ≠ NULL) and (x.successors[k].value < v) do
            x←x.successors[k]
        end
    end
    // At this point: x.value < v ≤ x.successors[1].value 
    If  x.successors [1] ≠ NULL and x.successors[1].value = v then
        return  x.successors [1]
    else
        return failure
    end
end


Algorithm 4: Deleting a Value From a Skip List
Data: list the skip list, v - the value to delete
Result: if present, a node whose value is v is deleted from list. 
function :
    update← make an empty array with list.max Level  NULL  elements
    for k←list.max Level, list.max Level 1,..., 1 do
        x←list.heads[k]
        y ← x.successors[k]
        while (y ≠ NULL) and (v > y.value) do
            x← y
            y←x.successors[k
        end
        if y ≠ NULL then
            // At this point we have that y.value> v
             if (y.value = v) then
                // y will be deleted, and we'll point x to
                y's  k-th successor
                update[k] ← x
            end
        end
    end
    if y.value = v then
        // v is in the list, so we delete y by removing any links to it
        for k ←1,2,..., list.max Level do
            if update[k] ≠ NULL then
                update[k].successors[k] ← y.successors[k]
            end
        end
        // We decrease the max level if it's been completely deleted
        while (list.maxLevel > 1) and (list.heads [list.max Level] = NULL) do
            list.max Level ← list.max Level - 1
        end
    end
end

Advantages Skip List representation of a dictionary:

• Simpler to Implement: Compared to balanced trees, skip lists are easier to implement while still providing efficient search operations.
• Amortized Costs: Operations have good amortized time costs, making them suitable for applications with a mix of frequent reads and occasional writes.
• Lock-Free Concurrency: Skip lists can be more easily implemented in a lock-free manner, which is useful for concurrent algorithms.

Disadvantages Skip List representation of a dictionary:

• Randomization Overhead: The randomization needed for maintaining balance can introduce overhead.
• Space Consumption: Skip lists use more memory than a simple linked list due to the additional pointers for the express lanes.