Re^2: Array VS Linked List

[gamache]

Is there then a way, when handed only one element of an array, to obtain the next or previous element?

[dragonchild]

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.

[salva]

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).

[tye]

Wow. (Update: I guess you are thinking of C arrays not Perl arrays, or at least an implementation much more like a naive, dynamic C array than what Perl actually uses.)

I'll agree with pop and shift being O(1) and not just in an average case. They are always O(1). (I won't argue with whether O() notation implies worst case or average case or whatever, mostly because I don't care.)

I'll agree with splice being O(N). Splicing to remove from the middle is always O(N/2). Splicing at position J elements from either end if often O(J). But splicing to insert K elements can be O(N+K). So averaging out to O(N) isn't a bad summary. Continuing to ignore some predicted objections to misuse of O(), I'd say splicing to remove is O(N/2) while splicing to insert is O(N+K). :)

If you push N times, then that is O(2*N), O(N) for the realloc() calls that likely end up copying the elements each time the array size doubles and O(N) for the N items being pushed. So push is O(2) on average. And using push on an array that both shrinks and grows is closer to O(1) than O(2) (yes, I'm still ignoring it).

If you unshift N times, then that is a bit more complex. I don't have swapped in the exact algorithm that is used for "leave some space at the front in case they unshift again", but I think it is also exponential (or is that "geometric"?) so unshift probably averages to O(3).

See Shift, Pop, Unshift and Push with Impunity! for another take on this.

[tilly]

Double check. Last I checked, unshift was O(1) average case as well.

[dragonchild]

I'm sure you mean that push is O(1). shift and unshift can be made O(1) very easily by the space padding provided at the beginning of an array and they have 1 O(N) operation every M entries (where M, I think, is in the range of 50).

Splice is O(N) only if you require that the Perl array be optimized for random access. If you're willing to allow for disjoint arrays and do some calculations that can be a bit fiddly, then you can make splice O(1) and random access O(1) (but potentially slower than it is right now).

[samtregar]

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

[gamache]

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