What is the point of PHP's SplDoublyLinkedList class, and more importantly, Linked Lists in general?_问答_开发者

On a quest to expand my programming prowess,开发者_高级运维 I've delved ever-so-slightly into The Standard PHP Library. This led to my discovery of the SplDoublyLinkedList class. From there I read the descriptions of Linked Lists and Doubly Linked Lists on Wikipedia.

I understand how they work... But I cannot conceive of a reason WHY we need it—or better yet a practical example of SplDoublyLinkedList since we have indexed and associative arrays in PHP.

How are Linked Lists normally used in-and-out of PHP?

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/

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)

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. :)

You are probably right, and it just isn't very useful.

There are many uses of linked lists in theory (notably the dancing links). But most of them involves either storing and cloning its iterators elsewhere, access the content in more than two directions, or splitting and merging the lists. SplDoublyLinkedList seemed not to have those.

If it's not for algorithms, one use is to allow an object to remove the reference of itself in some list in constant time, freeing its memory and without shuffling the list (by hashing or swapping with the last item) after insertion or deletion. But this requires storing an iterator of the list in those objects.

Without those functionalities, they just behave like two deques. If you only need to access items using the iterator, they are like two stacks. One better way in single threaded simple cases, barring not already wrapped in a class, is just to use two stacks (maybe fixed arrays, or both ends of the same array). Pop from one stack and push it to another whenever you want the iterator to move, and the top of one stack is the current item. If you also need to access the head and tail, you'll need to replace the stacks with deques.

But if you want to implement stacks or deques themselves without knowing the maximum size, or even to allocate nodes of normal linked lists (in a language without those libraries like in PHP), the good way is to chain some fixed arrays together, using doubly linked lists without those features. Somehow you'll still need it.

The PHP documentation itself, like the Java one, suggests they are supposed to be just a deque supporting some extra weird features, not even two deques (I think). Don't use them if you really need doubly linked lists.

They're there because many programmers comming from other languages are used to them where arrays have fixed sizes and you have to take care of memory managment.
So for PHP they're just another tool. They're implemented because many algorithms & pattern relay on lists and so they don't need to be changed to php-arrays.

As others have mentioned, Lists are an alternative to fixed arrays which are common in other languages. But one important aspect that is often overlooked - you can insert or remove an element from anyplace within a list very efficiently.

Why would this be important? Let's say you have several items that you want to maintain sorted in a array, perhaps so you don't have to sort them later or just to minimize search time. In this instance a List can be a very powerful tool. Especially for very large datasets.

Perhaps you are writing a web application in order to make a website look and act like a book (like epub online). A collapsible TOC (table of contents) would provide random access. The linked list would provide a convenient way to implement "next page" and "previous page" buttons. Next and Previous could be implemented in other ways. The linked list would make it a snap.