On Mar 20, 1:50 pm, Scott David Daniels <scott.dani...@acm.org> wrote: > Raymond Hettinger wrote: > > [Aahz] > >> The doubly-linked list part is what's sick and perverted. > > > The doubly-linked list part is what gives it big-oh running > > times the same as regular sets. If the underlying sequence > > is stored as a list, then deletion goes from O(1) to O(n). > > If the insertion times are recorded in a dictionary, then > > the insertion order has to be sorted prior to iteration > > which makes iteration go from O(n) to O(n log n). > > The double-linked list part could be done with weakrefs and > perhaps Aahz would relax a bit. > > --Scott David Daniels > scott.dani...@acm.org
Whether the structure holds one reference to its "containees" or three doesn't matter. But you're right, weakrefs are relaxing. I pronounce it the perfect data structure. Tell your CS 200 professor immediately. Shout it from the rooftops. IINM if I'm not mistaken, an O(1) 'multiadd' method wouldn't be hard either. If the item exists already, insert it in place in the linked list. -- http://mail.python.org/mailman/listinfo/python-list