Class SkipList<T>
- Namespace
- Utils.Collections
- Assembly
- Utils.Collections.dll
Represents a deterministic adaptive skip list that supports fast search, insertion, and deletion operations.
public class SkipList<T> : ICollection<T>, IEnumerable<T>, IEnumerableType Parameters
TThe type of elements in the skip list.
- Inheritance
-
SkipList<T>
- Implements
-
ICollection<T>IEnumerable<T>
- Inherited Members
- Extension Methods
Remarks
Instance members are not thread-safe. Callers must synchronize access when the same instance is shared between threads, including access through lookup operations such as Contains(T) and TryGet(T, out T), because lookups may maintain the adaptive index. As with other comparer-based sorted collections, an inserted value must not be mutated in a way that changes its ordering or identity under Comparer; doing so can invalidate the collection's logical organization.
Constructors
SkipList()
Initializes a new instance of the SkipList<T> class using the default comparer and a threshold of 10.
public SkipList()SkipList(IComparer<T>, int)
Initializes a new instance of the SkipList<T> class with the specified comparer and threshold.
public SkipList(IComparer<T> comparer, int threshold = 10)Parameters
comparerIComparer<T>The comparer to use when comparing elements.
thresholdintThe number of consecutive unindexed nodes that may be traversed before a subsequent node becomes eligible for promotion. Must be >= 2.
SkipList(int)
Initializes a new instance of the SkipList<T> class with the specified threshold.
public SkipList(int threshold)Parameters
thresholdintThe traversal count that must be exceeded before a subsequent node becomes eligible for promotion. Must be >= 2.
Properties
Comparer
Gets the comparer that defines element ordering and identity.
public IComparer<T> Comparer { get; }Property Value
- IComparer<T>
Count
Gets the number of elements contained in the skip list.
public int Count { get; }Property Value
IsReadOnly
Gets a value indicating whether the skip list is read-only (always false).
public bool IsReadOnly { get; }Property Value
Methods
Add(T)
Adds an element to the skip list at the appropriate position. If the list is empty, the element becomes the first and last element. Otherwise, we locate the insertion point and insert accordingly. If the element is inserted before Utils.Collections.SkipList<T>._firstElement, it becomes the new first. If it's inserted after Utils.Collections.SkipList<T>._lastElement, it becomes the new last. Otherwise, it is inserted in between two existing nodes at the bottom level. A comparer-equal element is treated as an existing element and is not inserted again.
public bool Add(T item)Parameters
itemTThe element to add.
Returns
Clear()
Removes all elements from the skip list.
public void Clear()Contains(T)
Determines whether the skip list contains a specific element.
public bool Contains(T item)Parameters
itemTThe element to locate in the skip list.
Returns
CopyTo(T[], int)
Copies the elements of the skip list to an array, starting at a particular array index.
public void CopyTo(T[] array, int arrayIndex)Parameters
arrayT[]The destination array.
arrayIndexintThe zero-based index in the destination array.
GetEnumerator()
Returns an enumerator that iterates through the collection.
public IEnumerator<T> GetEnumerator()Returns
- IEnumerator<T>
An enumerator that can be used to iterate through the collection.
Remove(T)
Removes a specific element from the skip list.
public bool Remove(T item)Parameters
itemTThe element to remove.
Returns
TryGet(T, out T)
Searches for an element that compares equal to item and returns
the stored instance. This is useful when the comparer considers only a subset of
the element's fields (e.g. a key), allowing the caller to retrieve the full stored
object rather than just a membership check.
public bool TryGet(T item, out T found)Parameters
itemTThe element to locate.
foundTWhen this method returns true, contains the stored element that matched
item; otherwise the default value.