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: 

sub insert_array_elem {
   my ($ra, $elem, $index) = @_; # insert $elem before $ra->[$index]

   if ($index < 0) {
     # convert negative indexes to positive equiv.
     $index = @$ra + $index;
   }

   if ($index == 0) {
     # at the beginning
     unshift @$ra, $elem;
   }
   elsif ($index == @$ra) {
     # at the end
     push @$ra, $elem;
   }
   else {
     # insert between -- makes copy: bad for large arrays?
     @$ra = @$ra[0..$index-1], $elem, @$ra[$index..@$ra-1];
   }
}

[download]

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?

Update: D'oh! I had completely spaced the existence of splice. Thanks to shmem especially for the benchmark (saved me some work), but also to Fletch and Tanktalus who were first to discuss the use of splice for this purpose.

For the record, or for anyone who might search this node later: 

# insert $elem before $index in @array
splice(@array, $index, 0, $elem);

[download]
<–radiant.matrix–>
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

In reply to Linked lists as arrays: inserting values by radiantmatrix

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.