Question: **What happens in memory when working with immutable lists?**

Is a Deep Copy performed when invoking List.Append?

What is the Big-O Notation to describe this operation for F# Lists?

Is it still O(1) when adding a node to the end of a list?

If not, then why would using an immutable list be useful if using an immutable list violates the intended performance of a linked list?

**Consider the following statement:**

```
_modules <- _modules |> List.append moduleItems

```

**Source Code:**

```
type CreationViewModel() =
    inherit ViewModelBase()

    let mutable (_modules:Module list) = []

    member this.Modules
        with get()      = _modules
        and set(value)  = _modules <- value

    member this.Add moduleItem = 
        _modules <- moduleItem :: _modules

    member this.AddList moduleItems = 
        _modules <- _modules |> List.append moduleItems

```

Answer: 
When List.append is called, the items themselves aren't copied but the pointers is the first list need to be.

This is because the list structure looks like

```
a::b::c::.....

```

so when you join two lists you go from

```
a::b::c::d::[] and e::f::g::h::[]

```

to

```
a::b::c::d::e::f::g::h::[]

```

which requires rewriting the first list.

As a result it is `O(n)` where `n` is the size of the first list
F# lists are singly-linked, much like the following definition.

```
type SList<'a> =
| Cons of 'a * SList<'a>
| Nil

```

So, adding a new element to the head of the list is done in O(1) time, by creating a new head element and having it reference the existing tail elements(s).

```
> Cons ( "something", Nil );;
val it : SList<string> = Cons ("something", Nil)

```

Which could be used to create a list as follows:

```
> let test = Cons (1, Cons (2, Cons (3, Nil)));;
val test : SList<int> = Cons (1,Cons (2,Cons (3,Nil)))

```

However, adding a new element to the end of the list requires traversing the entire list to find the end, which takes O(N) time, in order to have the last node reference a new last node.

A trivial implementation could be defined as follows. Even though it copies the list twice, it is still O(N) because the cost scales linearly with the size of the list.

```
let rec fold f state = function
    | Cons(v,xs) -> fold f (f state v) xs
    | Nil -> state

let reverse xs =
    fold (fun st v -> Cons (v, st)) Nil xs

let append x xs =
    reverse ( Cons (x, (reverse xs) ) )

```

Note that lists defined as above are immutable.

Adding a new element at the head references an existing tail which is never modified, so the tail can be safely shared amongst multiple lists (each with different head elements).

Appending an element to the end of a list results in a new list in order to preserve immutability of the original list: changing the last element to point to a new last element means updating the previous element to point to the updated element, and so on up for every element in the list.

**So why aren't F# lists doubly-linked?**

Aside from historical reasons (ML only provides singly-linked lists), I believe an immutable doubly-linked list implementation would require copying the entire list when adding elements at *either* end, due to the need to adjust the next and prev elements of every node for either operation, thus *always* costing O(N) time.

An immutable singly-linked list only pays O(N) when appending to the end, so is generally more efficient.

Because of that last point, code which works with immutable lists will generally avoid appending multiple elements sequentially, which is O(M\*N). Instead, such code generally reverses the list for O(N) cost, adds several elements to the head (backwards end) for O(1) cost, then reverses the result to get back the original ordering, making for an overall O(N) operation.