Hacker News Reader

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

View on HN

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.

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

Reply on news.ycombinator.com