4 ms·
Linked list has extremely fast prepend/insert/delete operations compared to an array!
by reikonomusha 10y ago
Linked list has extremely fast prepend/insert/delete operations compared to an array!
- dalailambda 10y agoBut it has really slow iteration time, due to pointer indirection and cache misses.
- cyphar 10y agoNot really. Depends how big your list is. If the answer is "not really that big" then cache misses and memory non-locality can cause linked lists to be less efficient. Besides, arrays actually have the same amortized time complexity as lists for dequeue operations. It's just in-the-middle deletions and insertions that can cause problems in arrays.
- enqk 10y agoUsing 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.
- adrianN 10y agoThere are very few usecases where linked lists are really the best choice: https://www.youtube.com/watch?v=fHNmRkzxHWs&list=PL8N1fQK8Lwr-Ytyp-0UffiFCw9aB5xMgD https://www.youtube.com/watch?v=fHNmRkzxHWs&list=PL8N1fQK8Lw...