Exploring the .NET CoreFX Part 13: ImmutableList is an AVL Tree

This is part 13 of my Exploring the .NET CoreFX Series.

Most implementations of IList, including System.Collections.Generic.List, are dynamic arrays. System.Collections.Immutable.ImmutableList is different — it is an AVL tree. This results in significantly different performance characteristics:

  List ImmutableList
Indexing O(1) O(log n)
Append O(1) average, O(n) worst-case O(log n)
Insert at arbitrary index O(n) O(log n)
Remove O(n) O(log n)
Memory layout Contiguous for value types Non-contiguous

The data structure behind ImmutableList was likely chosen so that modifications to the list are non-destructive and require minimal data copying.

Here’s a visual representation of what List and ImmutableList look like behind the scenes:

List ImmutableList
List l = new List();
Array0
ImmutableList l = ImmutableList.Create();
Empty
l.Add(1);
Array1
l = l.Add(1);
1
l.Add(2);
Array2
l = l.Add(2);
2
l.Add(3);
Array3
l = l.Add(3);
3
l.Add(4);
Array4
l = l.Add(4);
4

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s