Exploring the .NET CoreFX Part 13: ImmutableList is an AVL Tree
Exploring the .NET CoreFX .net core csharp system.collections.immutable
Published: 2015-01-13
Exploring the .NET CoreFX Part 13: ImmutableList is an AVL Tree

This is part 13/17 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(); ImmutableList l = ImmutableList.Create();
l.Add(1); l = l.Add(1);
l.Add(2); l = l.Add(2);
l.Add(3); l = l.Add(3);
l.Add(4); l = l.Add(4);