I have noticed that most functional languages employ a singly-linked list (a "cons" list) as their most fundamental list types. Examples include Common Lisp, Haskell and F#. This is different to mainstream languages, where the native list types are arrays.
Why is that?
For Common Lisp (being dynamically typed) I get the idea that the cons is general enough to also be the base of lists, trees, etc. This might be a tiny reason.
For statically typed languages, though, I can't find a good reasoning, I can even find counter-arguments:
- Functional style encourages immutability, so the linked list's ease of insertion is less of an advantage,
- Functional style encourages immutability, so also data sharing; an array is easier to share "partially" than a linked list,
- You could do pattern matching on a regular array just as well, and even better (you could easily fold from right to left for example),
- On top of that you get random access for free,
- And (a practical advantage) if the language is statically typed, you can employ a regular memory layout and get a speed boost from the cache.
So why prefer linked lists?
an array is easier to share "partially" than a linked list
needs clarification as to what you mean. Due to their recursive nature, the opposite is true as I understand it - you can partially share a linked list easier by passing along any node in it, while an array would need to spend time making a new copy. Or in terms of data sharing, two linked lists can point to the same suffix, which just plain isn't possible with arrays.