3 ms·
Using linked-list is not such an issue if nodes are not allocated with the general purpose allocator, and instead are allocated from a pool of memory addresses
by enqk 10y ago
Using linked-list is not such an issue if nodes are not allocated with the general purpose allocator, and instead are allocated from a pool of memory addresses next to one another.
- goldenkey 10y agoThen there's no point of using a linked list... A linked list is literally to connect distant memory addresses.
- enqk 10y agoSuch a linked-list using a linear pool of nodes is still useful if your algorithm makes many inserts and/or removals. The leap you're making here is about how distant the memory addresses should be in general. This is entirely dependent on your problem and your data-set.
- goldenkey 10y agoA skiplist array is the proper structure to use. A linked list is never the right structure for a local block of memory.
- cyphar 10y agoRight, but then you get fragmentation in the allocator unless all you're doing is stack operations (in which case you might as well use an array). Once you get fragmentation, you have the same problem as with any other linked list setup.