loading...
Cover image for Acing Your Interview: Traversing a Linked List in JavaScript

Acing Your Interview: Traversing a Linked List in JavaScript

nas5w profile image Nick Scialli (he/him) Originally published at typeofnan.dev ・2 min read

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!

Discussion

pic
Editor guide
Collapse
bytebodger profile image
Adam Nathaniel Davis

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.

Collapse
lobsterpants66 profile image
Chris Shepherd

Just wondering..Has anyone actually ever needed to do this as part of their day to day work ?

Collapse
nas5w profile image
Nick Scialli (he/him) Author

Gosh, no, why would they ask relevant questions in an interview ;)