Data Structures in JavaScript

Overview

The data structures in javascript are nothing but a meaningful way of arranging, and storing the data in the computer for efficient utilization and processing depending upon the situation. The data structures in javascript can be classified into two categories namely - primitive data structure and non-primitive data structure. A non-primitive data structure can store the value of more than one data type. For Example - singly-linked lists, doubly-linked lists, circular linked lists, queues, stacks, sets, hash tables, heaps, priority queues, trees, graphs, etc.

Cheatsheet for Data Structures in JavaScript

Before learning about the data structures in javascript, let us first learn what are data structures and data types.

Data types are nothing but the classification or categorization of the data items. Data types represent the kind of value and also tell what operations can be performed on a particular data. Various programming languages and various data types. On the other hand, the data structures are nothing but a meaningful way of arranging, and storing the data in the computer for efficient utilization and processing depending upon the situation. The data structure can be classified into two categories namely - primitive data structure and non-primitive data structure.

A primitive data structure can store the value of only one data type. For example, a char data structure (a primitive data structure) can store only characters.

Key features of a primitive data structure:

The size of a primitive data structure is known as it can store can only one data type.
The primitive data structure will always store some data. It cannot contain the NULL value.
Examples of the primitive data type are integer, character, boolean, float, double, long, etc.

Unlike the primitive data structure, a non-primitive data structure can store the value of more than one data type.

Key features of a primitive data structure:

The size of a primitive data structure depends upon the type of data it stores.
The primitive data structure will be just initialized without storing any data or value. It can contain the NULL value.
Examples of non-primitive data types are linked lists, stacks, queues, dictionaries, etc.

Now let us learn about the most commonly used non-primitive data structures along with their examples.

Linked List

As the name suggests, a linked list is a sequential collection of data elements connected via links. The data element of a linked list is known as a node which contains two parts namely - the data part and the pointer. The data part contains the actual data and the pointer part contains a pointer that points to the next element of the linked list.

Note: The last node of a linked list points to NULL.

Example:

linked-list2

To learn more about the linked lists, refer to the article - Linked Lists in Data Structure.

Doubly Linked List

The doubly linked list is also a sequential collection of data elements connected via links. The data element of a doubly linked list (node) contains three parts namely - the data part and two-pointers. The data part contains the actual data. One of the pointers points to the next element of the doubly linked list and the other pointer points to the previous element of the doubly linked list.

Note: The previous pointer of the head node of a doubly-linked list points to NULL similarly to the next pointer of the last node of a doubly-linked list point.

Example:

doubly-linked-list2

Circular Linked List

The circular linked list is also a sequential collection of data elements connected via links. The data element of a circular linked list (node) contains two parts namely - the data part and the pointer. The data part contains the actual data and the pointer part contains a pointer that points to the next element of the circular linked list. The last node of a circular linked list points to the first node hence making it circular.

Example:

circular-linked-list2

Queue

Queue in a linear data structure that stores data sequentially based on the First In First Out (FIFO) manner. So, the data which is inserted first will be removed from the queue first. Since the first element inserted is served and removed first, the queue data structure is also known as the First Come First Served data structure.

Example:

queue2

To learn more about the queues, refer to the article - Queues in Data Structure.

Stack

Stack in a linear data structure that stores data sequentially based on the Last In First Out (LIFO) manner. So, the data which is inserted first will be removed last. Since the last element inserted is served and removed first, the queue data structure is also known as the Last Come First Served data structure.

Example:

stack2

To learn more about the stacks, refer to the article - Stacks in Data Structure.

Set

The set data structures in javascript are similar to mathematical sets. In simple terms, we can say that a set behaves like a container that can store other data types but it only allows unique elements. So, a set cannot contain duplicate items or elements.

Example:

set

Hash Table

A hash table is one of the most important and widely used data structures in javascript. The hash table stores the data in the form of key-value pairs. These key-value pair helps in faster retrieval of data as the key part is used as the index of the value. The hash tables use a special function called hash function (or hashing technique) which maps the key to its value.

Example:

hash-table

To learn more about hash tables and hashing, refer to the article - Hashing in Data Structure.

Heap - Max and Min Heap Versions

A heap is also a non-linear tree-based data structure that stores the data in the form of nodes. The heap data structure forms a complete binary tree. The main advantage of using a heap is that it stores the data in a specific order. According to the order of the data, it can be divided into two types - max heap (the value of each node is greater than or equal to the values of its children node) and min heap (the value of each node is lesser than or equal to the values of its children node).

Example:

heap-data-structure2

To learn more about the heaps (mac heap and min heap), refer to the article - Heaps in Data Structure.

Priority Queue

A priority queue is somewhat similar to the queue data structure but the elements of the priority queue data structure are associated with some priority value. According to the assigned priority, the values are retrieved. So the highest priority value will be served first.

Example:

priority-queue2

To learn more about the priority queue, refer to the article - Priority Queues in Data Structure.

Trie

A trie is a non-linear data structure that is similar to trees. A trie is also known as a tree-like data structure that consists of nodes. The trie data structure is mainly used for searching purposes for example - a dictionary can be stored in the form of the trie. Using a trie data structure we can form a list of valid words, suggestions, etc.

Example:

trie

Tree

The tree is a hierarchical non-linear data structure that is used to organize, store, and manipulated the data efficiently. The tree traversal in the data structure is a technique that is used to traverse or visit the nodes of a tree (for printing, modifying, etc.). As we know all the nodes of a tree form a hierarchal structure (or we can say that they all are connected via edges), and we can easily traverse all the nodes using the root node or the head node.

Example:

tree2

To learn more about the trees, refer to the article - Trees in Data Structure.

A tree can be of many types let us briefly discuss some of them.

Binary Tree

A binary tree is a tree data structure in which each element can have at most two child nodes. Each node of a binary tree cannot have more than two nodes.

Example:

binary-tree2

To learn more about binary trees, refer to the article - Binary Tree in Data Structure.

Binary Search Tree

A `binary search tree is a binary tree in which each element can have at most two child nodes. All the nodes of the left subtree of a binary search tree must be less than or equal to the parent node as well as all the nodes of the right subtree of a binary search tree must be greater than or equal to the parent node.

Example:

To learn more about the binary search trees, refer to the article - Binary Search Trees.

AVL Tree

AVL tree (Adelson-Velsky and Landis tree) is a binary search tree that is self-balancing in nature. The main property of an AVL tree is that for each node of the AVL tree, the difference between the heights of the left subtree and the right subtree cannot be greater than one.

Example:

avl-tree2

To learn more about the avl tree, refer to the article - AVL Tree.

Red-Black Tree

The red-Black tree is also a binary search tree that is self-balancing in nature. As the name suggests, every node of a red-black tree is either red or black.

Properties of a Red-Black Tree are:

Leaf nodes are black.
If the parent node is red then both of its children must be black.
Every path from a node to the descendant leaf node must have the same number of a black node

Example:

red-black-tree2

To learn more about the red-black trees, refer to the article - Red Black Tree

Segment Tree

A segment tree or a statistic tree is a tree-based data structure that is used to store information about segments or intervals.

Example:

segment-tree

To learn more about the segment trees, refer to the article - Segment Trees in Data Structure.

Fenwick Tree (Binary Indexed Tree)

Fenwick Tree or the Binary Indexed Tree is an array-like structure where we can add elements at the end of the tree just like arrays. Fenwick Trees are easier to implement and take lesser space than Segment Trees.

Example:

fenwick-tree

To learn more about the Fenwick trees or the binary indexed trees, refer to the article - Fenwick Tree | Binary Indexed Trees.

Graph

Graphs are relationship-based non-linear data structures created using nodes that are connected via edges. The node in a graph is also known as a vertex. The typical representation of a Graph is G = (V, E) where V is the set of all the vertices of the graph and E is the set of all the edges of Graph G.

Example:

graph

To learn more about the graphs, refer to the article - Graph in Data Structure.

Conclusion

The data structures in javascript are nothing but a meaningful way of arranging, and storing the data in the computer for efficient utilization and processing depending upon the situation.
A linked list is a sequential collection of data elements connected via links. The data element of a linked list is known as a node which contains two parts namely - the data part and the pointer.
Stack in a linear data structure that stores data sequentially based on the Last In First Out (LIFO) manner. Queue in a linear data structure that stores data sequentially based on the First In First Out (FIFO) manner.
The set data structures in javascript only allows unique element.
The hash table stores the data in the form of key-value pairs. These key-value pair helps in faster retrieval of data as the key part is used as the index of the value.
The heap data structure forms a complete binary tree. The main advantage of using a heap is that it stores the data in a specific order.
The tree is a hierarchical non-linear data structure that is used to organize, store, and manipulated the data efficiently.
Graphs are relationship-based non-linear data structures created using nodes that are connected via edges. The node in a graph is also known as a vertex.