So this is actually not a problem so much for removals, because it evicts records from the chain immediately. Only records currently referenced by iterators will not get GCd, and work as "re-entry" points for those iterators to get back into the main chain. There is a case where lots of records are removed sequantially from the chain, creating a large list of deleted records the iterator has to move through. In reality, the chance of that happening vs. random removal is very small.

For additions, there is a real issue like you point out. I'm not super worried about it for this particular application, but I think we may want to make a not of it in the javadoc to highlight that you may see poor performance if you do a very large amount of inserts after grabbing an iterator. 

Perhaps revisit and alter or provide an alternative data structure if we find this to be an issue?