SplStack Implementation View as Markdown

Hello,

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

--

--
Etienne Kneuss
http://www.colder.ch

Men never do evil so completely and cheerfully as
when they do it from a religious conviction.
-- Pascal

Hello Ben,

there is no need in checking whether the implementation uses single
or double linked. Access to any structure from the engine will always
be slower by orders of magnitude, then maintaining a pinter structure
directly in C code. Now doing something with that in PHP code will
again be slower - by orders of magnitude.

marcus

Sunday, March 15, 2009, 2:19:55 PM, you 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?

Thanks in advance,

Ben

Best regards,
Marcus