CODEWITHSUNDEEP
f#
user2588666
user2588666

Reputation: 851

Why implement an immutable list as a linked-list?

According to F#'s list documentation:

Why not implement it contiguously in memory since it immutable and thus has a fixed size? Why ever use an F# list instead of an F# array?

Upvotes: 5

Views: 595

Answers (1)

Gus
Gus

Reputation: 26174

They serve different purposes, for instance:

You use an Array in F# to store big amounts of data that needs to be accessed randomly with relative low overhead.

A List in F# is useful when you need to accumulate something over iterations of a recursive function. Arrays don't play well here, since they have a fixed size.

With a list, you can prepend all elements of ListM (size M) to ListN (size N) in O(M) time. Similarly, you can prepend a single Element to any list in O(1) time.

Upvotes: 3

Related Questions