How should I sort a doubly linked list the D way?

Mirjam Akkersdijk noreply at
Tue Aug 13 22:19:15 UTC 2019

On Tuesday, 13 August 2019 at 21:11:41 UTC, H. S. Teoh wrote:
> A contiguous allocator doesn't help after the list has 
> undergone a large number of insertions/deletions, because of 
> fragmentation.
Fragmentation should not be an issue, I insist on keep using a 
DLL for the base structure in my application and create an array 
just for sorting operations. No new nodes are added and no nodes 
are permanently removed.

> You can still get a cache-efficient linked list by chunking. 
> [...]
I very much appreciate this thought, as I was thinking of adding 
such kind of cache to my implementation. It's still in the early 
stages and I have yet to see when this would make a considerable 
impact. I will remember this.

More information about the Digitalmars-d-learn mailing list