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 selfbalancing trees – such as AVL trees, redblack trees, or Btrees – 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 tradeoffs 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:
This assumes the best implementation for a linked list, which would be a circular doubly linked list. A singly linked list with access only from the head would perform worse than what the table shows.
Array insertion at the end is O(1) if the array is preallocated with enough capacity. Otherwise it’s amortized O(1) if it’s a dynamic array that needs to expand.
The time complexities for the balanced tree data structures are for the worst case per operation (not probabilistic or amortized) – this is good compared to the expected O(log n) time complexity of skip lists.
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 arraybased list takes a terrible O(n^{2}) time to do the same task.
Note: Java benchmarking was performed on Oracle Java 1.8.0 Update 45 (64bit). JavaScript benchmarking was performed on Mozilla Firefox 46.0.1 (32bit). The CPU was Intel Core i54690 (Haswell) 3.50 GHz and the OS was Windows 8.1 Pro (64bit).
Source code
 Java

 AvlTreeList.java
 AvlTreeListTest.java (JUnit)
The class
AvlTreeList
implementsjava.util.List
. You can use it as a dropin replacement anywhere you use aList
– though only rare situations need to use anAvlTreeList
instead of the commonly usedArrayList
.The iterator is not failfast 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 builtin
list
type. Compatible with Python 2 and 3.  C++

The class
AvlTreeList
has an interface similar tostd::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
This topic is covered in Introduction to Algorithms (the CLRS textbook), in the chapter “Augmenting Data Structures”, in the section on dynamic order statistics and retrieval by rank.
The O(log n) time complexity for singleelement operations can also be achieved in the average case using skip lists, but this is a probabilistic data structure compared to the absolute guarantees provided by balanced trees.
All 3 classes of data structures in the table require O(n) time to search for a value to find its index in the list, but the tree structures can be augmented to do search in O(log n) time in a complicated way: Add a second balanced tree that is sorted by value and contains pointers to nodes in the primary tree; add parent pointers to each node in the primary tree so that when given a node, it’s possible to compute the node’s index in the list.
This discussion is about the time complexity of singleelement operations on a list ADT. It’s not clear how to insert a whole list into a list or remove a whole range in logarithmic time and also be able to access random elements in logarithmic time. This can be a research or implementation exercise for the reader.
Because the balanced tree only updates O(log n) nodes on every operation and the nodes don’t have parent pointers, it is possible to implement this in a pure functional programming language like Haskell; similarly in imperative languages it is possible to make a copyonwrite implementation so that no nodes are ever modified in place.
The Python package blist implements lists as balanced trees, just like my AVL tree list here.
The Apache Commons Collections library provides a TreeList class that achieves the same goals as my Java implementation.