Interview Questions – Create a Linked List Class

This series answers coding interview questions from the Coding Interview Prep collection at freeCodeCamp. You can find more with the interview questions tag.

This is a data structures problem.

The question starta a linked list class and then asks you to create an add method that keeps in mind the length and head properties of the object the class creates as well as the next value of the nodes stored within it.

A wrong solution that passed

The first thing that occurred to me was: “Where the heck am I supposed to store the nodes???”

Two options occurred: use an array or a hash table. I used an array and everything worked out, tests passed.

What didn’t occur to me was that the head node was the storage and each node stored its next neighbor, both in a correct solution AND in this one. Basically, I was using the array as a crutch I didn’t need.

 this.add = function(element){
    // Only change code below this line
    if(this.store === undefined) this.store = [];
    let temp = new Node(element);
    this.store.push(temp);
    if(length === 0){
      head = this.store[0];
    } else {
      this.store[length-1].next = this.store[length]
    }
    length++;
    // Only change code above this line
  };

I’m creating the node (and the array if it doesn’t exist), putting it in the array, then pulling it back out of the array to be the next value of the prior node (if there is a prior node). The funny thing is that the list would remain intact even if I clobbered the array, because the node objects are passed by reference, not value.

What does that mean? Passing by reference means when I put a node into the next property, I’m not copying it out of the array, nor am I passing its location in the array, but I’m storing the node object’s location in memory, so even if the order of the array changes or the array itself is clobbered, the node still exists in the next property of the parent object.

Quick demo of how that works…

let f = [];
f.push({"help": "me"});
let b = f[0];
console.log(b)
f = null;
console.log(b)

The object still exists because it’s still assigned to a variable (b) keeping the garbage collector from removing it. So in my solution, the array is absolutely pointless except as a cheat to reference the order of the nodes. It also means I’m creating a whole mess and adding complexity to future management of the list if I keep using it for that purpose.

Solution explained

In the updated version, we still create a new node from the element and make it the head if there isn’t one.

If there is a head node, we iterate through its children to find the last one. Because it doesn’t have a built-in iterator, we construct it with the while loop. When it finds the node with null as its next value, it puts the newly created node in that node’s next property. Then, regardless of where the node was placed, the list length is increased by 1.

And that also passes. It also doesn’t require me to update parts of future exercises to implement an unnecessary array which would also need to be manipulated for remove operations.

Solution

  this.add = function(element){
    // Only change code below this line
    let node = new Node(element);
    if(head === null){
      head = node;
    } else {
      let b = head;
      while(b.next !== null){
        b = b.next;
      }
      b.next = node;
    }
    length++;
    // Only change code above this line
  };