# F# list

June 03, 2020

## List data structure and common operations

`F#`

list is a linked list, where each node has a link to the next node. It is also immutable. See mastering `F#`

lists. Available operations:

`Cons`

- add an element to the beginning of a list.`'a –> 'a list –> 'a list`

, constant time`O(1)`

. Example`1::[2..4]`

.`Concat`

- join two lists together.`'a list * 'a list -> 'a list`

,`O(n)`

where`n`

is the length of the first list. Example:`[2; 3; 4] @ [5 .. 7]`

## Avoid @

Avoid list concatenation with `@`

, from SO:

In F# the list type is implemented as a singly linked list. Because of this you get different performance for x @ y and y @ x if x and y are of different length. That’s why your seeing a difference in performance. (x @ y) has running time of X.length.

The append operator (`@`

) creates a new list by concatenating two lists, so appending a shorter list to a longer list is slower than appending a longer list to a shorter list, since it needs to copy the first list (lists are immutable, duh…).

## Correct way to build a list

To build a list prepend the new data to the front and then reverse (if e.g. using `List.foldBack`

).

See SO Why can you only prepend to lists in functional languages?.

And why not just use doubly-linked list on SO, spoiler alert - requires mutability.