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!

Nick Scialli

Nick Scialli is a senior UI engineer at Microsoft.

© 2024 Nick Scialli