The main principle of queue datastructure is FIFO (First in First Out). If we compare with real life queue example, people standing in a queue are nodes. Queue implementation can be done in two ways: using array and using object.
Implement Queue using array:
First we create an array named queue.
Second we push some elements using push()
Third we remove elements using shift()
Fourth to check if the queue is empty we use queue.length and see whether empty or not
// Initializing queue array.
var queue = [];
// Inserting vales into the queue.
queue.push(1);
queue.push(2);
queue.push(3);
queue.push(4);
queue.push(5);
console.log("The current queue is: ", queue);
// Removing element form queue using array method: shift()
var removed_element = queue.shift();
console.log("Removed element is: ", removed_element);
console.log("The current queue is: ", queue);
// We can check the if the queue is empty or not using the array.length method.
if (queue.length > 0) {
console.log("The Queue is not empty!");
} else {
console.log("The Queue is empty!");
}
While working with javascript we often use this popular method console.log(). During debugging when we need some insight about the happenings we use console.log(). There are a lot more methods to debug your code alternative to console.log(). These alternative console.log() methods are useful in data visualization, debugging etc.,
Alternative to console.log():
1.console.table()
This console.table() method is useful when we want to get a visual form of a group of objects that can be represented in a tabular form. It takes one mandatory argument data, which must be an array or an object, and one additional optional parameter columns. For example let us take 2 employee details and see in console.log() and console.table() methods
This console.assert() is great for debugging process. It takes an assertion and writes an error message when the assertion is false. If it is true nothing happens. Mainly used while debugging code. For example lets check whether a number is even and throw an error message if it is not.
const isEven = n => n % 2 === 0;
for (let i = 0; i < 3; i++)
{
console.assert(isEven(i), '%s is not even!', i);
}
3.console.count()
console.count() is used to count the number of times the line has been called.
for (let i = 0; i < 3; i++){
console.count();
}
4.console.trace()
console.trace() helps you output the current stack trace at the location where you call it from. This helps in displaying a trace that show how the code ended up at a certain point.
function a() {
b();
}
function b() {
c();
}
function c() {
console.trace();
}
a();
5.console.error()
console.error() is the second most popular method. It displays the error message.
console.error('This is an error message');
6.console.dir()
This method console.dir() will display the interactive view of the objects we want to log.
console.warn() displays the warn message in yellow color.
console.warn('This is a warning message');
8.console.time()
console.time() is used to measure how long a particular operation in a program takes. This starts a timer you can use to track the time of a particular operation
console.time();
for (let i = 0; i < 100; i++) {
// some code
}
console.timeEnd();
9.console.group()
console.group adds a level of indentation to any methods that comes after it. console.groupEnd() resets the indentation to the level it was before.
console.group('group 1');
for (let i = 0; i < 3; i++) {
console.log(i);
}
console.groupEnd('group 1');
console.group('group 2');
for (let i = 0; i < 3; i++) {
console.log(i);
}
console.groupEnd('group 2');
Today we will implement linked list data structure in javascript. LinkedList is a dynamic data structure as it can add or remove elements easily.We have already seen about the brief introduction of linked list in previous article.
Linked list implementation:
LinkedList is made of nodes. Each element in a linkedlist is a node which contains a value and a pointer to next node. Each linked list consists of head, tail and length properties. Tail node points to null.
Node creation:
A node contains two items: value and the pointer to next node.
In the above code a class named node having two properties: element, next is defined. Element holds value of the node and next holds the pointer to next node. Here it is initialized to null.
Now let’s jump into linked list implementation.
Linked List creation:
class LinkedList{
//Creates a linkedlist with passed value.
constructor(value){
//Creates a head node
this.head = {
value: value,
next : null
};
//As there is only one element in the list, head is also a tail
this.tail = this.head;
//Length would be 1
this.length = 1;
}
}
Here a linked list class with a constructor is defined. Head node is initialized to null as there is one node in linked list.
To create an instance of linked list class:
console.log('Creating a LinkList');
const myLinkedList = new LinkedList(12);
console.log(myLinkedList);
Creates a Linked list with a value 12. As only one node is created head and tail are same nodes with value 12.
Output:
Print a Linked list:
This method is useful in printing a linked list.
printList(){
//Creates an empty array.
let printArrayList = [];
//Pointer which points to the head node
let currentNode = this.head;
//Start iterating from the first node till you reach the last node
while(currentNode !== null){
//Add every node's value to the array
printArrayList.push(currentNode.value);
//Point pointer to the next node
currentNode = currentNode.next;
}
//Return the array
return printArrayList.join(' -> ');
}
Add a new tail node using append()
We have seen about creating a node in a linked list. Now we will see about append() function. Every appended node becomes the new tail node.
append(value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
// Check if head is present or not, if head is empty creates a head
if (this.head == null){
this.head = node;
}
else{ //Else creates a tail
//We need to point current tail's next to the newNode
this.tail.next = newNode;
//Now make newNode a tail node
this.tail = newNode;
//Increase the length by 1
this.length++;
}
return this;
}
Now let’s try to append two nodes with value 22 and 26
console.log('Append Nodes with values 22 and 26:');
myLinkedList.append(22).append(26);
console.log(myLinkedList.printList());
How to add a new node in front of the linked list as head?
Answer is prepend() . To add a new head node we will move the current head node one position forward.
//Add the node as a head of the linkedlist
prepend(value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
//Points this node's next to the head
newNode.next = this.head;
//Now make this node a head node
this.head = newNode;
//Increase the length by 1
this.length++;
return this;
}
Prepend a node with value 6
console.log('Prepend Node with value 6:');
myLinkedList.prepend(6);
console.log(myLinkedList.printList());
Insert a node at a given index:
To insert a node at a given index we have to traverse through the list to the previous node and split the list into 2 parts. First merge the right side of list with the node and then assign left using pointer.
//Insertes a node at specified index, say we want to insert 18 at index 2
//Current list: 6 -> 12 -> 22 -> 26
insert(index, value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
//Counter to loop
let count = 1;
//Create a temp node to traverse through list, which will start from the head node
//Pointing to 6
let previousNode = this.head;
//Traverse the list one node before the specified index, which is previous node
while(count < index){
//Point previous node to next for iterating
previousNode = previousNode.next;
//Increase the count to compare it with index;
count++;
}
//When the loop ends you will be able to have a previous node. Which is 12 in this example.
//First, points new node's next to the previous node's next, so it can hold the list ahead of its index
//New node = 18, So new node will be 18 -> 22 -> 26
newNode.next = previousNode.next;
//Now just point previous node's next to new node.
//Merge left side of the list, 6 -> 12 -> 18 -> 22 -> 26
previousNode.next = newNode;
return this;
}
Let’s insert two node with value 18 at index 2 and value value 9 at index 1:
console.log('Inserting Node at index 2 with value : 18');
myLinkedList.insert(2,18);
console.log(myLinkedList.printList());
console.log('Inserting at index 1: 9');
myLinkedList.insert(1,9);
console.log(myLinkedList.printList());
console.log('');
Delete method:
It can be performed at 4 places
Delete head
Delete tail
Delete at index
Delete at node with value
Delete head:
It’s quite simple just delete the head and make the next element as new head.
Deleting a tail node with value 26 and making node with value 22 as new tail
console.log('Deleting Tail-Node with value 26');
myLinkedList.deleteTail();
console.log(myLinkedList.printList());
console.log('');
Delete a node by index:
First we need to check whether the deleting node is head or not. Then traverse to the previous node and point its next to next.next.
deleteAtIndex(index){
//Check if index is head
if(index === 0){
//Appoint head to the next element
this.head = this.head.next;
this.length--;
return this;
}
let count = 1;
let previousNode = this.head;
while(count < index){
previousNode = previousNode.next;
count++;
}
previousNode.next = previousNode.next.next;
this.length--;
return this;
}
Now let us delete the node at index 2 with value 18
console.log('Deleting Node at index 2 with value 18:');
myLinkedList.deleteAtIndex(2);
console.log(myLinkedList.printList());
console.log('');
Delete a node by value:
Here we need 2 pointers. One to traverse the list and the other to point the previous node.
deleteNodeByValue(value){
//Current node to loop through the list
let currentNode = this.head;
//Previous node to update its pointer to next.next node
let previousNode = null;
while(currentNode != null){
//Check if we find the value we are looking for
if(currentNode.value === value){
//Check if it is a head or not by comparing previous node with null
if (previousNode === null) {
//If it is head, then update head to nextnode
this.head = currentNode.next;
}
else{
//If it is not head then simply update previous node
previousNode.next = currentNode.next;
}
//Reduce length by 1
this.length--;
}
//Previous node will point to this node with every iteration
previousNode = currentNode;
//Current node will point to next node for iteration
currentNode = currentNode.next;
}
return this;
}
We will delete the node with value 22
console.log('Deleting Node with value 22:');
myLinkedList.deleteNodeByValue(22);
console.log(myLinkedList.printList());
console.log('');
By now we have seen about creation, insertion, append, prepend, deletion of linked list.
Let’s jump into searching
Search a linked list:
Traverse through the list, compare the value and return true or false.
Here we will search for two elements 12 and 22 one is in the list and the other is not in the list. So it must return true for 12 and false for 22.
console.log('Searching for value 12:');
console.log(myLinkedList.printList());
console.log(myLinkedList.searchElement(12));
console.log('Searching for value 22:');
console.log(myLinkedList.searchElement(22));
Complete Linked List implement Code:
class Node {
constructor(value){
this.value = value,
this.next = null
}
}
class LinkedList{
//Creates a linkedlist with passed value.
constructor(value){
//Creates a head node
this.head = {
value: value,
next : null
};
//As there is only one element in the list, head is also a tail
this.tail = this.head;
//Length would be 1
this.length = 1;
}
append(value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
// Check if head is present or not, if head is empty creates a head
if (this.head == null){
this.head = node;
}
else{ //Else creates a tail
//We need to point current tail's next to the newNode
this.tail.next = newNode;
//Now make newNode a tail node
this.tail = newNode;
//Increase the length by 1
this.length++;
}
return this;
}
//Add the node as a head of the linkedlist
prepend(value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
//Points this node's next to the head
newNode.next = this.head;
//Now make this node a head node
this.head = newNode;
//Increase the length by 1
this.length++;
return this;
}
//Insertes a node at specified index, say we want to insert 18 at index 2
//Current list: 6 -> 12 -> 22 -> 26
insert(index, value){
//Create a new Node by creating a instance of a Node class
const newNode = new Node(value);
//Counter to loop
let count = 1;
//Create a temp node to traverse through list, which will start from the head node
//Pointing to 6
let previousNode = this.head;
//Traverse the list one node before the specified index, which is previous node
while(count < index){
//Point previous node to next for iterating
previousNode = previousNode.next;
//Increase the count to compare it with index;
count++;
}
//When the loop ends you will be able to have a previous node. Which is 12 in this example.
//First, points new node's next to the previous node's next, so it can hold the list ahead of its index
//New node = 18, So new node will be 18 -> 22 -> 26
newNode.next = previousNode.next;
//Now just point previous node's next to new node.
//Merge left side of the list, 6 -> 12 -> 18 -> 22 -> 26
previousNode.next = newNode;
return this;
}
deleteHead(){
this.head = this.head.next;
this.length--;
return this;
}
deleteTail(){
let secondLastNode = this.head;
while(secondLastNode.next.next !== null){
secondLastNode = secondLastNode.next;
}
secondLastNode.next = null;
this.length--;
return this;
}
deleteAtIndex(index){
//Check if index is head
if(index === 0){
//Appoint head to the next element
this.head = this.head.next;
this.length--;
return this;
}
let count = 1;
let previousNode = this.head;
while(count < index){
previousNode = previousNode.next;
count++;
}
previousNode.next = previousNode.next.next;
this.length--;
return this;
}
deleteNodeByValue(value){
//Current node to loop through the list
let currentNode = this.head;
//Previous node to update its pointer to next.next node
let previousNode = null;
while(currentNode != null){
//Check if we find the value we are looking for
if(currentNode.value === value){
//Check if it is a head or not by comparing previous node with null
if (previousNode === null) {
//If it is head, then update head to nextnode
this.head = currentNode.next;
}
else{
//If it is not head then simply update previous node
previousNode.next = currentNode.next;
}
//Reduce length by 1
this.length--;
}
//Previous node will point to this node with every iteration
previousNode = currentNode;
//Current node will point to next node for iteration
currentNode = currentNode.next;
}
return this;
}
searchElement(value){
let currentNode = this.head;
while(currentNode !== null){
if(currentNode.value === value) return true;
currentNode = currentNode.next;
}
return false;
}
printList(){
//Creates an empty array.
let printArrayList = [];
//Pointer which points to the head node
let currentNode = this.head;
//Start iterating from the first node till you reach the last node
while(currentNode !== null){
//Add every node's value to the array
printArrayList.push(currentNode.value);
//Point pointer to the next node
currentNode = currentNode.next;
}
//Return the array
return printArrayList.join(' -> ');
}
}
console.log('Creating a LinkList');
const myLinkedList = new LinkedList(12);
console.log(myLinkedList);
console.log('Append Nodes with values 22 and 26:');
myLinkedList.append(22).append(26);
console.log(myLinkedList.printList());
console.log('Prepend Node with value 6:');
myLinkedList.prepend(6);
console.log(myLinkedList.printList());
console.log('Inserting Node at index 2 with value : 18');
myLinkedList.insert(2,18);
console.log(myLinkedList.printList());
console.log('Inserting at index 1: 9');
myLinkedList.insert(1,9);
console.log(myLinkedList.printList());
console.log('');
console.log('Deleting Head-Node with value 6:');
myLinkedList.deleteHead();
console.log(myLinkedList.printList());
console.log('');
console.log('Deleting Tail-Node with value 26:');
myLinkedList.deleteTail();
console.log(myLinkedList.printList());
console.log('');
console.log('Deleting Node at index 2 with value 18:');
myLinkedList.deleteAtIndex(2);
console.log(myLinkedList.printList());
console.log('');
console.log('Deleting Node with value 22:');
myLinkedList.deleteNodeByValue(22);
console.log(myLinkedList.printList());
console.log('');
console.log('Searching for value 12:');
console.log(myLinkedList.printList());
console.log(myLinkedList.searchElement(12));
console.log('Searching for value 22:');
console.log(myLinkedList.searchElement(22));
call the getBinding() method to get the instance of sap.ui.model.Binding
From the instance of sap.ui.model.Binding, call the getPath() method. It returns the path of the Model to which the Binding happens. ( Code Example below)
pass the model path value in the method getModel() of sap.ui.model.Binding. It returns the sap.ui.model.Model instance.
var modelBindingInstance = mTableInstance.getBinding('items');
var modelPath = modelBindingInstance.getPath()
var modelInstance = modelBindingInstance.getModel(modelPath);
call the getBinding() method to get the instance of sap.ui.model.Binding
From the instance of sap.ui.model.Binding, call the getPath() method. It returns the path of the Model to which the Binding happens. ( Code Example below)
var modelBinding = mTableInstance.getBinding('items');
var pathOfModel = modelBinding.getPath();
JavaScript ES6 introduced two new data structures – maps and sets. These works similar to objects and arrays. Let’s see how to create a map data structure.
Map Data structure
A map is an ordered collection of key-value pairs. Maps are like objects. However, unlike objects maps are ordered and their keys need not be of string data type. They can be of any data type. Since it is ordered they can be iterable like arrays. Let’s see the syntax to create a map data structure.
Syntax:
let map = new Map([iterable])
let map = new Map()
Properties:
Map.prototype.size – returns the number of key-value pairs in Map object
Syntax:
Map.size
Methods:
set() – add/update a key value entry
get() – returns a value mapped to a specified key
has() – returns a Boolean indicating if a specific key exists or not
forEach() – executes a provided function for each key value pair
keys() – returns a new iterator object that contains the key of each element
values() – returns a new iterator object that contains the value of each element
entries() – returns a new iterator object that contains the [key, value] pairs of each element
delete() – removes specified elements from object map
clear() – removes all elements from object map
Now let us see some of the above methods properties with example.
let emp = new Map();
//set
emp.set('Name','John');
emp.set('ID','101');
emp.set('Salary','10000');
//get
emp.get('Name');
//size
console.log(emp.size);
//has
console.log(emp.has('ID'));
//keys
for (let key of emp.keys()) {
console.log(key);
}
//values
for (let value of emp.values()) {
console.log(value);
}
//entries
for (let entry of emp.entries()) {
console.log(entry);
}
//delete
console.log(emp.delete('Salary'));
console.log(emp.has('Salary'));
//clear
console.log(emp.size)
emp.clear();
console.log(emp.size)
Output:
How to convert object to map?
To create a map from object we can convert the object into an array of [key, value] pairs and then create a map using it.
Object.entries() – used to convert object to map.
let obj = {
"Name" : "John",
"ID" : "101";
"Salary" : "10000"
}
let newarr = Object.entries(obj);
let map = new Map(newarr);
console.log(map);
How to convert map to object?
Here we use object.fromEntries() to convert a map to object.
const map = new Map([['Name','John'],['ID','101'],['Salary','10000']]);
consr obj = Object.fromEntries(map);
console.log(obj);
Output:
To know more about javascript data structures click here!
Already we have seen stack data structure in detail. Now let’s jump into reverse a string using stack.
To reverse a string using Stack:
Create an empty stack.
Using push function push all the characters of the string to stack.
Using pop function remove all the characters of the string back.
function reverse(str){
let stack = [];
//push letter into stack
for (let i=0; i<str.length; i++){
stack.push(str[i]);
}
//pop letter from the stack
let reverseStr = '';
while(stack.length > 0){
reverseStr += stack.pop();
}
return reverseStr;
}
console.log(reverse('Abaython'));
We have already seen about Array Data Structure. Stack data structure is implemented using arrays. With push(), pop(), shift(), unshift() we create stack . For creation of stack we always prefer push() and pop(). Now let us implement stack data structure.
Methods to implement Stack Data Structure :
push() – adds an element at top of the stack
pop() – removes the top most element of the stack and if it is called on an empty stack returns ‘underflow’
peek() – similar to pop() returns top most element but does not delete it.
isEmpty() – return true if stack is empty.
printStack() – returns a string in which all elements of the stack are concatenated.
Program to implement Stack :
class Stack {
constructor() {
this.items = [];
}
// add element to the stack
add(element) {
return this.items.push(element);
}
// remove element from the stack
remove() {
if(this.items.length > 0) {
return this.items.pop();
}
}
// view the last element
peek() {
return this.items[this.items.length - 1];
}
// check if the stack is empty
isEmpty(){
return this.items.length == 0;
}
// the size of the stack
size(){
return this.items.length;
}
// empty the stack
clear(){
this.items = [];
}
}
let stack = new Stack();
stack.add(10);
stack.add(20);
stack.add(30);
stack.add(40);
console.log(stack.items);
stack.remove();
console.log(stack.items);
console.log(stack.peek());
console.log(stack.isEmpty());
console.log(stack.size());
stack.clear();
console.log(stack.items);
Already in previous post we have seen about the Data Strucutres in JavaScript. Now we will jump into the creation and implementation of arrays.
As you already know, array represents collection of similar data items. It is an object that stores multiple data items.
Array Declaration:
By array literal
Simplest way to create an array is by using array literal [ ].
Syntax:
let arrayname = [value1, value2, value3,….]
By new keyword
Syntax:
let arrayname = new Array();
//creates an array with 6 elements using array literal
var arr1 = [2,3,1,4,5,7];
//create array using new keyword
var arr2 = new Array(1,3,5,7,9,0);
//create an array with undefined elements
var arr3 = new Array();
//provide elements in arr3
arr3[0] = "Apple";
arr3[1] = "Orange";
arr3[2] = "Banana";
//create an array with 2 elements
var arr4 = new Array("Tom","Paul");
console.log(arr1);
console.log(arr2);
console.log(arr3);
console.log(arr4);
Output:
Accessing arrays:
Elements of an array are accessed using indexes.
var arr1 = [2,3,1,4,5,7];
//first element
console.log(arr1[0]);
//fourth element
console.log(arr1[3]);
Output:
2
4
Adding elements to an array:
We use push() and unshift( ) methods to add elements to an array.
push() method adds elements to the end of an array.
unshift() method adds elements to the start of an array.
It is done by length property. Returns the number of elements in an array.
let fruits = ["grapes","apple","orange","banana"];
console.log(fruits.length);
Output:
4
Methods in an array data structure:
In JavaScript arrays there are various methods available.
Methods
Description
concat()
joins two or more arrays and returns a result
indexOf()
searches an element of an array and returns its position
find()
returns the first value of an array element that passes a test
findIndex()
returns the first index of an array element that passes a test
forEach()
calls a function for each element
includes()
checks if an array contains a specified element
push()
adds a new element to the end of an array and returns the new length of an array
unshift()
adds a new element to the beginning of an array and returns the new length of an array
pop()
removes the last element of an array and returns the removed element
shift()
removes the first element of an array and returns the removed element
sort()
sorts the elements alphabetically in strings and in ascending order
slice()
selects the part of an array and returns the new array
splice()
removes or replaces existing elements and/or adds new elements
let fruits = ["grapes","apple","orange","banana"];
//sort in alphabetical order
fruits.sort();
console.log(fruits);
//find the index position
const pos = fruits.indexOf("apple");
console.log(pos);
//slicing array
const frutis1 = fruits.slice(2)
console.log(fruits1);
//concat two arrays
const frutis2 = frutis.concat(fruits1);
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.
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.