Project Nayuki

AVL tree list

Lists (or sequences) are a ubiquitous abstract data type (ADT) 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 Θ(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 Θ(1) time complexity and avoid the ones that take Θ(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 a self-balancing tree structure – such as an AVL tree, red-black tree, or B-tree – it is possible to implement a list that can access and modify single elements in just Θ(log n) worst-case 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 Θ(n) Θ(n) Θ(1) Θ(1)
Linked list Θ(1) Θ(n) Θ(1) Θ(n)
Balanced tree Θ(log n) Θ(log n) Θ(log n) Θ(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 Θ(n log n) time to build up this list of n elements, whereas an array-based list takes a terrible Θ(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().

  • AvlTreeList.ts
    The public API is identical to the hand-written JavaScript version.
  • Reuse the test infrastructure from the JavaScript version

When this TypeScript code is compiled down to JavaScript, it can be used as a drop-in replacement for the hand-written JavaScript version of this library. However, the internals have been majorly reworked to use ECMAScript 2015 (ES6) features like classes, let/const, and arrow functions. Also, the classes, fields, and methods were rearranged to satisfy the static type checks strictly.

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>. Currently no iterator is implemented.


The struct AvlTreeList has an interface similar to std::vec::Vec<T>. An immutable reference iterator is supported.

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