Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re^2: Linked lists as arrays: inserting values

by tilly (Archbishop)
on Sep 26, 2006 at 04:33 UTC ( #574859=note: print w/ replies, xml ) Need Help??


in reply to Re: Linked lists as arrays: inserting values
in thread Linked lists as arrays: inserting values

Absolutely the correct answer.

Building a large data set by repeatedly splicing into the middle is indeed O(n*n) while a linked list is O(n). But that is O(n*n) with a small constant term versus O(n) with a big term. Unless your dataset is very large, the native array approach will be far faster. Just consider the cost of accessing the next element. With the native approach it will be a pointer lookup versus having to make a function call (and Perl function calls are slow).

Furthermore a final reason not to use linked lists in Perl. Unless you are very careful, the linked lists will have circular data structures (each item points to the next which points to the previous). Therefore you are either in the business of having to do memory management yourself, or else you need to add yet another layer of slow indirection. Either way you've added more complexity, more room for bugs, and have reduced your potential performance gains even more.


Comment on Re^2: Linked lists as arrays: inserting values

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (7)
As of 2014-07-31 22:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (254 votes), past polls