Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: How do I insert an element into an arbitrary (in range) array index?

by jreades (Friar)
on Sep 06, 2000 at 01:17 UTC ( [id://31174]=note: print w/replies, xml ) Need Help??


in reply to How do I insert an element into an arbitrary (in range) array index?

Algorithms with Perl (call it the Wolf book) covers just this issue in one of the early chapters

Basically, you have two choices: an array or a linked list.

The choice between these two will depend on, primarily, the size of the list.

Splice(): As lhoward indicated, inserting a value at an aribtrary index using splice is expensive.

The time for each splice() increases at a constant rate as your list grows in size. With splice(), although from the user end it looks like you just inserted something, to memory you were creating and manipulating multiple arrays (basically, a one or more copies of your original array) in memory.

This may not be a problem if your array is 10, 20, or even 100 items, but if it's 10,000 or 100,000 you're going to see a real performance hit. This brings us to...

Linked Lists: perhaps the easiest (and probably least accurate) way to describe it is to say that linked lists are array-like.

The basic principle is that you have a value (call it 'x') and a pointer (reference, call it 'a') to the next item (call it 'y') in the linked list (assuming a simple linked list).

So a(x) -> b(y) -> c(z) and so on...

Suddenly, we've radically altered the tradeoffs... To add a value q between x and y I just need to change the pointers as follows:

a(x) -> e(q) -> b(y) -> c(z) and so on...

The cost of inserting values at arbitrary locations is reduced to, I believe, O(1) -- I can insert anywhere in the list just by rearranging the pointers and that is essentially a constant time operation regardless of how big my list is...

Of course, now I might have some trouble *finding* the element, but that's another question entirely...

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://31174]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others taking refuge in the Monastery: (5)
As of 2024-03-29 11:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found