Alex Gaynor wrote: > I don't see how that's possible. The linked list is a pretty well > known data structure and arbitrary lookups are O(n) in it. Using the > unrolled-linked-list data structure python uses you can make it faster > by a constant factor, but not O(1). There are other structures like > skip-lists that have O(log n) arbitrary lookups though. If someone > could make an O(1) linked-list I'd love to see it :)
Yeah, you're right - I was completely misremembering how deque worked. I've come across a data structure implementation similar to the one Steve is proposing somewhere before, but deque obviously isn't it. Cheers, Nick. -- Nick Coghlan | ncogh...@gmail.com | Brisbane, Australia --------------------------------------------------------------- _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
