Hacker News Reader

Comment by adrianN | Hacker News Reader

I've spent the last year wondering why compiling and linking took so long. Now I've been looking at the source of our toolchain and see that not only does it use linked lists for everything, it also appends everything at the end -- without storing a pointer to the last element in the head. Fixing the O(n) append improves performance a lot.

View on HN

I was using linked-list to append things to the head, which was supposed to be it's optimal use case. I've refactored the function it's calling to take an n argument, which means to leave first n holes in the returned vector for the calling function to fill.

I had also used a linked list of characters to represent strings to iterate through them one by one. This was very slow compared to iterating through an array.

Linked-lists were supposed to be O(1) inserting at the head, and O(n) iterating through it. However, it's no match against array O(1) assignment and O(n) array iteration.

Big-O doesn't care about constant factors, but in practice you do. Linked lists are one of the shittiest data structures on modern computers because random memory access is one of the most expensive operations you can do. In fact, on modern machines a random access is not an O(1) operation, it's O(log n), due to the TLB.

I am not 100% sure I understand your description, but if you want standard drop-in-replacement for linked lists, you want the array deque. It can do fast insertion and deletion at both ends. The only operation it cannot do is O(1) deletion of any element, even in the middle, that you have an iterator to. But in my experience it is rare that you need that.

Reply on news.ycombinator.com