[icholy]

> 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]

That 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]

... or just use a normal linked list with the existing entries like a sane person.