Interview Practice: Traversing a Linked List in JavaScript
Nick Scialli
April 28, 2020
New — Check out my free newsletter on how the web works!
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!
🎓 Learn how the web works
One of the best ways to level up your tech career is to have a great foundational understanding of how the web works. In my free newsletter, How the Web Works, I provide simple, bite-sized explanations for various web topics that can help you boost your knowledge. Join 2,500+ other learners on the newsletter today!
Signing up is free, I never spam, and you can unsubscribe any time. You won't regret it!
Sign up for the newsletter »Nick Scialli is a senior UI engineer at Microsoft.