An efficient list implementation

Arne Andersson and Stefan Nilsson

We present an efficient implementation of the Java List interface, supporting all basic operations in O(log n) time on a list of size n. Our experiments confirm that the data structure is competitive also in practice.