# 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...