php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Request #48358 SplDoublyLinkedList needs an insertAfterIterator() method or something similar
Submitted: 2009-05-21 17:02 UTC Modified: 2012-11-29 14:13 UTC
Votes:27
Avg. Score:4.7 ± 0.7
Reproduced:21 of 23 (91.3%)
Same Version:9 (42.9%)
Same OS:5 (23.8%)
From: dannel at aaronexodus dot com Assigned: colder
Status: Closed Package: SPL related
PHP Version: 5.3.0RC2 OS:
Private report: No CVE-ID:
 [2009-05-21 17:02 UTC] dannel at aaronexodus dot com
Description:
------------
The SplDoublyLinkedList is great, but it lacks a way to insert a node somewhere in the middle of the list.

One could technically extend the class and provide that functionality, but due to the fact that there seem to be [documented] data members in SplDoublyLinkedList, the only way to do it would be to find the reference node, insert the new node, and move all of the following nodes up one slot in the list, resulting in O(n) performance for an insert.

I propose adding an insertAfterIterator() method which would place the new node after the current node the iterator points to.

Another option could be an insertAfterArrayKey() method which would act similarly, but would find the reference node via a given array key, which might be a little more straightforward to use in code.

Each should probably have an insertBefore*() counterpart as well.


Patches

Add a Patch

Pull Requests

Pull requests:

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2010-05-22 13:46 UTC] 1000235409 at smail dot shnu dot edn dot cn
i have encountered the same problem today, after this was modified for 1 year...

but i have a solution to solve this problem. write anohter class with a lots of 
spldoublylinkedlists inside it. however, complex algorithm may be used...
 [2010-12-20 14:28 UTC] jani@php.net
-Package: Feature/Change Request +Package: SPL related
 [2011-04-15 21:23 UTC] omercan at gmail dot com
O(n) complexity should be expected from a list data structure along with no array access. The drawback of lists is they lack direct access to the elements by their position. Well, that's not the case with SplDoublyLinkedList because there's array access. So, it's a different implementation as far as it seems.

In my opinion, the problem with SplDoublyLinkedList is that the main operations are left to be implemented in the user land, which require iterating over the list in each. This class can be much more valuable if the following operations are included:

clear() -> clear all elements

remove($value) -> return number of removals b/c $value can be more than 1

sort(Closure $predicate) -> sort without keeping key association

swap($list) -> swap with another list or a Traversable instance

unique() -> return the unique values in the list, possibly in a new list
 [2012-11-01 00:57 UTC] dnwake at gmail dot com
This is ridiculous.  

Efficiency of inserting and deleting in the middle of the list is the main motivation for using a linked list in the first place.
 [2012-11-29 11:00 UTC] rdohms@php.net
I'm also running into this, usual implementations of DoublyLinkedList describe the 
insertBefore and insertAfter methods, wondering why they were left out in this 
implementation.
 [2012-11-29 14:13 UTC] colder@php.net
It is not as easy as one might think.

The state of iterators are separated from the state of the list itself. This allows for multiple concurrent iterations on the same list but it complicates the issue at hand.

I see four viable alternatives (example for insertAfter):
  - SplDoublyLinkedList::insertAfter(value)           -- O(1), but would work only for explicit iteration using Iterator methods, not foreach()! which works using a fresh iterator.
  - SPLDoublyLinkedList::insertAfter(index, value)    -- O(n), not exactly what we want but could be working.
  - SPLDoublyLinkedList::insertAfter(iterator, value) -- O(1), needs validation of the iterator itself.
  - SplDoublyLinkedList generates iterators of the class SplDoublyLinkedListIterator, which define a insertAfter(value), would require SplDLL to be an IteratorAggregate instead of Iterator.

Those are not mutually exclusive, but alternative #1 or #3 seem the most useful .

Note that while traversing elements should be easily doable, since list elements are ref-counted, the key() of iterators might return inconsistent results if you allow the middle of the 
lists to be expanded/reduced. Making it consistent would make it O(n), so it's probably not a big problem to keep it that way.
 [2013-03-19 13:48 UTC] dsp@php.net
-Status: Assigned +Status: Closed
 [2013-03-19 13:48 UTC] dsp@php.net
Automatic comment on behalf of mbaker@inviqa.com
Revision: http://git.php.net/?p=php-src.git;a=commit;h=42574690795937290a4ad6d319f917c077542953
Log: Fix #48358 add() method for SplDoublyLinkedLis
 [2013-11-17 09:31 UTC] laruence@php.net
Automatic comment on behalf of mbaker@inviqa.com
Revision: http://git.php.net/?p=php-src.git;a=commit;h=42574690795937290a4ad6d319f917c077542953
Log: Fix #48358 add() method for SplDoublyLinkedLis
 
PHP Copyright © 2001-2014 The PHP Group
All rights reserved.
Last updated: Sat Apr 19 04:01:55 2014 UTC