TypeOfNaN

Interview Practice: Traversing a Linked List in JavaScript

Nick Scialli April 28, 2020🚀 1 minute read

If you're enjoying this blog, please consider one or both of the following:

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

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!


Nick Scialli

Nick Scialli is a software engineer at the U.S. Digital Service.

Subscribe to the mailing list!

If you like what I post here, please sign up to get updates and code insights in your inbox. I won't spam you and you can unsubscribe any time!

Powered by Buttondown.