3 ms·
I'm wondering why GapList is slower than LinkedList on random add. The LinkedList is constant time, the GapList has to copy data around. It might be due to cac
by DennisP 15y ago
I'm wondering why GapList is slower than LinkedList on random add. The LinkedList is constant time, the GapList has to copy data around.
It might be due to caching, but even so it's going to depend on how big the data is. When the data's bigger than cache and the GapList is copying large amounts of data for every random insert, the O(1) linked-list insert is going to beat it.
Or maybe he's inserting to an indexed location, and counting the time required for the LinkedList to traverse to that location.