Hacker News Reader

An array can be used to efficiently simulate a linked list and other data structure, however. (Or an intrusive linked list may be embedded into the bucket structure like PHP, but this is less efficient with open addressing scheme which is nowadays better for cache locality.)

View on HN

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

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