Loading...

Building Custom Data Structures in Node.js with JavaScript

Welcome to this beginner-friendly tutorial on building custom data structures in Node.js with JavaScript. Data structures are the backbone of computer science and programming, as they help us store, organize, and manage our data efficiently. In this tutorial, we will learn how to build custom data structures from scratch and dive deep into their inner workings, enabling you to better understand the underlying concepts and apply them in your own projects.

Introduction to Data Structures

A data structure is a specialized format for organizing, storing, and managing data. They can be seen as a way to store data in an efficient manner, allowing us to perform operations on the data easily and quickly. There are various types of data structures, and each has its own set of advantages and disadvantages.

In this tutorial, we will be exploring the following custom data structures:

  1. Stack
  2. Queue
  3. Linked List
  4. Binary Search Tree

Prerequisites

Before we begin, make sure you have the following installed on your machine:

  1. Node.js
  2. A code editor (Visual Studio Code, Sublime Text, or any other text editor of your choice)

Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) order. This means that the newest element added to the stack is the first one to be removed. Think of it as a collection of items where the item at the top can be accessed easily, and items can be added or removed only from the top.

Implementing a Stack

We will start by creating a class named Stack and define the basic structure of our stack.

class Stack { constructor() { this.items = []; } }

Now let's add the following methods to our stack:

  1. push(): Adds an element to the top of the stack.
  2. pop(): Removes and returns the top element from the stack.
  3. peek(): Returns the top element of the stack without removing it.
  4. isEmpty(): Checks if the stack is empty.
  5. size(): Returns the number of elements in the stack.
class Stack { constructor() { this.items = []; } push(element) { this.items.push(element); } pop() { if (this.isEmpty()) { return 'Stack is empty'; } return this.items.pop(); } peek() { if (this.isEmpty()) { return 'Stack is empty'; } return this.items[this.items.length - 1]; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } }

Using the Stack

Now that our stack is complete, let's see how to use it.

const stack = new Stack(); stack.push(1); stack.push(2); stack.push(3); console.log(stack.peek()); // Output: 3 console.log(stack.pop()); // Output: 3 console.log(stack.size()); // Output: 2

Queue

A queue is a linear data structure that follows the First In First Out (FIFO) order. This means that the first element added to the queue will be the first one to be removed. It operates on the principle of a real-life queue, where the first person to enter the queue is the first one to leave.

Implementing a Queue

Similar to the stack, we will create a class named Queue and define the basic structure of our queue.

class Queue { constructor() { this.items = []; } }

Now let's add the following methods to our queue:

  1. enqueue(element): Adds an element to the end of the queue.
  2. dequeue(): Removes and returns the front element from the queue.
  3. front(): Returns the front element of the queue without removing it.
  4. isEmpty(): Checks if the queue is empty.
  5. size(): Returns the number of elements in the queue.
class Queue { constructor() { this.items = []; } enqueue(element) { this.items.push(element); } dequeue() { if (this.isEmpty()) { return 'Queue is empty'; } return this.items.shift(); } front() { if (this.isEmpty()) { return 'Queue is empty'; } return this.items[0]; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } }

Using the Queue

Now that our queue is complete, let's see how to use it.

const queue = new Queue(); queue.enqueue(1); queue.enqueue(2); queue.enqueue(3); console.log(queue.front()); // Output: 1 console.log(queue.dequeue()); // Output: 1 console.log(queue.size()); // Output: 2

Linked List

A linked list is a linear data structure where elements are stored in nodes. Each node points to the next node in the list. The first node is called the head, and the last node points to null, indicating the end of the list.

Implementing a Linked List

We will start by creating a class named Node to represent the elements in our linked list.

class Node { constructor(data) { this.data = data; this.next = null; } }

Now, let's create the LinkedList class and define the basic structure of our linked list.

class LinkedList { constructor() { this.head = null; this.size = 0; } }

Now let's add the following methods to our linked list:

  1. add(element): Adds an element to the end of the list.
  2. insertAt(element, index): Inserts an element at the specified index.
  3. remove(element): Removes the specified element from the list.
  4. removeAt(index): Removes the element at the specified index.
  5. indexOf(element): Returns the index of the specified element.
  6. isEmpty(): Checks if the list is empty.
  7. size(): Returns the number of elements in the list.
  8. toString(): Returns a string representation of the list.
class LinkedList { constructor() { this.head = null; this.size = 0; } add(element) { const newNode = new Node(element); if (this.head === null) { this.head = newNode; } else { let current = this.head; while (current.next) { current = current.next; } current.next = newNode; } this.size++; } insertAt(element, index) { if (index < 0 || index > this.size) { return false; } const newNode = new Node(element); let current = this.head; let previous; let i = 0; if (index === 0) { newNode.next = current; this.head = newNode; } else { while (i < index) { i++; previous = current; current = current.next; } newNode.next = current; previous.next= newNode; } this.size++; } remove(element) { const index = this.indexOf(element); return this.removeAt(index); } removeAt(index) { if (index < 0 || index >= this.size) { return null; } let current = this.head; let previous; let i = 0; if (index === 0) { this.head = current.next; } else { while (i < index) { i++; previous = current; current = current.next; } previous.next = current.next; } this.size--; return current.data; } indexOf(element) { let current = this.head; let index = 0; while (current) { if (current.data === element) { return index; } index++; current = current.next; } return -1; } isEmpty() { return this.size === 0; } size() { return this.size; } toString() { let current = this.head; let result = ''; while (current) { result += current.data + (current.next ? ' -> ' : ''); current = current.next; } return result; } } ### Using the Linked List Now that our linked list is complete, let's see how to use it. ```javascript const linkedList = new LinkedList(); linkedList.add(1); linkedList.add(2); linkedList.add(3); console.log(linkedList.toString()); // Output: 1 -> 2 -> 3 linkedList.insertAt(0, 0); console.log(linkedList.toString()); // Output: 0 -> 1 -> 2 -> 3 linkedList.remove(2); console.log(linkedList.toString()); // Output: 0 -> 1 -> 3

Binary Search Tree

A binary search tree (BST) is a binary tree data structure where each node has at most two children, arranged in such a way that the value of the node to the left is less than or equal to the parent node, and the value of the node to the right is greater than or equal to the parent node.

Implementing a Binary Search Tree

We will start by creating a class named TreeNode to represent the elements in our binary search tree.

class TreeNode { constructor(data) { this.data = data; this.left = null; this.right = null; } }

Now, let's create the BinarySearchTree class and define the basic structure of our binary search tree.

class BinarySearchTree { constructor() { this.root = null; } }

Now let's add the following methods to our binary search tree:

  1. insert(data): Inserts a new node with the specified data.
  2. search(data): Searches for a node with the specified data and returns the node if found, otherwise returns null.
  3. remove(data): Removes the node with the specified data.
  4. min(): Returns the minimum value in the tree.
  5. max(): Returns the maximum value in the tree.
  6. inorder(): Traverses the tree in an inorder fashion and returns an array of the visited nodes.
  7. preorder(): Traverses the tree in a preorder fashion and returns an array of the visited nodes.
  8. postorder(): Traverses the tree in a postorder fashion and returns an array of the visited nodes.
class BinarySearchTree { constructor() { this.root =null; } insert(data) { const newNode = new TreeNode(data); if (this.root === null) { this.root = newNode; } else { this.insertNode(this.root, newNode); } } insertNode(node, newNode) { if (newNode.data < node.data) { if (node.left === null) { node.left = newNode; } else { this.insertNode(node.left, newNode); } } else { if (node.right === null) { node.right = newNode; } else { this.insertNode(node.right, newNode); } } } search(data) { return this.searchNode(this.root, data); } searchNode(node, data) { if (node === null) { return null; } else if (data < node.data) { return this.searchNode(node.left, data); } else if (data > node.data) { return this.searchNode(node.right, data); } else { return node; } } remove(data) { this.root = this.removeNode(this.root, data); } removeNode(node, data) { if (node === null) { return null; } if (data < node.data) { node.left = this.removeNode(node.left, data); return node; } else if (data > node.data) { node.right = this.removeNode(node.right, data); return node; } else { if (node.left === null && node.right === null) { node = null; return node; } if (node.left === null) { node = node.right; return node; } else if (node.right === null) { node = node.left; return node; } node.data = this.minNode(node.right); node.right = this.removeNode(node.right, node.data); return node; } } min() { return this.minNode(this.root); } minNode(node) { if (node.left === null) { return node.data; } else { return this.minNode(node.left); } } max() { return this.maxNode(this.root); } maxNode(node) { if (node.right === null) { return node.data; } else { return this.maxNode(node.right); } } inorder() { const result = []; this.inorderTraversal(this.root, result); return result; } inorderTraversal(node, result) { if (node !== null) { this.inorderTraversal(node.left, result); result.push(node.data); this.inorderTraversal(node.right, result); } } preorder() { const result = []; this.preorderTraversal(this.root, result); return result; } preorderTraversal(node, result) { if (node !== null) { result.push(node.data); this.preorderTraversal(node.left, result); this.preorderTraversal(node.right, result); } } postorder() { const result = []; this.postorderTraversal(this.root, result); return result; } postorderTraversal(node, result) { if (node !== null) { this.postorderTraversal(node.left, result); this.postorderTraversal(node.right, result); result.push(node.data); } } } ### Using the Binary Search Tree Now that our binary search tree is complete, let's see how to use it. ```javascript const bst= new BinarySearchTree(); bst.insert(8); bst.insert(3); bst.insert(10); bst.insert(1); bst.insert(6); bst.insert(14); bst.insert(4); bst.insert(7); bst.insert(13); console.log(bst.inorder()); // Output: [1, 3, 4, 6, 7, 8, 10, 13, 14] console.log(bst.preorder()); // Output: [8, 3, 1, 6, 4, 7, 10, 14, 13] console.log(bst.postorder()); // Output: [1, 4, 7, 6, 3, 13, 14, 10, 8] console.log(bst.search(6)); // Output: TreeNode { data: 6, left: TreeNode, right: TreeNode } console.log(bst.min()); // Output: 1 console.log(bst.max()); // Output: 14 bst.remove(3); console.log(bst.inorder()); // Output: [1, 4, 6, 7, 8, 10, 13, 14]

FAQ

1. What are the main differences between a stack and a queue?

A stack is a linear data structure that follows the Last In First Out (LIFO) principle, whereas a queue follows the First In First Out (FIFO) principle. In a stack, elements are added and removed from the top, while in a queue, elements are added at the rear and removed from the front.

2. What is the difference between singly linked lists and doubly linked lists?

A singly linked list has nodes with a single pointer that points to the next node in the list, while a doubly linked list has nodes with two pointers, one pointing to the next node and the other pointing to the previous node. Doubly linked lists allow traversal in both forward and backward directions, whereas singly linked lists can only be traversed in the forward direction.

3. What is the time complexity of searching in a binary search tree?

The time complexity of searching in a binary search tree is O(h), where h is the height of the tree. In the best case, the tree is perfectly balanced, and the time complexity is O(log n), where n is the number of nodes. In the worst case, the tree is completely unbalanced (degenerated into a linked list), and the time complexity is O(n).

4. Are arrays considered data structures?

Yes, arrays are considered data structures. An array is a linear data structure that stores elements of the same data type in a contiguous block of memory. Arrays have a fixed size and allow random access to elements.

5. When should I use a custom data structure over built-in data structures in JavaScript?

Custom data structures can be useful when you have specific requirements that built-in data structures may not fulfill efficiently. They can be tailored to meet your unique use case and can provide a better understanding of the underlying concepts. However, it's important to note that built-in data structures are usually more optimized and should be the first choice in most situations.

Sharing is caring

Did you like what Mehul Mohan wrote? Thank them for their work by sharing it on social media.

0/10000

No comments so far