This is pretty easy to implement, by combining a double linked list with a hashtable, however I wanted this to have the same interface as a double linked list, so I made a new
dequeues
vocabulary which abstracts the operations on a double linked list, such aspush-front
push-back
pop-front
pop-back
Double linked lists in the
dlists
vocabulary now implement this protocol instead of exposing dlist-specific operations.The dequeue protocol also has a
dequeue-member?
generic word. This word runs in linear time on dlists.Search dequeues in the
search-dequeues
wrap an assoc and a dequeue and provide a sub-linear implementation of dequeue-member?
(constant time if the assoc is a hashtable). Pushing elements adds them to both the dequeue and assoc; the membership test is then just a call to key?
on the assoc.
No comments:
Post a Comment