Linked lists are another way of getting a lot of the functionality of arrays. While arrays are like a box of ordered things, linked lists are like a chain. Her

Linked lists are another way of getting a lot of the functionality of arrays. While arrays are like a box of ordered things, linked lists are like a chain. Here's a model of a linked list. We start with an empty list represented by an empty array. [] In normal arrays we'd add a number by putting it into the array, like [1], but we'll do something a little weirder: [1, []] we build a new array which contains one value and the empty array. We add new elements in the same way [] [1, []] [2, [1, []]] [3, [2, [1, []]]] The final one there is a bit like the array [3,2,1], but seems to have a lot more ceremony. In any case, the values above model linked lists. Why would you use such a thing? Well, when you want to push a new value on to an array you may find (internally) that the array you have so far is too small. To fix this, you build a new, larger array and move all of the old elements to the new array plus the one new thing you've added. This can be expensive. With linked lists, adding a new element is always the exact same process. It is in this way faster and simpler. Of course, the downside of linked lists is that there is more overhead to, say, read the 10th element. In an array you can just do a[10], but in an linked list you must do a[0][0][0][0][0][0][0][0][0][1]. Obviously this involves much greater overhead. Linked lists are closely related to infinite streams, however. Sometimes they better model what you actually want to talk about—the idea of having a value "now" and some more values "in the future". They also are much more naturally implemented immutably and have a much more natural sense of a fold or reduction. So, as with all data structures, there's a tradeoff.