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
Insert/remove
at middle
Insert/remove
at end
Get/set
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:

Benchmark

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

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

This implementation has an interface that mimics the built-in list type. Compatible with Python 2 and 3.

C++

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

JavaScript

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().

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).

Notes

More info