justin = { main feed , music , code , askjf , pubkey };
Ask Justin Frankel
No reasonable question unanswered since 2009!

Suggested topics: programming, music, sleep, coffee, etc.

Note: please do not ask questions about REAPER features, bugs or scheduling, use the forums instead.

Name: Ask: Human (enter yes):
[back to index] | [unreplied] | [replied] | [recent comments] | [all]
Question: Re: linked lists. Could you explain why the statement "you need...insertions will have problems" is false? If this is false then there is an assumption that arrays do better -- which isn't true if the insertions are not pushed at the back of the array. plus at every given time you might have a memcpy penalty if there isn't enough headroom, etc.
Asked by gio (94.66.83.x) on June 23 2013, 8:47am
Reply on June 23 2013, 10:27pm:
    I think his assertion that a doubly-linked list was necessary for random insertions was making a lot of assumptions, particularly that the random-insertion algorithm wasn't really aware of the structure of the list (basically, he's saying that you'd need the most general form of doubly-linked list to be used as-is for the algorithm, otherwise you have to actually write code that traverses the list to decide where to insert, etc).

    Regarding the performance penalties of having to shuffle the list around due to insertions, his point is that those penalties are actually relatively low (because of CPU caches etc) compared with having to traverse a list (which most of the time will thrash CPU caches and will in general touch a lot more memory due to overhead of the list structures).

    The real thing to take away from this, though, is that you should think about the data structures you are using, and think about how they will be used, before you decide which to use. Also, sometimes writing versions of algorithms that are optimized for a particular data structure (such as code that inserts at a random point in a singly-linked list, and does it with a single pass, vs a more braindead approach which would require a doubly-linked list), can have value. Having said that, though, linked lists can and do have plenty of uses where they DO perform well, even if they don't in this example.
Comment:
    Your Name:   -- Site Owner's Name:  (for human-verification)

    Comment:
[back to index] | [unreplied] | [replied] | [recent comments] | [all]
Copyright 2025 Justin Frankel. | RSS