Common Data Structures in JavaScript

When it comes to data structures, the majority of textbooks typically demonstrate implementation using languages such as C or Java. However, with the increasing popularity of Jamstack, it is crucial to carefully evaluate and select efficient data structures for client-side state management as well, considering both their advantages and limitations.

I will be referencing examples from the public repository trekhleb/javascript-algorithms in my blog post, but presenting them in a different manner. I encourage readers to adapt the underlying implementations to suit their specific needs.

Linked List

A linked list is a linear combination of data elements, where each element points to the next. This is particular useful to apply insert or delete on any particular node. For example,

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

Say we want to insert a new node or delete a node, it would be quite easy to unlink the existed node and attach or skip it.

Doubly-linked List

This is an extension of linked list with an extra property prev, which makes it faster to go through each node from reversed direction.

class AnotherListNode {
  val: number
  next: ListNode | null
  prev: ListNode | null

  constructor(val?: number, next?: ListNode | null, prev?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
    this.prev = prev === undefined ? null : prev
  }
}

Hash Table

A hash table is a structure that maps keys to values with a hash function that compute an index for lookup. There will be cases when hash functions maps different keys to the same index, in this case we will create a chain for iteration (can be a linked list).

In JavaScript, we could use object or Map to represent usage of hash tables.

Stack

A stack represents a collection of items with two operations, push & pop that follow first-in-last-out (LIFO) principles so that this collection maintains the order. We will explain more in another article.

Queue

A queue represents a collection of items with two operations, enqueue & dequeue that follow first-in-first-out (FIFO) principles so that this collection maintains the order. We will explain more in another article.

Priority Queue

A priority queue is a queue such that an element with high priority is served before an element with low priority. In this case, the order is determined by another comparator instead.

Tree

A tree is a collection of nodes starting at a root node, where each node is a data structure consisting of a value, together with a list of references to children nodes, with the constraints that no reference is duplicated, and none points to the root. For example, a binary tree can be defined like the following:

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

Graph

A graph a collection of vertices or nodes together with a set of pair of these vertices called edges. If such edges are in a particular order, it's a directed graph otherwise undirected.

This is the most generic concepts of data structure used in mathematics, especially in the branch Graph Theory. For example,

• An array is a undirected graph where each edge works as index of the element.
• A linked list is a directed graph where each edge starts from a non-repeated vertex to another non-repeated vertex.
• A tree is a directed graph where the graph starts from root node and points outward.

Final notes

I guess it would be rather easier with more examples, let's continue in future posts...