How To Create A Linked List, Stack and Queue in JavaScript
The linked list, stack and Queue are some of the most common data structures in computer science. All three hold a collection of elements and can be traversed. In the linked list one pointer is used to keep track of the head and another keeps track of the next value. On the other hand a stack and queue keeps track of the top value, size and previous value in most cases.
Each implementation of these data structures may differ slightly. The linked list can be written as a circularly linked list, double linked list or singly linked list. Depending on the implementation a stack may, or may not, keep track of the previous value.
Some other common data structures include trees, tries & graphs, heaps, array lists and hash tables. For the sake of this blog article we'll just discuss linked lists, queues and stacks using JavaScript
In this blog post we'll discuss how to implement a stack, queue and linked list using JavaScript.
I encourage you before you begin to try to implement these data structures by yourself first. Check back here and see how you did.
Linked List
A linked list is a linear collection of data elements, called nodes, each pointing to the next node. This is done by the use of of a pointer. See the below example.
<img src="/content/images/2017/02/LinkedList.jpg" style="max-width:100%;height:auto" align="left""/>
The first node is known as the head node. It points to the first element. We can use the pointer to traverse the elements in the node. The last node points to null.
To implement this data structure we'll use prototypal inheritance using JavaScript. Let's begin by creating a simple constructor function with a head pointion to null.
function LinkedList(){
this.head = null;
}
Now we need to implement the rest. We'll use prototype object to extend the LinkedList function.
LinkedList.prototype.push = function(val){
var node = {
value: val,
next: null
}
if(!this.head){
this.head = node;
}
else{
current = this.head;
while(current.next){
current = current.next;
}
current.next = node;
}
}
The code above implements the rest of the linked list. Each node object will have a value and a pointer to null. A check is made if the head is empty. If so it's set to head. Else a new node is created and appended to the end of the list.
Let's check if it works!
let ll = new LinkedList();
// add
ll.push(235);
ll.push(245);
ll.push(123);
ll.head; //Object value: 235
ll.head.next; //Object value: 245
ll.head.next.next //object value: 123
First we use the new keyword to create a new instance. We can then use the push method to add values. As you can see each value is added to a new node. We can access these nodes by using next value.
Pretty simple right? We could use ES6 classes to do the same thing, we'll look at that in another post.
Stack
A stack is an abstract data type that serves a collection of elements. It uses push to add values to the stack and pop to remove things from the stack.
You can think of it as a stack of plates you might see at a restaurant. Plates are added from the top and pushed down. To grab a plate you pop one off the top. This is also known as last in first out (LIFO).
You can see a demonstration on how this works below. (thanks Wikipedia!)
<img src="/content/images/2017/02/stack.png" style="max-width:100%;height:auto" align="left""/>
Let's implement this in JavaScript.
let stack = [];
//push
stack.push(5);
stack.push(10);
//pop
stack.pop(); //10
stack.pop(); //5
Good news! JavaScript already supports a stack out of the box using an array. We can easily push items onto the stack and pop them off. Keep in mind that as you pop values off the stack they'll be in reverse order that you put them on.
Queue
A queue is another abstract data type or collection that can hold a set of values in order. You can either enqueue a value which adds it to the end of the list. Or you can dequeue a value that removes a value from the front of the list. This is also known as first-in-first-out (FIFO).
Take a look at the example below.
<img src="/content/images/2017/02/300px-Data_Queue.svg.png" style="max-width:100%;height:auto" align="left""/>
Let's take a look at a simple implementation.
let queue = [];
//enqueue
queue.push(5);
queue.push(3);
queue.push(3);
//dequeue
queue.shift(); // 1
queue.shift(); //2
queue.shift(); // 3
In JavaScript we can use push as are enqueue and shift as a dequeue. The shift will retrieve elements from the front side of you array!
We could implement both the stack and queue using functions, however this just easier and proves the point.
Conclusion
Thanks for reading! If you like this article please enter your email address below, I'll send you some great information on the latest JavaScript on a weekly bases! Take care!