3 ms·
Is this a unrolled linked list implementation? https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list
by cristaloleg 10y ago
Is this a unrolled linked list implementation? https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list
- todd-davies 10y agoIt looks that way from looking at the README and skimming the code; I'd be interested to know if it differs somehow.
- Zekio 10y ago"Unrolled linked list, In this model, the maximum number of elements is 4 for each node." - wiki According to the README, it only uses 36 nodes for 10 Million records, so I guess it is like Unrolled linked lists but with a higher limit of elements per node?
- cristaloleg 10y agoIt's just a constant.
- ertucetin 10y agoList starts with array which has 10 elements(default just like ArrayList) unless you say otherwise(new GlueList(capacity)). You can say 'allocate me 10million elements' and there will be 1 node :)
- jdmichal 10y agoThere's nothing requiring that an unrolled linked list has a fixed number of elements per node. It's just easier to reason about the performance results by fixing the number. This looks like an unrolled linked list with variable elements per node, which allows it to do things like allocate a single node for an entire bulk add operation.