> Compared to a contiguous memory structure such as a C-style array (and its object oriented derivatives: vector, ArrayList, etc), iterating a linked list is fr

> Compared to a contiguous memory structure such as a C-style array (and its object oriented derivatives: vector, ArrayList, etc), iterating a linked list is frequently 3-10x slower. Careful. I've actually done some recent benchmarking (in OCaml, not Haskell), and the results don't necessarily bear that out, especially if you need dynamic arrays rather than static arrays. A particular use case is the creation of dynamically sized temporary data. A bump allocator will put list nodes in a contiguous section of memory, but does not require resizing. A dynamic array may be resized several times, requiring additional copying and allocations (and possibly expensive major heap allocations). As a result, the relative performance difference not only may not be as dramatic, but can actually swing in the favor of linked lists. Note that I'm not saying that performance degradation due to poor memory locality of linked lists won't happen, just that there are plenty of use cases where this is not a problem.