Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:43351 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 31243 invoked from network); 15 Mar 2009 13:30:26 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 15 Mar 2009 13:30:26 -0000 Received: from [127.0.0.1] ([127.0.0.1:26945]) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ECSTREAM id 6C/78-06903-2F20DB94 for ; Sun, 15 Mar 2009 08:30:26 -0500 X-Host-Fingerprint: 137.222.239.33 wireless-user.resnet.bris.ac.uk Received: from [137.222.239.33] ([137.222.239.33:18923] helo=localhost.localdomain) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id AF/96-06903-F700DB94 for ; Sun, 15 Mar 2009 08:20:00 -0500 Message-ID: To: internals@lists.php.net Date: Sun, 15 Mar 2009 13:19:55 +0000 User-Agent: Thunderbird 2.0.0.19 (X11/20090105) MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Posted-By: 137.222.239.33 Subject: SplStack Implementation From: gingerrobot@gmail.com (Ben Smithers) 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