Some of the information you want about Perl's internal structure is at Shift, Pop, Unshift and Push with Impunity!. When Perl 5.8 comes out building a list with unshift will be relatively efficient as well.

By and large Perl's data structures are implemented with buffered allocation for efficiency. What I mean by that is that an array has a contiguous block of space allocated for it, but the allocation is done in powers of 2 so that there is some buffer at the end. When you add to it, as long as it fits in the existing space, it just goes there. When you want to remove from it, it just marks the end as being a little shorter.

What this does is waste some space, but if you go to build up a large array or string incrementally (eg using push or .=) the amortized cost per increment is O(1) and the overall allocation overhead winds up being O(n).