Project Nayuki

AVL tree list

Lists (or sequences) are a ubiquitous abstract data type in computer science. The two classic ways to implement a list are the array and the linked list. While each one has its own advantages, each has some operations with the slow O(n) time complexity.

In most applications, it’s possible to use the appropriate data structure so that you only need to use the operations that have the fast O(1) time complexity and avoid the ones that take O(n) time. But in applications that require both fast random access and insertion/removal of elements anywhere in the list (especially in the middle), neither the array nor the linked list is appropriate.

By using self-balancing trees – such as AVL trees, red-black trees, or B-trees – it is possible to implement a list data structure that can access and modify single elements in just O(log n) time, where n is the current size of the list.

Here is a summary of the trade-offs in time complexity:

Data structure Insert/remove
at beginning
at middle
at end
at middle
Array O(n) O(n) O(1) O(1)
Linked list O(1) O(n) O(1) O(n)
Balanced tree O(log n) O(log n) O(log n) O(log n)

Notes about the table:


To demonstrate the power of the AVL tree list, we test a scenario that works badly for a dynamic array. We pick a size n, start with an empty list, and repeatedly insert an element into the current middle of the list n times. In Java code it would look like this:

List<Object> list = new AvlTreeList<>();
for (int i = 0; i < n; i++)
    list.add(i / 2, null);

The AVL tree list takes O(n log n) time to build up this list of n elements, whereas an array-based list takes a terrible O(n2) time to do the same task.

Java timings

JavaScript timings

Note: Java benchmarking was performed on Oracle Java 1.8.0 Update 45 (64-bit). JavaScript benchmarking was performed on Mozilla Firefox 46.0.1 (32-bit). The CPU was Intel Core i5-4690 (Haswell) 3.50 GHz and the OS was Windows 8.1 Pro (64-bit).

Source code

Java (SE 7+)

The class AvlTreeList implements java.util.List. You can use it as a drop-in replacement anywhere you use a List – though only rare situations need to use an AvlTreeList instead of the commonly used ArrayList.

The iterator is not fail-fast unlike the ones in the Java collections framework. Take care to not modify the list when iterating over it.

Python (compatible with 2 and 3)

This implementation has an interface that mimics the built-in list type.

C++ (C++11 and above)

The class AvlTreeList has an interface similar to std::vector. Currently no iterator is implemented.


The class AvlTreeList has some methods that are idiosyncratic and some that imitate the native Array class. The full set of methods is: length, get(), set(), insert(), remove(), clear(), iterator(), toArray(), push(), shift(), pop(), slice(), splice(), forEach().

C# (.NET 4.0+)

The class AvlTreeList almost implements the System.Collections.Generic.IList<T> interface. It can be used as a substitute for the commonly used List<T>.

License: MIT (open source)

One application idea for the AVL tree list is to be the backing store for a scrollable graphical user interface that displays many thousands of items and allows the user to insert/edit/remove any item in the list (kind of like Windows Explorer or a big photo collection organizer).


More info