Nondestructive lists in JavaScript: a cheap hack

Let’s say you are programming in JavaScript but you are used to linked lists with their nondestructive O(1) operations. You could code up linked lists, but it’s a bunch of code and the overhead of abstraction is a bit high, so you might end up being slower anyway. What to do?

Here’s a simple hack: represent your list as an array of elements a in reverse order, along with a separate length n. The list elements are the array elements (a[n-1],a[n-2],...,a[0]). Any additional elements in the array are ignored and may be part of other lists. With this representation, the main list operations are easy to implement:

  • head: a[n-1] (remember, the elements are stored in reverse order)
  • tail: n-- (Now the same array a represents a shorter list!)
  • cons: if n equals the array length, just push the element (e) onto the end of the array and increment n. Otherwise, copy the array:
    • if (n != a.length) a = a.slice(0, n);
      a.push(e); n++;
  • iteration over list: loop over the elements from n-1 down to 0:
    • for (let i = n-1; i >= 0; i--) { const e = a[i]; ... }
  • map:
    • a.slice(0, n).map(f)

Obviously, this implementation of cons isn’t asymptotically as fast in the worst case as a real linked-list cons, but for a lot of programs, the slice case will not happen often enough to outweigh the performance win from using JavaScript’s built-in arrays. (And note that push takes amortized O(1) time if implemented correctly.)

This is a very simple idea and surely, many people have used it in the past in various settings, but I thought I’d write it down anyway in case it might be useful to others. Enjoy!