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) worstcase  O(log n) 
Insert at arbitrary index  O(n)  O(log n) 
Remove  O(n)  O(log n) 
Memory layout  Contiguous for value types  Noncontiguous 
The data structure behind ImmutableList
was likely chosen so that modifications to the list are nondestructive 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); 