6 ms·
The nuance you're missing here is that the author is always inserting at the front of the arraylist. So even though the list grows dynamically, it still needs t
by bfstein 10y ago
The nuance you're missing here is that the author is always inserting at the front of the arraylist. So even though the list grows dynamically, it still needs to move every value one spot over.
e.g. arraylist: [0][1][2][3][ ]
Even though there is space left in the array, we still need to move all the values one index to the right to be able to insert at the front, which takes O(n) time. In contrast, inserting at the front of a linked list is simply a matter of moving pointers and therefore constant time.
- gens 10y agoCan't you just imagine it is reversed, where the_array[num_things-1] is the first ?
- DougBTX 10y agoYes, then it would be a discussion about append performance instead of insert performance. Might be handy to do if you know that all the changes to an array will be inserts at the front, then you can just write the array in reverse and also read in reverse. But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data. The OP is discussing inserts at the start just because it is the worst-case scenario for arrays, then a positive result will still be true if some of the inserts are in the midddle or even near the end.
- fixerfrasse 10y agoAfaik, if you read in reverse, then you will miss cache optimization since it only works forward.
- thaumasiotes 10y ago> But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data. This is true if you already have a reference to the middle of the list. If you don't (say, because you want to insert while preserving the fact that the list is sorted), then inserting into a linked list is O(n) just like the array is.
- wolf550e 10y agoMemory reads and memory writes are not the same. Linked list insert in the middle needs to do only O(1) writes. But because linked lists preclude memory prefetch, they should not be used these days.
- hinkley 10y agoStay strong.
- hinkley 10y agoThe awful thing about writing benchmarks is that if you don't give the worst case example, people give you shit for coming up with metrics that say whatever you want to say. If you give metrics for the case that should be worst for your argument, people give you shit about using such a stupid example. There's no way to avoid someone giving you grief no matter what you do.
- andrewflnr 10y agoUm, give both?
- hinkley 10y agoThen both groups agree that your examples are terrible ;)
- SapphireSun 10y agoSome languages, such as Perl, start the array in the middle to avoid exactly this situation.