Hello, On Sun, Mar 15, 2009 at 2:19 PM, Ben Smithers <gingerro...@gmail.com> wrote: > Firstly, apologies if this is not the correct place to ask such a question - > I was directed here from a forum. > > I recently discovered the datastructures found in the Standard PHP Library. > I noticed that SplStack is implemented using a doubly-linked list and > wondered why. Given that a stack is LIFO store and the only operations > really needed are push and pop, why would next and previous pointers be > required on each item? There's no requirement to allow iteration over a > stack. > > It would seem to me that a stack should require a linear linked list and a > pointer to the top of the stack - which would have roughly half the memory > overhead of a doubly-linked list (half the number of pointers). > > Do i just have no idea what i'm talking about or have i missed something > obvious?
You're right, a stack can be implemented in a simpler way that would reduce slightly the memory usage. However, storing one additional pointer per doubly linkedlist (DLL) node and managing it is totally irrelevant when placed in context of PHP code. If you look at the code, you'll see that the additionnal code to make a DLL work as a stack is very small, and that's why it was implemented like that. One could implement a stack and a queue using a single linked list, but that would mean code duplication which ends up to be not worth the irrelevant speed/memory improvement. If SPLinkedList is implemented once, we might consider move SplStack and SplQueue to use that new implementation, but I believe there are other priorities for SPL right now, such as documentation. Regards, > > Thanks in advance, > > Ben > > -- > PHP Internals - PHP Runtime Development Mailing List > To unsubscribe, visit: http://www.php.net/unsub.php > > -- Etienne Kneuss http://www.colder.ch Men never do evil so completely and cheerfully as when they do it from a religious conviction. -- Pascal -- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: http://www.php.net/unsub.php
