Re:XOR Linked List
by dpark on Friday May 04, 2012 @09:47AM
(#3928313)
These seem like like related but distinct ideas. From what I understand, CDR coding is basically an optimization that replaces the entire list with an array. This has the effect that inserting elements involves an ugly and expensive indirection hack.
Unrolled linked list don't exhibit this behavior (though they have other drawbacks). Their behavior is closer to that of B-trees, where size-bounded multi-element nodes can be split and joined cheaply, which allows for cheap element insertion.
Unrolled linked list don't exhibit this behavior (though they have other drawbacks). Their behavior is closer to that of B-trees, where size-bounded multi-element nodes can be split and joined cheaply, which allows for cheap element insertion.