Hacker News Reader

HNHacker News

Top New Best Ask Show Jobs

Comment by im3w1l | Hacker News Reader

Parent Full thread

im3w1l·

> I wrote the inner loop of the C to operate on a linked list of blocks

Linked lists are slow...

View on HN

Linked list has extremely fast prepend/insert/delete operations compared to an array!

Not really. Depends how big your list is. If the answer is "not really that big" then cache misses and memory non-locality can cause linked lists to be less efficient. Besides, arrays actually have the same amortized time complexity as lists for dequeue operations. It's just in-the-middle deletions and insertions that can cause problems in arrays.

Using linked-list is not such an issue if nodes are not allocated with the general purpose allocator, and instead are allocated from a pool of memory addresses next to one another.

Right, but then you get fragmentation in the allocator unless all you're doing is stack operations (in which case you might as well use an array). Once you get fragmentation, you have the same problem as with any other linked list setup.

Then there's no point of using a linked list... A linked list is literally to connect distant memory addresses.

Such a linked-list using a linear pool of nodes is still useful if your algorithm makes many inserts and/or removals.

The leap you're making here is about how distant the memory addresses should be in general.

This is entirely dependent on your problem and your data-set.

A skiplist array is the proper structure to use. A linked list is never the right structure for a local block of memory.

But it has really slow iteration time, due to pointer indirection and cache misses.

There are very few usecases where linked lists are really the best choice:

https://www.youtube.com/watch?v=fHNmRkzxHWs&list=PL8N1fQK8Lw...

Reply on news.ycombinator.com