Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re^3: OOP/Linked List Question

by BrowserUk (Pope)
on Feb 08, 2005 at 02:26 UTC ( #428889=note: print w/replies, xml ) Need Help??

in reply to Re^2: OOP/Linked List Question
in thread OOP/Linked List Question

Instead of shifting all the list elements up or down, I would prefer to just delete a node an update a pointer.

How big is your list?

I ask for two reasons:

  1. If your list is large, using hashes or arrays to create your linked list will cost you lots of memory.
  2. Despite it's O(N) credentials, splice is remarkably adept at inserting things into the middle of even fairly long ( < ~ 20,000 elements ) lists.

And sometimes, the easy option is good enough. If your list is long enough for the cost of spliceing to become a problem, then you will also be approaching that point at which contructing linked lists from either hashes or arrays starts to consume very large volumes of memory.

Using a heap, or even a string-based list may prove to be fast enough whilst keeping your memory consumption with the range of sanity.

Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.

Replies are listed 'Best First'.
Re^4: OOP/Linked List Question
by hok_si_la (Curate) on Feb 08, 2005 at 04:11 UTC

    The list in my future code would be dynamic in size, and would contain anywhere from 50-1500 elements. I certainly obtained a ton of good advice on the topic. I need to consult my old operation cost charts from school, and play with a few of the ideas to decide which data type would be a best fit for my app. I am really looking forward to getting this running.


      Well, have fun. Just remeber that O-notation comparisons of different algorithms general carry an unstated "all other things being equal" clause.

      That is, an O(N) algorithm written in C (like splice), may outform a O(1+a few bits) algorithm written in Perl, if N is fairly small (and 50-1500 is small in this context) and those "few bits" consitute several lines of Perl.

      Examine what is said, not who speaks.
      Silence betokens consent.
      Love the truth but pardon error.

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (5)
As of 2018-04-19 19:48 GMT
Find Nodes?
    Voting Booth?