Skip to main content

Skip list based sorted collections

Project description

Build status

skiplistcollections is a Python module containing skip list based sorted collections. skiplistcollections is written in Python and works with:

  • CPython 2.6+, 3.2+
  • PyPy 1.9+

Project page on GitHub:

Project page on PyPI:


SkipListDict is container providing dict-like interface and implemented using skip list. It’s permanently sorted by key.

  • Iterating the container (starting with any key, supports reverse ordering) is O(n)
  • Getting, setting and deleting arbitrary key is O(log n) on average, O(n) in worst case (degenerated skip list)

See for details.

>>> from skiplistcollections import SkipListDict
>>> things = SkipListDict(capacity=16)
>>> len(things)
>>> things['x'] = 1
>>> things.setdefault('x', 'DEFAULT')
>>> 'x' in things
>>> len(things)
>>> things['g'] = 2
>>> things['z'] = 3
>>> tuple(things.keys())
('g', 'x', 'z')
>>> tuple(things.values())
(2, 1, 3)
>>> tuple(things.items())
(('g', 2), ('x', 1), ('z', 3))
>>> tuple(things.items(start_key='x'))
(('x', 1), ('z', 3))
>>> tuple(things.items(start_key='x', reverse=True))
(('x', 1), ('g', 2))
>>> del things['z']
>>> things.update({'a': 'A', 'b': 'B'})
>>> len(things)
>>> things
SkipListDict({'a': 'A', 'b': 'B', 'g': 2, 'x': 1}, capacity=16)

As you can see, SkipListDict follows Python dict interface quite closely. In fact it inherits MutableMapping Abstract Base Class.

There are differences of course:

  • You need to set the maximum dict size when you create it
  • Initializing using another mapping is not supported yet
  • You can’t use None as a key
  • items, keys, and values are views and accept start_key and reverse parameters


SkipListSet is set implementation using skip list. It’s permanently sorted by key.

  • Iterating the container is O(n)
  • Adding, removing and checking if a key exist in the containe is O(log n) on average, O(n) in worst case (degenerated skip list)
>>> from skiplistcollections import SkipListSet
>>> things = SkipListSet(capacity=16)
>>> len(things)
>>> things.add(3)
>>> len(things)
>>> things.add(1)
>>> things.add(4)
>>> things
SkipListSet((1, 3, 4), capacity=16)
>>> tuple(things)
(1, 3, 4)
>>> things.remove(2)
Traceback (most recent call last):
KeyError: 2



  • Fixed bug with SkipListDict yielding too many items if start_key was not found (GitHub issue #1)


  • Fixed SkipListDict repr
  • Created SkipListSet


  • Included start_key and reverse values in views reprs
  • Improved README


  • items(), values(), keys() return views now


  • Improved README

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for skiplistcollections, version 0.0.6
Filename, size File type Python version Upload date Hashes
Filename, size skiplistcollections-0.0.6-py2.py3-none-any.whl (6.9 kB) File type Wheel Python version 2.7 Upload date Hashes View
Filename, size skiplistcollections-0.0.6.tar.gz (4.8 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page