On Wed, 2003-08-20 at 23:38, Jaap van Ganswijk wrote: > > Finding a single element in a doubly linked list can > be sped up using a hash-code table, but it also > makes things like renumbering numerically indexed > entries a lot harder (I think, I never used a > combination of these things.)
Doubly threaded red-black trees are good for in order traversal and arbitrary lookup. As with most structures that provide more speed, you use more memory :) O( lg n ) insertion, O( lg n ) deletion, O( lg n ) search. Threaded means the in order nodes are threaded into a linked list. PHP I believe uses hashes of some sort, I'm not sure how they keep track of the insertion order for doing a foreach loop -- I guess we could look. On a more related topic: if he's happy with the unset() function but wants the indexes renumbered, he could write a C function which performs the renumbering. Should keep it relatively fast and provide the option of renumbering -- or not. Cheers, Rob. -- .---------------------------------------------. | Worlds of Carnage - http://www.wocmud.org | :---------------------------------------------: | Come visit a world of myth and legend where | | fantastical creatures come to life and the | | stuff of nightmares grasp for your soul. | `---------------------------------------------' -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
