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?

  • 5
    Coming from the comments on @sepp2k's answer, I think 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.
    – Izkata
    Commented Jan 29, 2012 at 15:19
  • If an array defines itself as an offset,length,buffer triple, then you could share an array by making a new one with offset+1,length-1,buffer. Or have a special type of array as the subarray. Commented Oct 17, 2012 at 7:01
  • @Izkata When talking about arrays, we rarely just mean a buffer such as a pointer to the start of contiguous memory in C. We usually mean some sort of structure which stores the length and a pointer to the start of a wrapped buffer. Under such a system, a slicing operation can return a subarray, whose buffer pointer points mid-way into the buffer (at the first element of the sub array), and whose count is such that the start+count gives you the last element. Such slicing operations are O(1) in time and space
    – Alexander
    Commented Sep 4, 2017 at 16:50
  • For the topic of functional data structures in general, you may be interested in Phil Bagwell's data structures. These are the basis for the vector,set,map used in Clojure, Scala, Haskell, etc: stackoverflow.com/questions/16270598/…. Chris Okasaki also wrote a book called Purely Functional Data Structures, but this predates Bagwell's tries.
    – Riley
    Commented Jun 21, 2020 at 16:05
  • Here is a gentle introduction to the inner workings of Clojure's vector: hypirion.com/musings/understanding-persistent-vector-pt-1
    – Riley
    Commented Jun 21, 2020 at 16:08

5 Answers 5


The most important factor is that you can prepend to an immutable singly linked list in O(1) time, which allows you to recursively build up n-element lists in O(n) time like this:

// Build a list containing the numbers 1 to n:
foo(0) = []
foo(n) = cons(n, foo(n-1))

If you did this using immutable arrays, the runtime would be quadratic because each cons operation would need to copy the whole array, leading to a quadratic running time.

Functional style encourages immutability, so also data sharing; an array is easier to share "partially" than a linked list

I assume by "partially" sharing you mean that you can take a subarray from an array in O(1) time, whereas with linked lists you can only take the tail in O(1) time and everything else needs O(n). That is true.

However taking the tail is enough in many cases. And you have to take into account that being able to cheaply create subarrays doesn't help you if you have no way of cheaply creating arrays. And (without clever compiler optimizations) there is no way to cheaply build-up an array step-by-step.

  • That's not true at all. You can append to arrays in amortized O(1).
    – DeadMG
    Commented Jan 29, 2012 at 2:28
  • 10
    @DeadMG Yes, but not to immutable arrays.
    – sepp2k
    Commented Jan 29, 2012 at 2:30
  • "partially sharing" - I think both that two cons lists can point to the same suffix list (dunno why you'd want this), and that you can pass a midpoint instead of the beginning of the list to another function without having to copy it (I've done this many times)
    – Izkata
    Commented Jan 29, 2012 at 5:00
  • @Izkata The OP was talking about partially sharing arrays though, not lists. Also I've never heard what you're describing referred to as partial sharing. That's just sharing.
    – sepp2k
    Commented Jan 29, 2012 at 5:19
  • 1
    @Izkata The OP uses the term "array" exactly three times. Once to say that FP languages use linked lists where other languages use arrays. Once to say that arrays are better at partial sharing than linked lists and once to say that arrays can be pattern matched just as well (as linked lists). In all cases he's contrasting arrays and linked lists (to make the point that arrays would be more useful as a primary data structure than linked lists, leading to his question why linked lists are preferred in FP), so I don't see how he could be using the terms interchangeably.
    – sepp2k
    Commented Jan 29, 2012 at 7:30

I think it comes down to lists being rather easily implemented in functional code.


(define (cons x y)(lambda (m) (m x y)))


data  [a]  =  [] | a : [a]

Arrays are harder and not nearly as pretty to implement. If you want them to be extremely fast then they'll have to be written low-level.

Additionally, recursion works much better on lists than arrays. Consider the number of times you've recursively consumed/generated a list vs indexed an array.

  • I wouldn't say it's accurate to call your scheme version an implementation of linked lists. You won't be able to use it to store anything but functions. Also arrays are harder (impossible actually) to implement in any language that doesn't have built-in support for them (or memory chunks), while linked lists only require something like structs, classes, records or algebraic data types to implement. That's not specific to functional programming languages.
    – sepp2k
    Commented Jan 29, 2012 at 2:29
  • @sepp2k What do you mean "store anything but functions"?
    – Pubby
    Commented Jan 29, 2012 at 2:54
  • 1
    What I meant was that lists defined that way can't store anything that's not a function. That's not actually true though. Dunno, why I've thought that. Sorry about that.
    – sepp2k
    Commented Jan 29, 2012 at 3:00

A singly-linked list is the simplest persistent data structure.

Persistent data structures are essential for performant, purely functional programming.

  • 1
    this seems to merely repeat point made and explained in the top answer that was posted over 4 years ago
    – gnat
    Commented Jul 5, 2016 at 13:41
  • 3
    @gnat: The top answer doesn't mention persistent data structures, or that singly linked lists are the simplest persistent data structure, or that they are essential for performant purely functional programming. I can find no overlap with the top answer at all. Commented Jul 5, 2016 at 18:16

You can use Cons nodes easily only if you have a garbage collected language.

Cons Nodes match a lot with the functional programming style of recursive calls and immutable values. So it fits well into the mental programmer model.

And don't forget historical reasons. Why are they still called Cons Nodes and worse still use car and cdr as accessors? People learn it from text books and courses and then use it.

You are right, in the real world arrays are much easier to use, consume only half the memory space and are much performanter because of cache level misses. There is no reason to use them with imperative languages.


Linked lists are important for the following reason:

Once you take a number like 3, and convert it to successor sequence like succ(succ(succ(zero))), and then use substitution to it with {succ=List node with some memory space}, and {zero = end of list}, you'll end up with a linked list (of length 3).

The actual important part is numbers, substitution, and memory space and zero.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.