Comparing F# List to .NET List<T>

The List is similar to .NET List, because they both have indexes and the same methods as well, although the semantics are different.

The List is implemented as a single linked list, not as the List<T> in .NET BCL. This linked list implementation is faster than List<T>. The List can be stored recursively by easily using F# head::tail syntax.

A single linked list means that each element of the list contains a portion of property that points to the next element of the list, as illustrated here:

F# List is efficient and faster than List<T> in a sense that a single linked list always guarantees that any operations that access only the head of the list are O(1), and element access is O(n). It is ordered that each element can have a pointer to the next element.

The apparent advantages of F# List over .NET List<T> are as follows:

• F# List is immutable. It can be considered as a persistent data structure when combining with List.

• The nature...