|Pathologically Eclectic Rubbish Lister|
Linked lists as arrays: inserting valuesby radiantmatrix (Parson)
|on Sep 25, 2006 at 15:19 UTC||Need Help??|
radiantmatrix has asked for the
wisdom of the Perl Monks concerning the following question:
I've been reading Advanced Perl Programming lately, and within there is an admonition that one should "almost always" use Perl's arrays instead of a linked list. The rationale is that the built-in functions (pop, push, shift, and unshift) are quite fast -- likely much faster than anything one could implement oneself in pure Perl.
I think it's valuable advice, but the set of functions the author lists deal only with the ends of arrays. One of the values, to me, of the linked list is the ease with which one can insert values in the middle of the list. The only sensible Perl-array idiom I was able to come up with for doing this is to use array slices:
It seems to me that this method makes a copy of the array anytime you insert a value in the middle of the array. For small-ish arrays, that's fine, but for large arrays, wouldn't that be very slow?
Since I have an upcoming interest in inserting values in the middle of a list of values, I am curious if there is any way of inserting values in the middle of an array that's faster (and more RAM-friendly) than making a full copy for each insert. What can I do?
A collection of thoughts and links from the minds of geeks
The Code that can be seen is not the true Code
I haven't found a problem yet that can't be solved by a well-placed trebuchet