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

views:

answers:

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

+1 A:

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.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.number of operations.

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

Dutchie432 2010-10-18 20:58:19

HAha! Yeah I read that too. +1 for "I have no idea. :)"

Stephen 2010-10-18 20:59:45

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.

Fge 2010-10-18 21:05:28

Is this based on assumption? It seems a stretch that an unneeded data structure--one that only exists to appease programmers transitioning to PHP from another language--would be implemented in the SPL...

Stephen 2010-10-18 21:07:29

They're implemented in the SPL as custom php-written implementations are far less efficient. The php community could live without them for years. And lists are sure one of the most important data structures used. Same applies for classes for example - you don't need them to write programms but they sure do help but they're a tool too.

Fge 2010-10-18 21:12:00

Okay I'll bite. They are not necessary (obviously since I've gotten on so long without them), but do you have an example of how they could make my life easier? You've compared them to classes. Classes make my life approximately nine billion times easier. How and where does a linked list fit in PHP?

Stephen 2010-10-18 21:15:50

They don't make life easier in PHP. In PHP you can add new entries to an array like '$array[] = $object;' without having to check for indexes and array size (IndexOutOfBoundException in Java I think). But you can't do this in any compiled language. There arrays have fixed sizes. This is where lists come into play - they don't have a fixed size and can be extended without expansive copying the complete array into a bigger one. To understand the real advantage you've to unterstand how arrays and lists work in any compiled language as they're way more restrictive.

Fge 2010-10-18 21:27:35

Don't get me wrong... **I'm** obviously the one who doesn't get it. But your last comment confuses me. "They don't make life easier in PHP." and "To understand the real advantage you've to unterstand how arrays and lists work in any compiled language." So is there, or is there not a real advantage?

Stephen 2010-10-18 21:38:34

The advantage over arrays isn't that clear in php as php's arrays are more powerfull. In any compiled language when you create an array you have to specify how many entries it will be able to take. If you want to make this array larger, you have to copy it into a larger one (which takes quite a long time). Lists don't have this size limit. In PHP you don't specify the the array size - they extend automatically. So yes - there is no real benefit *in PHP*. In PHP they're there because they're a standard tool in almost every other language.

Fge 2010-10-18 21:50:43

So I was right? :)

Dutchie432 2010-10-19 12:26:20

Basically yes. In my understanding the spl is a collection of tools everyone's free to use. You can't even say lists are better then arrays in general, they're a great tool when the situation requires them. The (only, important) benefit they have in general isn't there in PHP.

Fge 2010-10-19 13:10:59

ansaurus

tags:

views:

answers:

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

related questions