Garbage collectors are really nice for concurrent data structures, making lock-free algorithms very practical. Java's skip list does not require any locks for w

Garbage collectors are really nice for concurrent data structures, making lock-free algorithms very practical. Java's skip list does not require any locks for write, and requires essentially no synchronisation at all for reads (just suitable platform-dependent memory barriers). I believe reads are also wait free. There is a locality penalty for lookups, although I don't think this is core to skip-lists, just an impracticality of the Java language and how you can use its standard libraries. The variable size of the nodes is not a problem for the Java heap, due to how compacting garbage collectors work.