These attributes and methods are defined on a
Inserts a new child element
into the skip list.
If you created the skip list with
allowDups=0 and the new
element has the same key as an existing member of
the list, this method will raise a
If duplicates are allowed (the
allowDups=1 option to the
constructor), and the new element's key duplicates
one or more already in the list, the new child will
be added in sequence after the other duplicates.
This makes the ordering stable; see Section 2.1.3, “Stability”.
Deletes the first or only element whose key is equal to
and returns the deleted child element (or
None if there are no matching
If duplicates are allowed and there are multiple
elements equal to
only the first one will be deleted.
Returns the first or only object whose key equals
If there are no such objects, this method raises a
Searches for the first element whose key is equal
to or greater than
and returns an iterator that iterates over all
If there are any elements in the skip list, this
method returns the first element. If the skip list
is empty, it raises
This special method defines the meaning of the
len() function when
applied to a
SkipList. It returns
the number of child elements in the list.
Returns an iterator object that can be used to iterate over the elements of the skip list. You can have multiple independent iterators pointing at the same skip list, and each will move independently of the others. This allows constructs like:
for i in s: ...
s is a
Such a loop will set
each child value from
.__contains__ ( self,
Defines the meaning of the Python
operators in the usual way for container classes.
s is a
SkipList, the expression
k in s returns true if and
k is equal to at least
one member of
k not in s
returns true iff
k is not
equal to any member of
.__delitem__ ( self,
.__getitem__ ( self,
This method defines the usual meaning of
s is a
SkipList. It has the same
This syntax is useful mainly for skip lists that
don't allow duplicates. If you need to retrieve
multiple members that all compare equal, use the
Read-only; equal to the number of times the list
has been searched. Each call to the
.delete() method is counted as
Read-only; equal to the number of times two elements
have been compared with the
cmpFun function (or its default).
Statistically, the ratio of
.nSearches should be
proportional to the log of the number of elements.
For analysis, see Pugh's original article.