3 ms·
> An array can be used to efficiently simulate a linked list That's obviously not what the OP meant. Also, I don't think there's an efficient way of implementi
by icholy 2y ago
> An array can be used to efficiently simulate a linked list
That's obviously not what the OP meant. Also, I don't think there's an efficient way of implementing deletes with an array backed linked list.
- mjevans 2y agoThat depends on what someone is willing to compromise. Extra space to point back at exactly that key (but that also needs to be updated each compaction?); personally I'd normally rather pay the lookup or key sort on iterator snapshot fee. An 'insert, or re-sorted order' side index which allows for nodes to be marked as 'deleted' (maybe nil / null, maybe a sentinel value meaning skip?); I might propose that to see if it fit the requirements well enough.
- icholy 2y ago... or just use a normal linked list with the existing entries like a sane person.