4 ms·
Right. Like there are so many algorithms that I shudder to think about how you'd implement them without linked lists. Like...how about a buddy allocator? Sure y
by Sirened 4y ago
Right. Like there are so many algorithms that I shudder to think about how you'd implement them without linked lists. Like...how about a buddy allocator? Sure you could use a vector for each but you'd be copy and resizing huge swathes of memory constantly for very little gain. Use the right tool for the job!
- tsimionescu 4y agoThe thing is, the cost of copying memory is essentially the same as the cost of reading it, and linked lists force you to keep re-reading the same memory over and over (assuming random access). Adding an element in the middle of an array vs the middle of a linked list actually has the same asymptotic complexity (O(n)), but far better cache impact for the array (since moving a contiguous block of n/2 elements should only incur 1 cache miss, while reading n/2 randomly distributed nodes of the list will incur on average something like n/4 cache misses). Adding closer to the beginning of the linked list is faster, but adding close to the end of the vector is faster still, so overall with random access, the vector should win.
- halayli 4y agoI think you missed the point here. You don't use link lists when you are going to walk the list and insert in the middle or some random place. The only time you end up walking a link list in typical scenarios is when you want to print them out or some unimportant operation. Link list is used to hold relationship between nodes and when you are operating on that node the common patterns are remove and add it to another list, or re-add it on either side. Take a look at bsd or linux source for inspiration. A process struct has more than dozen member variables of node* type because the object ends up being in several lists like sched, signal queue, child threads etc.