JS: Data Structures

JS: Data Structures

Introduction to data structures with JavaScript.

ยท

18 min read

In JavaScript, user-defined data types refer to data types that the developer creates themselves, rather than the built-in data types that come with the language. These custom data types can be created using objects, classes, or functions.

Objects

Objects are a composite data type that consists of key-value pairs. Each key in an object acts as a unique identifier for its corresponding value. An object can store values of any data type such as strings, numbers, boolean, and even other objects. One advantage of objects is their ability to store complex structured data.

const user = {
  name: 'John',
  age: 25,
  hobbies: ['reading', 'playing guitar'],
  address: {
    street: '123 Main St',
    city: 'New York',
    state: 'NY'
  }
};

Classes

Classes are similar to objects, but they provide a way to define a blueprint for creating objects. A class in JavaScript is created using the class keyword. The properties and methods specify what the class should do and how it should behave. Once a class is created, an object can be created using the new keyword followed by the class name.

class Person {
  constructor(name, age) {
    this.name = name;
    this.age = age;
  }

  greet() {
    console.log(`Hi, my name is ${this.name} and I'm ${this.age} years old.`);
  }
}

const john = new Person('John', 25);
john.greet(); // Output: "Hi, my name is John and I'm 25 years old."

Functions

Functions can also be used to create custom data types in JavaScript. A function can return an object or another function, which can then be used as a custom data type.

function Address(street, city, state) {
  this.street = street;
  this.city = city;
  this.state = state;
}

const myAddress = new Address('123 Main St', 'New York', 'NY');
console.log(myAddress.city); // Output: "New York"

In conclusion, user-defined data types in JavaScript can be created using objects, classes, or functions. These custom data types can provide more flexibility and code organization by allowing developers to create their own specific objects/classes to meet their application requirements.


Recursive Types

A recursive data type is a data type that refers to itself in its definition. In JavaScript, this can be accomplished through the use of constructors and prototypes. Consider the example of a tree data structure, where each node contains a value and references to its child nodes.

function Node(value) {
  this.value = value;
  this.children = [];
}

Node.prototype.addChild = function(childNode) {
  this.children.push(childNode);
}

Here, the Node constructor takes a value argument and initializes an empty array for children. Each node can also call the addChild method to add a child node to its children array. Since each child node is itself a Node, this creates a recursive data structure where every node contains references to its child nodes, which themselves contain references to their own child nodes, and so on.

const root = new Node(1);
const child1 = new Node(2);
const child2 = new Node(3);
const grandchild = new Node(4);

child1.addChild(grandchild);
root.addChild(child1);
root.addChild(child2);

In this example, root is the root of the tree and has two child nodes, child1 and child2. child1 also has a child node, grandchild. Note how the addChild method can be called on any node to add a child node, making it easy to recursively define the tree structure.

In conclusion, recursive data types are a powerful tool in programming and can be used in JavaScript through the use of constructors and prototypes. By defining a data type that refers to itself in its definition, we can create complex and flexible data structures like trees.


JSON Format

JSON stands for JavaScript Object Notation, and it is a data format commonly used for exchanging data between client and server. It is a lightweight data interchange format that is easy for humans to read and write, and easy for machines to parse and generate.

JSON data is represented as key-value pairs, similar to JavaScript object literals. The keys are always strings and are followed by a colon, and the values can be any JSON data type, including strings, numbers, booleans, null, arrays, and other JSON objects.

An example of JSON:

{
   "name": "John Smith",
   "age": 30,
   "isStudent": true,
   "grades": [90, 85, 95],
   "address": {
     "street": "123 Main St",
     "city": "Anytown",
     "state": "CA"
   }
}

The built-in JSON object in JavaScript provides two methods for converting between JSON and JavaScript objects:

  • JSON.parse(): Accepts a JSON string as a parameter and returns the corresponding JavaScript object.

  • JSON.stringify(): Accepts a JavaScript object as a parameter and returns the equivalent JSON string.

Here is an example of using JSON.stringify() to convert a JavaScript object to a JSON string:

const person = {
  name: 'John Smith',
  age: 30,
  isStudent: true,
  grades: [90, 85, 95],
  address: {
    street: '123 Main St',
    city: 'Anytown',
    state: 'CA'
  }
};

const jsonPerson = JSON.stringify(person);
console.log(jsonPerson);

This will output the following JSON string:

{
   "name": "John Smith",
   "age": 30,
   "isStudent": true,
   "grades": [90, 85, 95],
   "address": {
     "street": "123 Main St",
     "city": "Anytown",
     "state": "CA"
   }
}

JSON is widely used in web development for data exchange between a client and a server, especially when using AJAX requests. It's also commonly used as a data format for configuration files, data storage, and data transmission in various applications.


Data Collections

Collections in JavaScript generally refer to data structures that allow you to store and manipulate multiple values in a single variable. Examples of collections in JavaScript include arrays, objects, maps, and sets. These collections enable developers to easily manage groups of related data and perform operations on them efficiently.

Array

In JavaScript, an array is a collection of elements that can be of any type. Arrays are declared using square brackets [ ] and they are dynamic, meaning you can add, remove or modify elements at any time. Elements in an array are accessed via their index value.

One of the advantages of using an array in JavaScript is that they are easy to use and understand. Arrays in JavaScript also have a wide range of built-in methods to manipulate and iterate over them.

// Declaring an array
const numbers = [1, 2, 3, 4, 5];

// Accessing an element in an array
console.log(numbers[0]); // Output: 1

// Modifying an element in an array
numbers[1] = 10;

// Adding an element to an array
numbers.push(6);

// Removing an element from an array
numbers.splice(0, 1); // removes the first element

Sparse Arrays

A sparse array in JavaScript is an array with "holes" or empty slots between its elements. The indexes of elements are not continuous, and some indexes may have no value assigned to them.

Sparse arrays can be created in JavaScript by manually assigning a value to a particular index or by removing an element from an array. For example:

const myArray = [];
myArray[0] = "first element";
myArray[100] = "one-hundredth element";
console.log(myArray.length); // Output: 101

In this example, myArray is a sparse array with two assigned indices, 0 and 100. The length of the array is 101 because it is determined by the highest index plus one.

To check if an index in a sparse array is empty, you can use the in operator:

const myArray = [];
myArray[0] = "first element";
console.log(1 in myArray); // Output: false

In this example, there is no element with an index of 1, so the in operator returns false.

It's important to note that sparse arrays can cause some unexpected behavior in JavaScript since iterating through a sparse array using a for loop is slower than iterating through a dense array. Additionally, some array methods such as map, filter, slice, and concat do not work correctly with sparse arrays since they preserve the sparsity of the array.

Splice & Slice

splice and slice are two array methods in JavaScript that allow you to modify and extract elements from an array.

splice method: The splice method allows you to add or remove elements from an array at a specified index. The syntax of the splice method is as follows:

array.splice(start, deleteCount, item1, item2, ...)

where:

  • start: The index at which to start changing the array. A negative index indicates an offset from the end of the array.

  • deleteCount: The number of elements to remove from the array. If set to 0, no elements will be removed.

  • item1, item2, ...: The elements to add to the array. If set to 0, no elements will be added.

Here's an example:

const array = [1, 2, 3, 4, 5];

// Removes the second and third elements and adds 6 and 7 at their place
array.splice(1, 2, 6, 7);
// Output: [1, 6, 7, 4, 5]

In this example, the splice method removes the elements at index 1 and 2 (i.e., 2 and 3), and replaces them with the elements 6 and 7, resulting in [1, 6, 7, 4, 5].

slice method: The slice method allows you to extract a section of an array and return a new array with those extracted elements. The syntax of the slice method is as follows:

array.slice(start, end)

where:

  • start: The index at which to begin extraction. A negative index indicates an offset from the end of the array.

  • end: The index at which to end extraction (the extracted element will not include this index). A negative index indicates an offset from the end of the array.

Here's an example:

const array = [1, 2, 3, 4, 5];

// Extracts the second and third elements
const extractedArray = array.slice(1, 3);
// Output: [2, 3]

In this example, the slice method extracts the elements between index 1 (inclusive) and 3 (exclusive), resulting in [2, 3]. Note that the original array is not modified by the slice method.


Matrices

In JavaScript, a matrix is a two-dimensional array where each element can be accessed using two indices, such as matrix[i][j]. Matrices are used in various mathematical computations, including linear algebra, image processing, and machine learning.

Here's an example of a matrix in JavaScript:

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];

In this example, the matrix is a 3x3 matrix where the elements are sequential integers from 1 to 9.

Matrices can be used in various mathematical computations, including matrix addition, multiplication, and inversion. For example, matrix addition is performed by adding the corresponding elements of two matrices, as shown below:

const matrix1 = [
  [1, 2],
  [3, 4],
];

const matrix2 = [
  [5, 6],
  [7, 8],
];

// matrix addition
const result = [
  [0, 0],
  [0, 0],
];

for (let i = 0; i < matrix1.length; i++) {
  for (let j = 0; j < matrix1[0].length; j++) {
    result[i][j] = matrix1[i][j] + matrix2[i][j];
  }
}

console.log(result);
// Output: [[6, 8], [10, 12]]

In this example, we perform matrix addition by creating a new matrix result and then adding the corresponding elements of matrix1 and matrix2 using a nested loop.

Overall, matrices are a useful mathematical tool in JavaScript and are used in many different applications that involve linear algebra or image processing.


Data Set

In JavaScript, a set is a collection of distinct values. The Set object lets you store unique values of any type, whether primitive values or object references. Here's an example of how to create and use a set in JavaScript:

// Create a new set
const mySet = new Set();

// Add some elements to the set
mySet.add("apple");
mySet.add("banana");
mySet.add("orange");

// Remove an element from the set
mySet.delete("banana");

// Check if an element is in the set
const containsOrange = mySet.has("orange");

// Get the number of elements in the set
const size = mySet.size;

// Iterate over the elements in the set
for (const element of mySet) {
  console.log(element);
}

Advantages of using sets in JavaScript include:

  1. Sets are useful for removing duplicates from arrays.

  2. Sets are faster than arrays for the has and delete operations, since these operations have constant time complexity.

  3. Sets can be used to perform set operations like union, intersection, and difference.

Disadvantages of using sets in JavaScript include:

  1. Sets do not have the same built-in methods as arrays, such as map, filter, and reduce.

  2. Sets are not index-based, so you cannot access elements by their position in the set.

  3. Sets cannot be serialized to JSON.

Use cases for sets in JavaScript include:

  1. Removing duplicates from an array
const arr = [1, 2, 3, 1, 2, 3];
const uniqueValues = new Set(arr);
console.log(uniqueValues); // Set {1, 2, 3}
  1. Checking if a value is in a set
const mySet = new Set(["apple", "banana", "orange"]);
const hasBanana = mySet.has("banana");
console.log(hasBanana); // true
  1. Performing set operations
const setA = new Set([1, 2, 3]);
const setB = new Set([2, 3, 4]);
const union = new Set([...setA, ...setB]);
const intersection = new Set([...setA].filter(x => setB.has(x)));
const difference = new Set([...setA].filter(x => !setB.has(x)));
console.log(union); // Set {1, 2, 3, 4}
console.log(intersection); // Set {2, 3}
console.log(difference); // Set {1}

HashMap

In JavaScript, an equivalent data structure to HashMap is the Object. Objects in JavaScript are collections of key-value pairs that allow you to store and retrieve data based on a unique key.

One advantage of using an object in JavaScript is that they are a very powerful and versatile data structure. They also have a lot of built-in methods and it can be used to create complex data structures.

// Declaring an object (hash map)
const person = {
  name: 'John',
  age: 30,
  email: 'john@example.com'
};

// Accessing a key-value pair in an object
console.log(person.name); // Output: 'John'

// Modifying a value in an object
person.name = 'Jane';

// Adding a key-value pair to an object
person.address = '123 Main St';

// Removing a key-value pair from an object
delete person.email;

Data Dictionary

In JavaScript, the equivalent of a data dictionary is an object. In fact, JavaScript objects are often referred to as dictionaries because of their key-value structure, where the key represents the name of the property and the value represents the value of the property.

An object in JavaScript is an unordered collection of properties, where each property consists of a key and a value. The key is a string that acts as the name of the property and the value can be any valid JavaScript value, including another object.

Here's an example of a data dictionary implemented using objects in JavaScript:

const dataDictionary = {
  age: 24,
  name: "John Doe",
  address: {
    street: "123 Main St",
    city: "Anytown",
    state: "CA",
    zip: "12345"
  },
  phone: [
    {
      type: "home",
      number: "555-1234"
    },
    {
      type: "work",
      number: "555-5678"
    }
  ]
};

// Accessing the properties of the data dictionary
console.log(dataDictionary.age); // 24
console.log(dataDictionary.name); // "John Doe"
console.log(dataDictionary.address.city); // "Anytown"
console.log(dataDictionary.phone[0].number); // "555-1234"

In this example, we have an object that represents a data dictionary with properties such as age, name, address, and phone. The value of the address property is another object with its own properties, and the value of the phone property is an array of objects.

You can access the properties of the data dictionary using dot notation or bracket notation. For example, dataDictionary.address.city is equivalent to dataDictionary["address"]["city"].


List and Stack

There are no direct equivalents to List and Stack in JavaScript, but you can use an array as a List or a Stack.

Arrays in JavaScript are dynamic, meaning you can add or remove elements at any time, which makes them suitable for implementing List and Stack data structures.

// Implementing a stack using an array
const stack = [];

stack.push(1); // stack is now [1]
stack.push(2); // stack is now [1, 2]
stack.push(3); // stack is now [1, 2, 3]

stack.pop(); // removes 3 from the top of the stack, stack is now [1, 2]
// Implementing a list using an array
const list = [];

list.push('apple'); // list is now ['apple']
list.push('banana'); // list is now ['apple', 'banana']
list.push('orange'); // list is now ['apple', 'banana', 'orange']

list.splice(1, 0, 'pear'); // inserts 'pear' at index 1, list is now ['apple', 'pear', 'banana', 'orange']

Heap

In JavaScript, there is no built-in data structure that is equivalent to Heap, but you can implement a Heap data structure using manual techniques or third-party libraries. One of the most commonly used libraries for implementing Heaps in JavaScript is "Heap.js".

// Importing Heap.js library
const Heap = require('heap.js');

// Declaring a new min heap
const heap = new Heap();

// Adding elements to the heap
heap.push(10);
heap.push(5);
heap.push(15);

// Removing the highest priority element from the heap
console.log(heap.pop()); // Output: 5

Trees

In computer science, a tree is a hierarchical data structure that is used to represent elements or objects in a hierarchical manner. A tree consists of nodes, where each node has a value and may have zero or more child nodes. The topmost node in a tree is called the root node, while the nodes with no children are called leaf nodes.

Here are some types of trees with a brief description for each:

  1. Binary Tree - It is a tree in which each node has at most two child nodes. A binary tree can be used to represent a hierarchical structure such as the file system in a computer, where each folder or directory is a node, and the files contained within are the child nodes.

  2. AVL Tree - It is a balanced binary search tree in which the height difference between any two sub-trees of a node is at most one. The AVL tree was named after Adelson-Velsky and Landis, who developed it in 1962. It is commonly used in database indexing, where it provides efficient lookup, insertion, and deletion operations.

  3. Red-Black Tree - It is a self-balancing binary search tree in which each node is colored either red or black. It was developed by Rudolf Bayer in the 1970s. The red-black tree guarantees that the longest path from the root node to any leaf node is at most twice as long as the shortest path.

  4. B-Tree - It is a tree data structure that is commonly used in databases and file systems. It is a balanced tree with a variable number of child nodes per node, typically ranging from 2 to 256. A B-tree is optimized for reading and writing data to and from a storage medium, as it reduces the number of I/O operations required.

  5. Trie Tree - It is a tree data structure used for efficient string searching operations, such as autocomplete or spell checking. In a Trie tree, each node represents a prefix or a complete word, and its child nodes represent the next characters in the word to be searched.

These are just a few examples of tree data structures, there are many other types of trees such as Suffix Tree, Segment Tree, Fenwick Tree, etc., each designed for specific use case.

Binary Tree

A binary tree is a tree-like data structure in which each node has at most two children, referred to as the left child and the right child. The left child is always less than the parent and the right child is always greater. When a node has no children, it is referred to as a leaf node.

In JavaScript, we can represent a binary tree using an object for each node with the left and right properties pointing to the left and right children respectively, and a value property containing the value of the node. Here's an example implementation of a binary tree in JavaScript:

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

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

  insert(value) {
    const newNode = new Node(value);

    if (!this.root) {
      this.root = newNode;
    } else {
      this._insertRecursive(newNode, this.root);
    }
  }

  _insertRecursive(newNode, currentNode) {
    if (newNode.value < currentNode.value) {
      if (!currentNode.left) {
        currentNode.left = newNode;
      } else {
        this._insertRecursive(newNode, currentNode.left);
      }
    } else {
      if (!currentNode.right) {
        currentNode.right = newNode;
      } else {
        this._insertRecursive(newNode, currentNode.right);
      }
    }
  }

  search(value) {
    let currentNode = this.root;
    while (currentNode) {
      if (value === currentNode.value) {
        return true;
      }
      if (value < currentNode.value) {
        currentNode = currentNode.left;
      } else {
        currentNode = currentNode.right;
      }
    }
    return false;
  }

  // other methods for traversal, deletion, etc. can be added here
}

The BinaryTree class has a root property which points to the root node of the tree. It also has an insert method for inserting new nodes into the tree and a search method for searching for a value in the tree.

The insert method traverses the tree recursively to find the correct position for the new node to be inserted. The _insertRecursive function is a private function that does the actual recursion.

The search method starts at the root node and traverses the tree in a similar way to the insert method to find the node with the matching value. If the value is found, the method returns true. If the value is not found, the method returns false.

This implementation of a binary tree is just one example, and there are many other ways to implement binary trees in JavaScript.


Graphs

In computer science, a graph is a collection of vertices (also known as nodes or points) and edges (also known as lines or arcs) that connect them. A graph can be used to represent a wide range of real-world problems, such as social networks, transportation networks, and data relationships.

There are several ways to implement a graph in JavaScript, some of which are:

  1. Adjacency list - In this method, each vertex in the graph is represented by an array, and each element in the array represents the adjacent vertices. This method is memory efficient for sparse graphs because it only requires memory proportional to the number of edges.

  2. Adjacency matrix - In this method, a two-dimensional array is used to represent the graph. The rows and columns represent the vertices, and the values represent the presence or absence of edges between the vertices. This method is efficient for dense graphs because it requires memory proportional to the number of vertices.

  3. Edge list - In this method, the graph is represented by a simple list of edges, with each edge containing information about its two connecting vertices and any attributes associated with it. This method is easy to implement, but it can be memory-intensive for large graphs.

  4. Object-oriented representation - In this method, a class is defined to represent the vertices and edges of the graph. The class has methods for adding and removing vertices and edges, and for traversing the graph. This method is flexible and easy to understand, but it can become complex for large graphs.

These are some of the ways to implement a graph in JavaScript, and each method has its own advantages and disadvantages depending on the use case.


Disclaim: This article was created with ChatGPT. If you don't like something don't blaim me. Comment below and move on. I like feedback, maybe I can improve something.


You have read all this? You must be crazy. I'm proud of you. Learn and prosper ๐Ÿ––

ย