What is the point of PHP's SplDoublyLinkedList class, and more importantly, Linked Lists in general?

The SPL data structures reduce memory consumption and improve performance. Good explanations:

Data structures are inherently language-independent and exist as a set of logical concepts based in mathematics. These containers use different algorithms as appropriate to maximize efficiency.

For example, if you don't need the hash map capabilities of an associative array -- that is, if you aren't using the array key for a specific purpose and only need an enumerated array -- SplFixedArray (formerly SplFastArray, currently undocumented) may be a suitable replacement. The only caveat is that the size of the array is fixed, meaning that you must specify the size when you instantiate the class and an error will occur if you attempt to store more than that number of elements. This is the reason that, on average, it performs better than standard PHP arrays.

http://web.archive.org/web/20130805120049/http://blueparabola.com/blog/spl-deserves-some-reiteration

Within the C code that makes up the PHP interpreter, arrays are implemented as a data structure called a hash table or hash map. When a value contained within an array is referenced by its index, PHP uses a hashing function to convert that index into a unique hash representing the location of the corresponding value within the array.

This hash map implementation enables arrays to store an arbitrary number of elements and provide access to all of those elements simultaneously using either numeric or string keys. Arrays are extremely fast for the capabilities they provide and are an excellent general purpose data structure.

In computer science, a list is defined as an ordered collection of values. A linked list is a data structure in which each element in the list includes a reference to one or both of the elements on either side of it within the list. The term “doubly-linked list” is used to refer to the latter case. In the SPL, this takes the form of the class SplDoublyLinkedList.... It makes sense to use lists when the number of elements to be stored is not known in advance and the elements only need to be accessed by sequential position.

http://matthewturland.com/2010/05/20/new-spl-features-in-php-5-3/


According To Wikipedia,

The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk. For that reason, linked lists allow insertion and removal of nodes at any point in the list, with a constant number of operations.

On the other hand, linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations — such as obtaining the last node of the list, or finding a node that contains a given datum, or locating the place where a new node should be inserted — may require scanning most of the list elements.

So to answer your question, I have no idea. :)


First and foremost, SplDoublyLinkedList are objects, as such

  • they can be extended, so you can override their methods (you may for example return all strings uppercased, etc)
  • the interfaces they implement can be checked like in myfunc( SplDoublyLinkedList $var ) ...
  • they're passed as reference by default
  • etc.

Secondly, SplDoublyLinkedList accept iteration modes, so you can delete your items on the go, and switch direction without reordering the array or complicating your code:

SplDoublyLinkedList::IT_MODE_LIFO (Stack style)

SplDoublyLinkedList::IT_MODE_FIFO (Queue style) The behavior of the iterator (either one or the other)

SplDoublyLinkedList::IT_MODE_DELETE (Elements are deleted by the iterator)

SplDoublyLinkedList::IT_MODE_KEEP (Elements are traversed by the iterator)

The above quotation is from http://simpletechinfo.com/SplDoublyLinkedList which contains some code samples.

There are other perks (like foreach not having to do a copy in memory of all the data, etc)