Stack, Queue, Linked List and Hash Table In JavaScript
The Stack, Queue, Linked List and Hash Table 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 Stack, Queue, Linked List and Hash Table 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.
Stack
Arguably the most important Stack in JavaScript is the call stack where we push in the scope of a function whenever we execute it. Programmatically, it’s just an array with two principled operations: push and pop. Push addselements to the top of the array, while Pop removes them from the same location. In other words, Stacks follow the “Last In, First Out” protocol (LIFO).
Below is an example of a Stack in code. Notice that we can reverse the order of the stack: the bottom becomes the top and the top becomes the bottom. As such, we can use the array’s unshift and shift methods in place of pushand pop, respectively.
An example of a Queue in code:let stack = [];
//push
stack.push(5);
stack.push(10);
//pop
stack.pop(); //10
stack.pop(); //5
Queue
JavaScript is an event-driven programming language which makes it possible to support non-blocking operations. Internally, the browser manages only one thread to run the entire JavaScript code, using the event queue to enqueue listeners and the event loop to listen for the registered events. To support asynchronicity in a single-threaded environment (to save CPU resources and enhance the web experience), listener functions dequeue and execute only when the call stack is empty. Promises depend on this event-driven architecture to allow a “synchronous-style” execution of asynchronous code that does not block other operations.
Programmatically, Queues are just arrays with two primary operations: unshift and pop. Unshift enqueues items to the end of the array, while Popdequeues them from the beginning of the array. In other words, Queues follow the “First In, First Out” protocol (FIFO). If the direction is reversed, we can replace unshift and pop with push and shift, respectively.
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.
Linked List
Like arrays, Linked Lists store data elements in sequential order. Instead of keeping indexes, linked lists hold pointers to other elements. The first node is called the head while the last node is called the tail. In a singly-linked list, each node has only one pointer to the next node. Here, the head is where we begin our walk down the rest of the list. In a doubly-linked list, a pointer to the previous node is also kept. Therefore, we can also start from the tail and walk “backwards” toward the head.
Linked lists have constant-time insertions and deletions because we can just change the pointers. To do the same operations in arrays requires linear timebecause subsequent items need to be shifted over. Also, linked lists can grow as long as there is space. However, even “dynamic” arrays that automatically resize could become unexpectedly expensive. Of course, there’s always a tradeoff. To lookup or edit an element in a linked list, we might have to walk the entire length which equates to linear time. With array indexes, however, such operations are trivial.
Like arrays, linked lists can operate as stacks. It’s as simple as having the head be the only place for insertion and removal. Linked lists can also operate as queues. This can be achieved with a doubly-linked list, where insertion occurs at the tail and removal occurs at the head, or vice versa.
Linked lists are useful on both the client and server. On the client, state management libraries like Redux structure its middleware logic in a linked-list fashion. When actions are dispatched, they are piped from one middleware to the next until all is visited before reaching the reducers. On the server, web frameworks like Express also structure its middleware logic in a similar fashion. When a request is received, it is piped from one middleware to the next until a response is issued.
Single Linked List
Array: 0: 12 1: 99 2: 37Linked List: head → 12 → 99 → 37 → ∅
Doubly Linked List
A doubly-linked list is the same as a singly-linked list, except that every node has both a next pointer pointing forwards and a pre (previous) pointer pointing backwards. This takes more memory to maintain and the logic of the methods becomes a little more difficult to reason about. It allows some speed optimizations. It would look like this.
head
↓
∅ ← 12 ⇄ 99 ⇄ 37 → ∅const list = {
head: → { value: 12, pre: ∅, next: ⤵ }
{ value: 99, pre: ⤴, next: ⤵ }
{ value: 37, pre: ⤴, next: ∅ }
};
Circular Linked List
A circular linked list has no null value at the end. The next value of the last item is set equal to the head.
head
↓
12 ← 37
↘ ↑
99const list = {
head: → { value: 12, next: ⤵ }
{ value: 99, next: ⤵ }
{ value: 37, next: list.head }
};
Hash Table
I’ll try to give a non technical answer here.
A Hash table is one which helps you reduce the possible places where you can find an element, really. What you do is given a set of possible places, you chop (hacher) them down into little pieces. To place an object, associate it with a piece based on the element’s property.
When you want to check if an object exists, you will only try to check the check that piece.
An analogy will be looking for Karthik in the ‘K’ section of a regular phonebook instead of the entire book. This is, assuming you decided to organize the names initially and put names starting with ‘K’ on the K-page.
