3 ms·
Arrays are fast for getting random elements and inserting/deleting at the end (amortized), but slow for inserting/deleting in the middle. Linked lists are fast
by nayuki 10y ago
Arrays are fast for getting random elements and inserting/deleting at the end (amortized), but slow for inserting/deleting in the middle.
Linked lists are fast for inserting/deleting/getting at the beginning and end, but slow for random access for anything in the middle.
So far, that's what the article covered. Now if you want fast random insertions/deletions and fast random access, this is possible with balanced trees. A tree-based list can support all single-element operations in O(log n) time. Sample code: https://www.nayuki.io/page/avl-tree-list https://www.nayuki.io/page/avl-tree-list
- edejong 10y agoThat's not what the article is about nayuki. The author of the article makes and proves a claim that arrays are faster than linked lists regardless of the insertion point. The metrics presented clearly show this. The reason for this abnormality is cache locality (there are other reasons, which I will not go into right here). Balanced trees can be pretty slow in fact. After some operations, a tree structure can become quite fragmented in memory, leading to many cache misses. In my experience, it is often faster to work with arrays instead of trees when processing in memory. However, using external storage, a b-tree often introduces quite some performance gain.