TypeOfNaN

Interview Practice: Traversing a Linked List in JavaScript

Nick Scialli
April 28, 2020

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!

If you'd like to support this blog by buying me a coffee I'd really appreciate it!

Nick Scialli

Nick Scialli is a senior UI engineer at Microsoft.

© 2024 Nick Scialli