Data Structure in Javascript
Topics:
1. What are Data Structures?2. Data Structure in JavaScript3. Array4. Stack5. Queue6. Linked List7. Hash Table8. Trees9. Graphs10. Sample Example
What are Data Structures?
Data sctructures are techniques for store and organize data to make it easier to modify, navigate, and access. Data structures are used in almost all areas of computer science and programming, from operating systems to basic vanilla code to artificial intelligence.
Data structures enable us to:
- Manage and utilize large datasets
- Search for particular data from a database
- Design algorithms that are tailored towards particular programs
- Handle multiple requests from users at once
- Simplify and speed up data processing
Data Structure in JavaScript
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 are not defined by the programming language but rather by the programmer. These include linear data structures, static data structures, and dynamic data structures, like queue and linked lists.
Array
This is a basic data structure. Maybe every JavaScript programmer or developer used this one. Array is foundational building block for complex data structures. We can store data in an array and call them by index number. we can also insert and delete an element. Some methods in array:
1. push()
2. pop()
3. unshift()
4. shift()
5. splice()
6. concat()
7. slice()
etc.Stack
A stack is an abstract data type that serves as a collection of elements, with two principal operations:
- push, which adds an element to the collection, and
- pop, which removes the most recently added element that was not yet removed.
Stack work in LIFO (Last In Fast Out) style. The last item we pushed on the stack will be the first one removed. The back button in web browsers is a good example: each page we view is added to the stack, and when we click back, the current page (the last one added) is popped from the stack.
We can see this example:
It’s easy to understand because of comment out, isn’t it?
Queue
The queue is quite similar with stack. The key difference between the stack and the queue is that the queue follow FIFO (First In First Out) style.
Look at the above image, we can see the side of in and out. In queue, if we insert a value it will go forward. For example, here we insert ‘A’ as the very fast element, then ‘B’. Now if we want to delete an element, we need to delete the element ‘A’ first, then ‘B’.
Maybe you got the idea of queue.
You can also see this example to know how a queue work:
It’s also easy.
Linked List
A linked list is mostly used for languages that do not have dynamic sizing arrays. Linked lists organize items sequentially, with each item pointing to the next item.
Each node in a linked list has a data value and a next value. Below, 5 is the data value, and the next value points to the next node, i.e., the node that has the value 10.
Visually, it looks like this:
Hash Table
A hash table (hash map) is a data structure which implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found
Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions must be accommodated in some way.
Trees
Trees are another relation-based data structure, which specialize in representing hierarchical structures. Like a linked list, nodes contain both elements of data and pointers marking its relation to immediate nodes.
Each tree has a “root” node, off of which all other nodes branch. The root contains references to all elements directly below it, which are known as its “child nodes”. This continues, with each child node, branching off into more child nodes.
Nodes with linked child nodes are called internal nodes while those without child nodes are external nodes. A common type of tree is the “binary search tree” which is used to easily search stored data. These search operations are highly efficient, as its search duration is dependent not on the number of nodes but on the number of levels down the tree.
Many kinds of trees:
- Binary Search Tree
- AVL Tree
- Red-Black Tree
- Segment Tree - with min/max/sum range queries examples
- Fenwick Tree (Binary Indexed Tree)
Graphs
A graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics, specifically the field of graph theory
A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.
Example:
Sample Example
The seven elements A, B, C, D, E, F and G are pushed onto a stack in reverse
order, i.e., starting from G. The stack is popped five times and each element is
inserted into a queue. Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. So what is the value of popped item?
First think about this and try it your self.
If you find the answer, that will be great. But if you can’t, don’t worry. Look at the below:
In fig:-1 elements are inserted into a stack then in fig:-2 top 5 elements are popped and these 5 elements are inserted into a queue which is shown in fig:-3, now first two elements are deleted from queue and pushed into stack one by one which is shown in fig:-5.
At top of the stack element B is presented.
So, ‘B’ is the correct answer.
