Acing Your Interview: Traversing a Linked List in JavaScript

#javascript #interview #career #programming

Traversing a linked list data structure is a common interview question. Today, we'll explore how to do so in JavaScript.

🎥 The Video Version

Prefer video tutorials? I made a walkthrough of this interview question solution on YouTube!

The Linked List Data Structure

An example of a linked list is an ordered list of numbers. For example:

5 -> 3 -> 10

In JavaScript, a linked list tends to be represented as an object with a value and a reference to the next item in the list. Our aforementioned list of numbers could be represented as follows:

const linkedList = {
  val: 5,
  next: {
    val: 3,
    next: {
      val: 10,
      next: null,
    },
  },
};

How to Traverse? Let's Take Some Hints from the Structure

So our assignmnet is to traverse this list and put its values into an array: [5, 3, 10].

To do so, we're going to take a hint from the data structure. We can se that, if next has a value, there are more elements to traverse. if next is null, we're done.

We'll start with an empty array and use a while loop to trace our way down the structure:

const arr = [];
let head = linkedList;

while (head !== null) {
  arr.push(head.val);
  head = head.next;
}

console.log(arr);
// [5, 3, 10]

How This Works

So how does this work? At each iteration of the while loop, the head variable points to one object deeper in the linked list.

const linkedList = {
  // head @ Loop 1
  val: 5,
  next: {
    // head @ Loop 2
    val: 3,
    next: {
      // head @ Loop 3
      val: 10,
      next: null,
    },
  },
};

Each loop we push the val to our arr and then move on. If next is null, our while loop ends!

Top comments (3)

Adam Nathaniel Davis • May 6 '20

An alternate solution using recursion:

const linkedList = {
  val: 5,
  next: {
    val: 3,
    next: {
      val: 10,
      next: null,
    },
  },
};

const getValuesFromLinkedList = (currentList = {}, currentValues = []) => {
  if (currentList.hasOwnProperty('val'))
    currentValues.push(currentList.val);
  if (currentList.hasOwnProperty('next') && typeof currentList.next === 'object' && currentList.next !== null && !Array.isArray(currentList.next))
    currentValues = getValuesFromLinkedList(currentList.next, currentValues);
  return currentValues;  
}

console.log(getValuesFromLinkedList(linkedList));

As silly as this sounds, if you can demonstrate (working) recursion during a whiteboard/screenshare interview, it often carries more weight with the interviewers than it warrants. Like you've certified yourself as a master of the dark arts.

I humbly submit that this solution is a bit more robust, because it doesn't depend upon the idea that there are given properties in the source object, or that they are set to a specific value of null. That while loop above is problematic if values other than Object/null are set on next.

Finally, by encapsulating the answer in a function, the function can truly operate as a standalone algorithm. But the while loop is dependent upon the setting of the head variable before you enter the loop.

Are all of these points incredibly nitpicky?? Yes. They absolutely are. I'm waiting for my next meeting to begin, and I'm bored. So I went through this in much more detail than you should expect in most interviews.

Cheers.