14 ms·
The answer could be 2x. Let's say you're in a 64 bit platform. Your linked list nodes consist of a next pointer and a 64 bit integer. If your linked list nodes
by onekorg 6y ago
The answer could be 2x. Let's say you're in a 64 bit platform. Your linked list nodes consist of a next pointer and a 64 bit integer.
If your linked list nodes are all allocated sequentially in memory then it'd only be 2x as slow as an array of 64 bit integers.
But maybe it's not fair to call sequentially allocated linked list a "trivial linked list".
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- koala_man 6y agoThis kind of CS-based rationalization is arguably another aspect of what the article comments on. I wrote a benchmark and found the difference in this case to be 3x-3.5x.