Building a List in JavaScript

Types in dynamic languages are confusing. JS arrays wrap your data in so many layers of abstractions that it is hard to know exactly what an array even is. A JS array might not even stay the same type, depending what you put into a JavaScript array, its actual internal can be everything from an array to a binary search tree.

Learning arrays are like those movies where a character realizes that they had the power inside themselves the whole time or that they are actually really an alien or a clone, or were dead the whole time. You can go your whole life not realizing what an array is until one day you realize it was a bunch of things all along. And that is why you never felt like it belonged and you were confused all the time. You were never an Array you were an Object.

Everything being an object can be hugely powerful, it means you don't have to worry about types of data ahead of time. You can just start throwing things into an object and no matter what the structure your data ends up being you get to keep the same API.

Arrays in JS are actually more like Lists. They expand and accept any type of data. They have checkmarks and some people use post it notes to keep track of them but some people prefer apps they never use and some people use calendars. Wait those are two different type of lists. I got distracted.

What is a List?

A List is like an array that can grow. A list has no fixed sized. Items in a list point directly to memory locations so lookup time is constant. Writing is typically linear. They are like arrays sorta, but not exactly.

One rarely encounters an actual List in JS because implementing one would be redundant. JS arrays provide all the features of a List and more. It would actually add performance overhead to use a custom List type in JS.

We can learn a lot by manually implementing a List even though in real world JS it has few if any uses. Building a List teaches us how arrays are actually implemented in dynamic languages and why operations on a array have the performance characteristics they do.

What is a List's API

  • get: Retrieves an item from the list. O(1)
  • push: Adds an item at the end the list. O(1)
  • pop: Removes the item at the end of the list. O(1)
  • unshift: Adds an item to the beginning of the list. O(N)
  • shift: Removes the item at the beginning of the list.. O(N)

In addition to the main functions, most languages provide a functionality for iterating over the list

  • forEach: Loops over each item in the list. O(n)

What you can do with a List

  • implement a dynamic array
  • implement an array that holds types other than primitives
  • efficiently store an ordered sequence of data

A list can also help you;

  • keep track of food to get
  • forget it at home and end up at the grocery without the list
  • leave a grocery store with all the ingredients for tacos except the taco shells
  • design a Dribbble shot

Building the List

The key thing about a list is that it reflects memory locations. Each element in a list corresponds to a location in memory.

Since we cant actually use memory directly in JS we will use an array to represent it:

class List {
  constructor() {
    this.memory = []
    this.length = 0
  }

  get(address) { }

  push(value) {}

  pop() { }

  unshift(value) { }

  shift() { }
}

get: Retrieves an item from a list

We can retrieve an item from a list by simply looking it up by address:

get(address) {
  return this.memory[address]
}

push: Adding items to the end of a list

You might be wondering how we can store items in order when we still look them up by address. We accomplishing this by making sure our addresses are sequential. This means when we add an item to memory we must make sure to use the current length of the list as the address:

push(value) {
  this.memory[this.length] = value
  this.length++
}

pop: Removing an item from the end of the list

We can remove an item by calculating the lastAddress (the current length - 1) and then deleting that element from memory:

pop() {
  if (this.length === 0) {
    return
  }

  const lastAddress = this.length - 1
  const value = this.memory[lastAddress]
  delete this.memory[lastAddress]
  this.length--

  return value
}

unshift: Adding an item to start of a list

To unshift a list we simply need to iterate over every item and move it over once. To figure how to do this we can break down our operations into manual steps:

1: Insert an item at the address 0:

this.memory[address] = value

2: We need to take value that was at that address and set it at the index 1. This requires us to keep track of the previous value, so let's revise our previous code:

let address = 0
let previous = this.memory[address]
this.memory[address] = value

Now we can insert the value at the next index:

address = address + 1
previous = this.memory[address]
this.memory[address] = value

And so on... Every step is this exact operation until we reach the end of the list. To generalize this algorithm all we need to do is keep track of the previous element and the next address we are inserting at -- moving them along by one every time. There are two ways two do this:

  1. via recursion
  2. via a loop

Let's look at the recursive solution first. The insertion of our first value and the previous value are the same operation. Intuitively you might think we need two steps for this;

  1. An operation where we insert the value
  2. A series of operations (an algorithm) where we insert the previous element into the next address until we reach the end of the list.

You don't actually need two steps, because we can simply default the address to the first position in the list (0). This means the first "previous" element will be the first value we insert:

The two step version is rather similar to how an unshift in a LinkedList is done. In a LinkedList the current node points to the next node in the list. To shift a LinkedList you could recursively call a function with the current item until the current item has no next node.

Here is our recursive unshift:

A solution with a loop accomplishes the exact same thing but by looping over things until the end of the list has been reached:

A general rule is that recursion will be slower than loops. Usually function calls have some overheard. In JS, this can be quite significant. In functional languages that encourage recursion the overhead can be nearly non-existent.

shift: Remove an item at the beginning of the list

Let's break down shift into its manual operations. First, how do we set the element at the beginning of the list to the element that is next in the list?

We point the address of 0 to the value of the address + 1:

const address = 0
this.memory[address] = this.memory{address++}

We do this same operation until there are no more addresses. To do this recursively we just need to check if there is a value in the next address and then call the function again if there is:

It is important to note that this sort of list shifting doesn't truly work in JS. It actually leaves us with undefined elements. Those undefined elements wont have an address any more (they are deleted) but your array will be interleaved with undefined values. An array is not very good as an actual memory store, it is just used for learning here.

To make the for loop version of shift all we need to do is construct a loop using 0 as our startpoint and the length of the memory as our endpoint:

shift() {
  if (this.length === 0) {
    return
  }

  const value = this.memory[0]

  for (let address = 0; address < this.length; address++) {
    this.memory[address] = this.memory[address + 1]
  }

  delete this.memory[this.length - 1]
  this.length--

  return value
}

A JavaScript List Using Recursion

The list implementation using recursive techniques:

A JavaScript List Using Loops

And the full implementation using loops: