Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

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?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://574859]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (10)
As of 2018-03-20 22:31 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (260 votes). Check out past polls.