Interview Practice: Traversing a Linked List in JavaScript
source link: https://typeofnan.dev/interview-practice-traversing-a-linked-list-in-javascript/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK