21
The Benefits Of Linked Lists And How I Implemented A Queue In React
While developing my latest project, I came across a situation in which I wanted to use a Queue. Having recently learned about Linked Lists, I decided to implement the Queue using my own Linked List Class. In this post I will explain the pros and cons of using Linked Lists and how I implemented a Linked List in my project.
A Linked List is a data structure that is similar to an Array. The main difference is that Linked Lists have no random access, meaning that we can not immediately grab elements from the list using an index. Instead we have to traverse the list starting from the head to get to the element at the specified index. For this reason, it is not usually a good idea to use Linked Lists as a replacement for a standard Array.
However, the benefit we get from using Linked Lists is saving time when we add or remove items at the beginning or middle of the list. This is because Linked Lists don't use indexes like Arrays. When we shift an element onto an Array, the Array must update the index for every element after the shifted element. With a Linked List we don't have to worry about that. This makes using Linked Lists advantageous when we want to use them as a Queue.
To elaborate, a queue is an idea of a list that abides by the First in, First out principle. Therefore, if we are implementing a Queue for an application, we need to add or remove elements from the start of the list and do the opposite at the end of the list. For instance, if we are adding elements to the start of our Queue, when we want to remove elements, we remove them from the end of the Queue, and vice versa. Because we are always either adding or removing from the start of the list, an Array would not be the most efficient data structure to use for a Queue. (Provided we don't care about random access.)
To implement a Queue for my React Project, I made a basic Queue Class. The code is below:
class Node {
constructor(val){
this.val = val
this.next = null
}
}
export default class Queue{
constructor(){
this.first = null
this.last = null
this.length = 0
}
enqueue(val){
node = new Node(val)
this.length++
if(this.length === 1){
this.first = node
this.last = node
}
else{
this.last.next = node
this.last = node
}
return this
}
dequeue(){
if(this.length === 0) return undefined
this.length--
temp = this.first
if(this.length === 0) this.last = null
this.first = temp.next
return temp.val
}
}
My project is an app that scrapes the FoodNetwork Website to find random recipes. Users can swipe left or right to discard or save recipes as they appear. I use the queue to load extra recipes so after a user swipes another one will be loaded and ready to go.
To start with, I initialize the queue when the component mounts and enqueue 5 recipes.
const recipes = new Queue()
useEffect(()=>{
findRecipe(setNext)
findRecipe(setRecipe, setLoading)
for(let i=0;i<5;i++){
findRecipe((obj)=>recipes.enqueue(obj))
}
},[])
The findRecipe function is a call to my Scraper that takes a callback function and passes a new Recipe object to that callback.
I use another useEffect hook to set the the nextRecipe to the recipe that is returned from dequeuing and also enqueue a new recipe. This happens each time a user swipes to find a new recipe. Thus, the queue maintains 5 recipes at most.
useEffect(() =>{
setNext(recipes.dequeue())
findRecipe((obj)=>recipes.enqueue(obj))
},[recipe])
I found that using a Linked List worked best for this because I don't need to access elements from the middle of the list and the small time I save with dequeueing from the Linked List rather than unshifting from an array helps make my app a little smoother. I hope you liked reading my post and have a good day. :)
21