In this article, let’s try to understand the important data structures in javascript.
What is a Data Structure?
Data Structure is a storage that is used to store and organize data. It is a way of storing and organizing the data in such a way that it can be accessed more efficiently. It refers to group of data values, the relationship between them and the operations that can be performed on it. JavaScript has dynamic arrays i.e their size and type are not determined.
Now let us jump into the data structures in javascript.
1.Array Data Structure
Most popular linear data structure. All the elements are of same data type and stored in contiguous memory location. An array is represented by set of elements with index.
2.Stack Data Structure
Stack works on Last in First out(LIFO) principle. It is a linear data structure. It contains only one pointer and that points to the top element or last added element of the stack. Whenever we add or delete an element it is added or deleted from the top. Like a pile of books.
3.Queue Data Structure
Queue works on the principle of First in First out(FIFO). It is a linear data structure. It contains two-pointers front pointer and rear pointer. The front pointer contains address of the starting element and rear pointer contains address of the last element. The two main methods used for implementation. Enqueue is process of adding an element in the queue and dequeue is process of removing an element from the queue.
4.Linked List
Linked list is a linear data structure and here unlike arrays elements are stored in non-contiguous memory locations. It is made of group of nodes. Each node has its own data and address to the next node.
Here in linked list you have to start from head and work through the way to desired element. First element is head and last element is tail.
- List don’t have indexes, so we cannot access elements randomly.
- Insertion and deletion is more efficient we have to just redirect the pointers.
5.Trees
Tree is a non-linear data structure which consists of nodes connected by edges. This data structure link nodes via parent/child relationship. The top node is called root node and all the other nodes come off that node are called children. The nodes at the bottom of the tree are called leaf nodes. The height of the tree is determined by number of parent/child relationships it has.
Points to note:
- A connection is valid between nodes when it is from parent to child.
- Connection between siblings or child to parent are not valid.
- Tree must have only one root node.
Examples:
- File folders in our operating system
- DOM model
Popular Tree based data structure
- Binary Tree
- Binary Search Tree
- AVL Tree
- Red-Black Tree
- N-ary Tree
- 2-3 Tree
6.Graph Data Structure
Graphs are relation based data structure helpful in storing web-like or network relationships. It is made up of a finite collection of nodes called vertices, and the connections between them are known as edges. Graphs can be of two types: Directed graph and undirected graph.
Often used in Social networks, geolocalization(Google maps) and Web analytics.
7.Hash table
Hash table is also known as hash map or hash. Generally used in Object data structures, map or dictionary as it queries through a key and hash function. Hashing is a technique of mapping keys, values into the hash table using a hash function. Key is a searched string and value is the data paired with the key. Insertion and search function are very fast irrespective of the size of the table. Hash tables are built using arrays. In real life example of hash table is in schools each student is assigned a unique id number.
