JavaScript Data Structure

In this section we will discuss about some JavaScript data structure.

1)What are Data Structures?

Data structures are techniques for storing and organizing data that make it easier to modify, navigate, and access. Data structures determine how data is collected, the functions we can use to access it, and the relationships between data.JavaScript has primitive and non-primitive data structures. Primitive data structures and data types are native to the programming language. These include boolean, null, number, string, etc. Non-primitive data structures include linear data structures, static data structures, and dynamic data structures, like queue and linked lists.

2)What is Queue?

A Queue works on the FIFO(First in First Out) principle. Hence, it performs two basic operations that is addition of elements at the end of the queue and removal of elements from the front of the queue.In below, we show the skeleton the Queue.

3)Implementation of Queue

fig: queue implementation

4)What is a linked list?

A linked list is an ordered collection of data elements. A data element can be represented as a node in a linked list. Each node consists of two parts: data & pointer to the next node.It allocates memory as the list grows. Unlike arrays, which have a fixed size.Random access of data elements is not allowed,

A linked list has the following properties:

  • Successive nodes are connected by pointers.
  • The last node points to null.
  • A head pointer is maintained which points to the first node of the list.
  • A linked list can grow and shrink in size during execution of the program.

Advantages

  • Dynamic size
  • Orders data in the order it was received
  • Low runtime

Disadvantages

  • Can only retrieve the oldest element

Applications

  • Effective as a buffer when receiving frequent data
  • Convenient way to store order-sensitive data such as stored voicemails
  • Ensures the oldest data is processed first

5)What is Stack?

Stack is a linear data structure in which addition or removal of element follows a particular order called LIFO(Last in First Out).

class Stack {

// Array is used to implement stack

constructor()

{

this.items = [];

}

// Functions to be implemented

// push(item) it is used to add element

// pop() it is used to remove element

// peek() retur the top element of the stack

}

6)Implementation of stack

fig: stack part-1
fig: stack part-2

7)What is hash tables(MAP)?

Hash tables are a complex data structure capable of storing large amounts of information and retrieving specific elements efficiently. This data structure relies on the concept of key/value pairs, where the “key” is a searched string and the “value” is the data paired with that key.The core concept of the hashing function is that it takes an input of any size and returns a hash code identifier of a fixed size.It is used in database storage and address looks up.

Advantages

  • Key can be in any form, while array’s indices must be integers
  • Highly efficient search function
  • Constant number of operations for each search
  • Constant cost for insertion or deletion operations

Disadvantages

  • Collisions: an error caused when two keys convert to the same hash code or two hash codes point to the same value.

8)The core code to implement a hash table

class HashTable {
constructor(size) {
// define the size of our hash table, which will be used in our hashing function
this.size = size;
this.storage = [];
}
insert(key, value) { }
get() {}
remove() {}
// this is how we will hash our keys
myHashingFunction(str, n) {
let sum = 0;
for (let i = 0; i < str.length; i++) {
sum += str.charCodeAt(i) * 3;
}
return sum % n;

9)Tree Data Structure

In computer science, a tree is a widely used abstract data type (ADT) — or data structure implementing this ADT — that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

Applications

  • Storing hierarchical data such as a file location.
  • Binary search trees are excellent for tasks needing searching or ordering of data.

10)This type of tree is defined by four strict rules

  1. The left subtree contains only nodes with elements lesser than the root.
  2. The right subtree contains only nodes with elements greater than the root.
  3. Left and right subtrees must also be a binary search tree. They must follow the above rules with the “root” of their tree.
  4. There can be no duplicate nodes, i.e. no two nodes can have the same value.

Web developer