About the ordered removal, if it's not very common, using tombstones (a constant to denote no element) is fine. Too many tombstones would need a compaction phas

About the ordered removal, if it's not very common, using tombstones (a constant to denote no element) is fine. Too many tombstones would need a compaction phase and still it'd work way better than a linked list. Personally I have not met a case where a random removal in the middle of a list is common -- b/c finding the needle is slow to begin with O(n). In such case linked hash sets are O(1) but way more memory intense (which is a very advanced linked list) That being said linked queues are great for concurrent lock free cases.