A skip list container class in Python |  |
A skip list container class in Python | |
When considering the class structure of the application, two classes are obvious:
The user sees only the SkipList class, a classic
container object.
It makes sense to create a class to hold all the
information for one node of the skip list data
structure. This class is called _SkipItem; the single
underbar in its name signifies that it is private to
the module.
However, we need a third class to represent the iterators
that are returned by the .find()
method in the SkipList class, and by that class's special
.__iter__() method.
So we define a third class, _SkipListIterator, that defines a
.next() method. This
object keeps track of its position in the list by
pointing to a _SkipItem.
How does this iterator know when it has reached the end of
the skip list? It can't compare the _SkipItem to
.__terminator, which is private to
the SkipList class. Even if we made that attribute public,
a _SkipItem object doesn't contain a reference to its
containing SkipList.
The solution is to stipulate that the
.__terminator object's forward
links all point to itself. That way, a _SkipListIterator instance
can detect when it is pointing at the terminator.
There is one more complication with this technique. What
happens if someone has a copy of an iterator that points
to a _SkipItem that has been deleted
from its containing SkipList?
In order that the _SkipItem object correctly detects this
erroneous situation, it must know when it represents a
deleted element.
Therefore, we stipulate that in a _SkipItem instance the
level-0 forward link must be set to
None when it is deleted. That
way, the .next() method will know
to signal an error and not attempt to chase its forward
link.