Erm, no a perl AV (the underlying C data type underneath an @array) is a pointer to a C array of SV* (pointers to the underlying C scalar value type). You can't trim elements out from the middle without shifting the successors down, nor prepend an element without shifting things up; you can append (i.e. push) items onto it but this may trigger a realloc of the C array of SV*s (likewise prepending may need to do this as well; but there may be an optimization for that). See the (slightly long in the tooth) relevant section of Perlguts Illustrated for more details.

Now having said that, for most of what you'd use a linked list for in another language yes arrays are the appropriate data structure. And if you really need a true linked list it's trivial to whip one up.

Update: And just to clarify a bit when I say you can't trim things out of the middle I'm talking about the underlying C operations that are taking place. Of course when you use splice it "Just Works™" and the representation of the array looks as if you've just removed the element(s) out from the middle; but underneath it all there's some shifting around being done that's going to be more overhead than would be if a true LL was being used under the hood.

Thanks Fletch, I'm going to comp performance between using an array and a linked list. BTW, to dragonchild, an example of what I want to avoid is the added CPU usage when inserting characters into the middle of the array. Lets say my user decides to paste a block of text into the middle of the document. The bigger the array is the more CPU it uses to do so. Right now I'm seeing significant (to me) CPU usage when this occurs, and since my intent for this project is to be entirely non-blocking, I figure I may as well do everything I can to drop any unecessary CPU usage. From what I'm seeing, I certainly have to question your statement about a perl array being a linked list, as it certainly doesnt perform like one.

Lets say my user decides to paste a block of text into the middle of the document. The bigger the array is the more CPU it uses to do so. Right now I'm seeing significant (to me) CPU usage when this occurs,

You said you were developing a "win32 shell", but now people can use it to edit documents? What kind of application is this exactly? What kind of data are these arrays holding, how big are they, and what operations are you performing on them?

If you describe the application and show some code, we can make better recommendations to help your performance problems. It might even turn out that the array operations aren't the bottleneck at all.

The point was that, from within Perl itself (and not dipping into XS), the array is the best data structure for handling the needs of a linked list. Yeah, you could create a hashref for each node and put in references to the next element. But, I would be shocked and appalled if doing that was faster than the corresponding array implementation.

The only benefit I can see is if you are translating algorithms directly from C (or a similar language) and want to have functions that you can pass nodes and it can call $node->next or $node->prev. But, translating functions to take $arr and $idx instead and $node->next translates to $arr->[$idx+1] is probably saner.

---

My criteria for good software:

1. Does it work?
2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

Given that this is (almost always) an optimization for providing the tools to properly traverse said list, it's not necessary. And, linked lists only point in one direction. Doubly-linked lists point in both.

The point of a linked list is to provide O(1) add and remove operations anywhere in the list, given certain assumptions. If you can do that with a Perl array (which you can), then it satisfies all the reasons why a linked list exists. The implementation of meeting those criteria is ... irrelevant.

Linked lists are, in many ways, inferior to Perl's arrays. You cannot do random access into a linked list, but you can into a Perl array.

---

My criteria for good software:

1. Does it work?
2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

perl array operations are on the average case:
• pop is O(1)
• push is O(1)
• shift is O(1)
• unshift is O(1)
• splice is O(n)

update: examining (blead) perl source code, I have found that push and unshift are O(1) and not O(n) as previously stated (thanks tilly).

The point of a linked list is to provide O(1) add and remove operations anywhere in the list, given certain assumptions. If you can do that with a Perl array (which you can), then it satisfies all the reasons why a linked list exists.

You can? Are you claiming that splice() is O(1)? I don't think that's true, but maybe I'm misunderstanding you...

-sam

My point is that Perl arrays and linked lists are not the same unless they are the same. And they aren't.