# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

A values-sorted data structure with fast insertion and deletion

Contributed by:
Bradley Klee

ResourceFunction["SkipListStructure"][] initializes an empty data skiplist structure. | |

ResourceFunction["SkipListStructure"][ sequentially inserts key-value pairs from | |

ResourceFunction["SkipListStructure"][ returns the | |

ResourceFunction["SkipListStructure"][ returns a values-sorted Association of all key-value pairs contained in | |

ResourceFunction["SkipListStructure"][ returns the first element in | |

ResourceFunction["SkipListStructure"][ returns the first element and removes it from | |

ResourceFunction["SkipListStructure"][ depicts | |

ResourceFunction["SkipListStructure"][ supports an additional |

ResourceFunction["SkipListStructure"] is an implementation of a values-sorted association, which is optimized to have logarithmic Insert and KeyDrop times. In terms of functionality and design, this skiplist structure most closely follows DataStructure (but without optimizations due to compiling code).

An initialization *init* can be either an Association or a List. If the latter, the keys are taken to be the corresponding Part indices.

ResourceFunction["SkipListStructure"] accepts the option "OrderFunction", with default value Order. User-specified alternatives should behave like built-in Order by taking an adjacent pair of input values and returning 1 if the values are correctly ordered, -1 if they need to be transposed, or 0 if they are equivalent. An initialization of the structure can be done using this option.

In addition to primary usages above, ResourceFunction["SkipListStructure"] allows a wide variety of auxiliary usages:

SkipListStructure[data, "InsertPosition", value] | searches data and returns before and after indices pointing where to insert value. |

SkipListStructure[data, "Lookup", key,default] | attempts a Lookup, and returns default when key is not set. |

SkipListStructure[data, "Normal", n] | returns a values-sorted Association of only those key-value pairs occurring on the level of the n^{th}data structure. |

SkipListStructure[data, "Last"] | returns the last element of data in the given ordering. |

SkipListStructure[data, "PopLast"] | returns the last element and removes it from data. |

SkipListStructure[data, "FirstLast"] | returns both first and last elements of data. |

SkipListStructure[data, "MemberQ", value] | returns True if data already contains value, and False otherwise. |

SkipListStructure[data, "EmptyQ"] | returns True if data contains no key-value pairs, and False otherwise. |

SkipListStructure[data, "Validate"] | checks local structure and Ordering, returning True for valid data, and False otherwise. |

Desired complexity statistics are achieved by emulating 2,3-Trees with a linked list. In fact, the linked list has both horizontal and vertical links, so it can also be accurately described as a linked array with dimensions *(log n)⨯ n*.

All valid ResourceFunction["SkipListStructure"] linked arrays are consistent with a constraint on branching ratio per-level. One or two vertices occur between every pair of adjacent horizontal links.

The linked array of a particular ResourceFunction["SkipListStructure"] can be depicted through the "Visualization" method. Five or six different colors are used to distinguish between inequivalent vertex figures:

Color | Vertical? | Next Color |

Yes | ||

No | ,, or | |

Yes | ||

No | ||

No | ,, or | |

Yes | None |

It is relatively easy to delete a blue or purple vertex, or to insert around a yellow vertex. Deleting a yellow vertex or inserting around a blue or purple vertex sometimes requires non-trivial recursion and heuristic decision making.

The leading depth dimension log *n* is predictive of Insert / KeyDrop times. This method iterates through levels, making local changes only, until a halting condition is reached when the ResourceFunction["SkipListStructure"] is proven valid around every vertex.

ResourceFunction["SkipListStructure"] is path dependent with regard to sequences of insertions and deletions. Two ResourceFunction["SkipListStructure"] objects can fail a SameQ test, while having the same normal form.

Initialize an empty SkipListStructure:

In[1]:= |

Out[1]= |

Insert a string value:

In[2]:= |

Out[2]= |

Look up the value associated with key 1:

In[3]:= |

Out[3]= |

Insert another string value and print the normal form:

In[4]:= |

Out[4]= |

Use KeyDrop method to remove the value "alpha" and again print the normal form:

In[5]:= |

Out[5]= |

Remove the key corresponding to the value "one" and check if the data is empty:

In[6]:= |

Out[6]= |

Sort a list of ten random reals:

In[7]:= |

Out[9]= |

Initialize a SkipListStructure with random initial data and print the first and last elements:

In[10]:= |

Out[12]= |

Visualize the SkipListStructure as a rectangular graph:

In[13]:= |

Out[13]= |

List the five lexicographically earliest elements of the SkipListStructure:

In[14]:= |

Out[14]= |

Print the new first element:

In[15]:= |

Out[15]= |

Visualize the SkipListStructure again as a rectangular graph:

In[16]:= |

Out[16]= |

Validate the remaining data:

In[17]:= |

Out[17]= |

Initialize alphabetical data with randomized pointers and show the visualization:

In[18]:= |

Out[18]= |

Return values on each level in normal form:

In[19]:= |

Out[19]= |

Find before and after pointers when inserting a second letter "k":

In[20]:= |

Out[20]= |

Look up the predecessor and successor directly:

In[21]:= |

Out[21]= |

Use SkipListStructure to sort a randomized list of RandomTree outputs:

In[22]:= |

Out[19]= |

Sort values in reverse order:

In[23]:= |

Out[23]= |

Both SkipListStructure and the resource function IndexedQueue have logarithmic insertion times:

In[24]:= |

Out[24]= |

Sort a list of ten random reals:

In[25]:= |

Out[27]= |

The resulting SkipListStructure is not completely empty:

In[28]:= |

Out[28]= |

Use the "GarbageCollect" method to remove "MissingIndices" and reset "NextIndex" to 1:

In[29]:= |

Out[30]= |

The Lookup method does not thread over lists:

In[31]:= |

Out[31]= |

Compare insert-history dependence of SkipListStructure using its "Visualization" method:

In[32]:= |

In[33]:= |

Out[33]= |

The structure is different, but the normal forms are exactly the same:

In[34]:= |

Out[34]= |

- 1.0.0 – 13 March 2023

This work is licensed under a Creative Commons Attribution 4.0 International License