Java has a lock-free concurrent skip list in the ConcurrentSkipListMap class [1]. Herlihy et al. claim that existing skip list algorithms (including the Java im

Java has a lock-free concurrent skip list in the ConcurrentSkipListMap class [1]. Herlihy et al. claim that existing skip list algorithms (including the Java implementation) are complicated, and instead provide a supposedly faster implementation [2]. The two techniques they use are: - Optimistic traversal of lists without grabbing a lock: Only when it arrives at the item being seeked, it grabs the lock and validates that the list is unchanged. - Lazy deletion: marking a node as deleted and removing it from the list later. [1] https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListMap.html https://docs.oracle.com/javase/8/docs/api/java/util/concurre... [2] http://people.csail.mit.edu/shanir/publications/LazySkipList.pdf http://people.csail.mit.edu/shanir/publications/LazySkipList...