Re: Linked lists as arrays: inserting values

[Tanktalus]

Well, it seems that even you quote says "almost always" - perhaps you've found one of the places that make it "almost always" rather than just "always".

That said, as far as I'm aware, perl data is mostly a small struct of pointers, so copying them around is probably not that expensive - O(n) based on the number of items that need to be copied around instead of O(nm) where m is related to the length of the strings, or the contents of whatever they may refer to (hash refs, array refs, objects, etc.). So it may not really be that bad to use splice.

The flip side is that by using perl arrays for your data instead of linked lists, perl handles all the details for you. Not that linked lists are necessarily hard or anything, but any time you introduce any type of complexity, you increase the possibility for bugs. By their nature, programs are complex, so we can't avoid that risk. However, we can avoid risk in areas with insignificant gains.

That, of course, begs us to ask: what gains? And thus, I challenge you to benchmark it to prove that there are gains to be had with another method, and to prove that those gains are of significance in your application.

My guess is that you'll need a package full of code to abstract the list away to keep the rest of your code simple. And that will eat away at significant portions of your speed gains. And then, if you ever want to hand your list to some standard function, you're going to have to convert it back to a list anyway, and there goes all the rest of your gains.

That's just a guess, though. ;->

[tilly]

Absolutely the correct answer.

Building a large data set by repeatedly splicing into the middle is indeed O(n*n) while a linked list is O(n). But that is O(n*n) with a small constant term versus O(n) with a big term. Unless your dataset is very large, the native array approach will be far faster. Just consider the cost of accessing the next element. With the native approach it will be a pointer lookup versus having to make a function call (and Perl function calls are slow).

Furthermore a final reason not to use linked lists in Perl. Unless you are very careful, the linked lists will have circular data structures (each item points to the next which points to the previous). Therefore you are either in the business of having to do memory management yourself, or else you need to add yet another layer of slow indirection. Either way you've added more complexity, more room for bugs, and have reduced your potential performance gains even more.