What are Data Structures and why are they Important
Data Structures are way of organizing data that is stored in a computer or database. Each type of data structure represents a different way of organizing the data.
There are different types of data structures because they have different strengths and weaknesses.
Some are fast at storing and slow at retrieving and some vice-versa.
Importance of Data Structures:
– Data structures have big impact on performance, quick and efficiently a program runs. Example, when we need to store data at a faster pace, we can use linked list. Or when we need to access data quickly, we can use a hash table.
– Reinforce knowledge of JavaScript algorithms and other important concepts
2. Constructor functions and the ‘this’ keyword
Constructor function – A function that creates an Object class and allows to create multiple instances of the class.
function User(firstName, lastName) {
this.firstName = firstName;
this.lastName = lastName;
}
var user1 = new User('Murari', 'Nayak');
3. The prototype object
It simply is an Object that other objects can refer to for functionalities.
User.prototype.emailDomain = '@gmail.com';
SECTION 2 – Linked Lists
4. What is a Linked List
Linked list is a series of node in a single line.
Single Linked List – When the node has the reference to it’s next node.
Double Linked List – When the node has the reference to the next node as well as the previous one.
Has a head-pointer and a tail-pointer to know about the head and tail of the double linked list.
5. Linked List and Node Constructor Functions
function LinkedList() {
this.head = null;
this.tail = null; // Not passed to parameters as there is no head or tail
// until a Node is added to the LinkedList.
}
function Node(value, next, prev) {
this.value = value;
this.next = next;
this.prev = prev;
}
var userList = new LinkedList();
var todoList = new LinkedList();
var node1 = new Node(100, 'node2', null);
6. Add to Head – Part 1
LinkedList.prototype.addToHead = function(value) {
var newNode = new Node(value, this.head, null);
// this.head returns the current head in the LinkedList if items exist,
//else gives the default null as it is set by default in a new LinkedList.
};
7. Add to Head – Part 2
LinkedList.prototype.addToHead = function(value) {
var newNode = new Node(value, this.head, null);
if (this.head) {
// When there are nodes earlier
this.head.prev = newNode;
} else {
// When there were no nodes earlier
this.tail = newNode;
}
this.head = newNode;
};
8. Using Add To Head
var ll = new LinkedList();
ll.addToHead(100);
ll.addToHead(200); // You can see Circular reference from here
ll.addToHead(300);
9. Add to Tail
LinkedList.prototype.addToTail = function(value) {
var newNode = new Node(value, , null, this.tail);
if (this.tail) {
this.tail.next = newNode;
} else {
this.head = newNode;
}
this.tail = newNode;
}
10. Testing Add To Tail and Add To Head
var myLL = new LinkedList():
myLL.addToTail(10);
myLL.addToTail(20);
myLL.addToTail(30);
myLL.addToHead(100);
11. Remove Head
LinkedList.prototype.removeHead = function() {
if (!this.head) {
return null;
}
var val = this.head.value;
this,head = this.head.next;
if (this,head) {
this.head.prev = null;
} else {
this.tail = null;
}
return val;
}
myLL.removeHead();
12. Remove Tail
LinkedList.prototype.removeTail = function() {
if (this.tail) {
return null;
}
var val = this.tail.value;
this.tail = this,head.prev;
if (this.tail) {
this.tail.next = null;
} else {
this.head = null;
}
return val;
};
newLL.removeTail();
13. Search Method
LinkedList.prototype.search = function(searchValue) {
var currentNode = this.head;
while (currentNode) {
if (currentNode.value === searchValue) {
return currentNode.value;
}
currentNode = currentNode.next;
}
return null;
};
14. Testing Search
myLL.search(100);
15. LinkedList – Independent Exercise
Create an indexOf function in the LinkedList
— My try
LinkedList.prototype.indexOf = function(searchValue) {
let counter = 0;
let indexes = [];
let currentNode = this.head;
while(currentNode) {
if (currentNode.value === searchValue) {
indexes.push(counter);
}
currentNode = currentNode.next;
counter++;
}
return indexes;
}
16. LinkedList – Exercise Review
— Similar to the one above.
17. Big O Notation and Calculating the runtime of a Function
It is a notation used to signify how scalable n algrorithm or a function is and lets us determine the worst case runtime of an algorthm or how long it takes for the algorithm to complete based on the input size.
Get the graph with all the 4 notations.
function log(array) {
console.log(array[0]);
console.log(array[1]);
}
log([1,2,3,4]);
log([1,2,3,4,5,6,7,8,9]);
This function has a constant runtime and is denoted as O (1)
function logAll(array) {
array.forEach(item => {
console.log(item);
});
}
logAll([1,2,3,4]);
logAll([1,2,3,4,5,6,7,8,9]);
This function has a Linear runtime and is denoted as O (n)
Here the runtime increases inline with the number of elements.
function addAndLog(array) {
for (var i = 0; i < array.length; i++) {
for (var j = 0; j < array.length; j++) {
console.log(array[i] + array[j]);
}
}
}
addAndLog(['A', 'B', 'C']); // 9
addAndLog(['A', 'B', 'C', 'D']); // 16
This function has an exponential runtime and is denoted as O (n^2)
function binarySearch(array, key) {
var low = 0;
var high = array.length - 1;
var mid;
var element;
while (low <= high) {
mid = Math.floor((low + high) / 2), 10);
element = array[mid];
if (element < key) {
low = mid + 1;
} else if (element > key) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
This one is like searching for a word in a dictionary.
This has a logarithmic runtime and is denoted by O (log n)
This is because, for every iteration, we are removingh alf of the elements from the search array.
An iteration of around 4000 elements can be done with 12 iteration.
This is the best form of time conplexoty a program can have.
18. Big O Notation and Runtime Source Code
The source code as written above.
19. LinkedList Wrap Up
Constant Time – O (1) for Adding/Removing Head/Tail
Linear Time – O (n) for Searching through the LinkedList
Practical use cases include online gaming like poker, board games, dominoes
A circular LinkedList is used for the gaming.
Q. Why LinkedList is a preferred data-structures in many low level languages.
A. This is because, in case of LinkedList, the data doesn’t have to be stored togeher and can be kept around with the broken pieces.
It’s very efficient with memory space.
20. Linked List Source Code
— Basically the source code of the entire section.
SECTION 3 – BINARY SEARCH TREES
21. What is a Binary Search Tree
A colection of nodes which are connected in a certain way.
Every node can have 2 child nodes known as left node and right node.
Here we are going to build a Number BInary Search Tree. However it can be made with any type of data.
All of the left nodes will have smalled or equal value in the left node and the larger ones will be added to the right node.
In this case, rather than calling nodes, they can be called as Binary Serach Tree (BST), because every node is a Binrary Search Tree with 2 child nodes.
We will go thorugh adding to the system, which will include 2 types of traversal methods namely,
– Depth First Traversal – Start at the top and follow each branch all the way to the bottom.
– Breadth First Traversal – Start at the top, but move across levels before moving to the next level.
On each node, we are going to run some functions. And to go through recyursion needs to be understood, because BST are recusrsive in nature.
22. Recursion – Part 1
A function that calls itself.
For a function to be properly recursive, it needs to have 2 parts:
– A base case which will return something
– Recursive case, where the function is going to call itself.
function myFunc() {
if (baseCase)
return info;
else // recursive case
myFunc(); // call the function again;
}
Factorial
4! = 4 * 3 * 2 * 1 = 24
function factorial(num) {
if (num <== 2) {
return num;
} else {
return num * factorial(num-1);
}
}
23 – Recursion Part 2 and the Call Stack
Snapshot
24. Insert Method
functiom BST(value) {
this.value = value;
this.left = null;
this.right = null;
}
BST.prototype.insert = function(value) {
if (value <= this.value) {
if (this.left) {
this.left.insert(value);
} else {
this.left = new BST(value);
}
} else {
if (this.right) {
this.right.insert(value);
} else {
this.right = new BST(value);
}
}
};
25. Testing Insert method
var bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(100);
bst.insert(69);
console.log(bst.left.right);
26. Contains Method
BST.prototype.contains = function(value) {
if (!value) {
return false;
}
if (value === this.value) {
return true;
} else {
if (value < this.value) {
if (this.left) {
return this.left.contains(value);
} else {
return false;
}
} else {
if (this.right) {
return this.right.contains(value);
} else {
return false;
}
}
}
};
console.log(bst.contains(100));
28. Depth-First Traversal-in-Order
BST.prototype.depthFirstTraversal = function(iteratorFunc) {
if (this.left) {
this.left.depthFirstTraversal(iteratorFunc);
}
iteratorFunc(this.value);
if (this.right)
this.right.depthFirstTraversal(iteratorFunc);
}
};
29. Testing Depth First Traversal-in-Order
function log(value) {
console.log(value);
}
bst.depthFirstTraversal(log);
// This should log the whole data in incremental values. // 10,15,45, 70,100
30. Refactoring Depth-First Traversal Method
BST.prototype.depthFirstTraversal = function(iteratorFunc, order) {
if (this.left) {
this.left.depthFirstTraversal(iteratorFunc, order);
}
if (order === 'in-order') {
iteratorFunc(this.value);
}
if (this.right) {
this.right.depthFirstTraversal(iteratorFunc, order);
}
};
bst.depthFirstTraversal(log, 'in-order');
31. Depth-First Traversal – Pre-Order
Helpful to create a copy of the BST
BST.prototype.depthFirstTraversal = function(iteratorFunc, order) {
if (order === 'pre-order') {
iteratorFunc(this.value);
}
if (this.left) {
this.left.depthFirstTraversal(iteratorFunc, order);
}
if (order === 'pre-order') {
iteratorFunc(this.value);
}
if (this.right) {
this.right.depthFirstTraversal(iteratorFunc, order);
}
};
32. Testing Depth-First Traversal Pre-Order
bst.depthFirstTraversal(log, 'pre-order');
33. Depth-First Traversal – Post-Order
BST.prototype.depthFirstTraversal = function(iteratorFunc, order) {
if (order === 'pre-order') {
iteratorFunc(this.value);
}
if (this.left) {
this.left.depthFirstTraversal(iteratorFunc, order);
}
if (order === 'in-order') {
iteratorFunc(this.value);
}
if (this.right) {
this.right.depthFirstTraversal(iteratorFunc, order);
}
if (order === 'post-order') {
iteratorFunc(this.value);
}
};
bst.depthFirstTraversal(log, 'post-order');
This helps while deleting the nodes in a BST as it starts from the bottom.
34. Breadth-First Traversal – Part 1
BST.prototype.breadthFirstTraversal = function(iteratorFunc) {
var queue = [];
};
This is helpful for viewing organizational charts finding who all come at the same level.
For this we need to have queue FIFI (First In First Out)
So we would process a node and add it’s children to the queue and then process them while adding their children to the queue. Then we can popup out the node we are working at.
35. Breadth-First Traversal – Part 2
BST.prototype.breadthFirstTraversal = function(iteratorFunc) {
var queue = [this];
while (queue.length) {
var treeNode = queue.shift();
iteratorFunc(treeNode);
if (treeNode.left) {
queue.push(treeNode.left);
}
if (treeNode.right) {
queue.push(treeNode.right);
}
}
};
36. Testing Breadth-First Traversal
function log(node) {
console.log(node.value);
}
bst.breadthFirstTraversal(log);
37. Binary Search Tree – Independent Exercise
getMinVal and getMaxVal
BST.prototype.getMinValue = function() {
currentValue = this.value;
if (this.left) {
return this.left.getMinValue();
} else {
return currentValue;
}
};
BST.prototype.getMaxValue = function() {
currentValue = this.value;
if (this.right) {
return this.right.getMaxValue();
} else {
return currentValue;
}
};
38. Binary Search Tree – Exercise Review
BST.prototype.getMinVal = function() {
if (this.left) {
return this.left.getMinVal();
} else {
return this.value;
}
};
BST.prototype.getMaxVal = function() {
if (this.right) {
return this.right.getMaxVal();
} else {
return this.value;
}
};
39. Binary Search Tree – Wrap Up
BST are great for both inserting and retrieving data.
These are most performing when they are balanced, meaning having child on both right and left.
Better for Dictionary, Phone Book, Users listing
40. Binary Search Tree – Source code
The source code of the whole module.
function BST(value) {
this.value = value;
this.right = null;
this.left = null;
}
BST.prototype.insert = function(value) {
if (value <= this.value) {
if (!this.left) this.left = new BST(value);
else this.left.insert(value);
}
else if (value > this.value) {
if (!this.right) this.right = new BST(value);
else this.right.insert(value);
}
};
BST.prototype.contains = function(value) {
if (this.value === value) return true;
if (value < this.value) {
if (!this.left) return false;
else return this.left.contains(value);
}
else if (value > this.value) {
if (!this.right) return false;
else return this.right.contains(value);
}
};
BST.prototype.depthFirstTraversal = function(iteratorFunc, order) {
if (order === 'pre-order') iteratorFunc(this.value);
if (this.left) this.left.depthFirstTraversal(iteratorFunc, order);
if (order === 'in-order') iteratorFunc(this.value);
if (this.right) this.right.depthFirstTraversal(iteratorFunc, order);
if (order === 'post-order') iteratorFunc(this.value);
};
BST.prototype.breadthFirstTraversal = function(iteratorFunc) {
var queue = [this];
while (queue.length) {
var treeNode = queue.shift();
iteratorFunc(treeNode);
if (treeNode.left) queue.push(treeNode.left);
if (treeNode.right) queue.push(treeNode.right);
}
};
function log(value) {
console.log(value);
};
BST.prototype.getMinVal = function() {
if (this.left) return this.left.getMinVal();
else return this.value;
};
BST.prototype.getMaxVal = function() {
if (this.right) return this.right.getMaxVal();
else return this.value;
};
var bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(100);
bst.insert(60);
bst.insert(59);
bst.insert(20);
bst.insert(45);
bst.insert(35);
bst.insert(85);
bst.insert(105);
bst.insert(10);
function log(node) {
console.log(node.value);
}
bst.breadthFirstTraversal(log);
SECTION 4 – HASH TABLES
41. What is a Hash Table
Hash table is the fastest data structure that is avaiable with O (1) runtime.
Here data is stored in key: value pair where key is a string and value can be of any data type.
[ , , , , , , , , ]
{ ‘murari’: ‘some address’ } – The key is then hashed and then the whole key-value pair is stored in the hash container at the hashed key position.
Will require:
– insert
– get
– hash function
42. HashTable and HashNode Constructor Functions
function HashTable(count) {
this.
}
function HashNode(key, value, next) {
this.key = key;
this.value = value;
this.next = next;
}
var myHT = new HashTable(30);
43. charCodeAt Method and the Modulus Operator
charCodeAt can be run over a string and passing an index into it will provide the UniCode of the given character.
"hello".charCodeAt(4); // 111 - The UniCode of character 'o'
Modulus returns the remainder of a division.
console.log(100 % 30) - Logs 10
44. Hash Method
HashTable.prototype.hash = function(key) {
var total = 0;
for (var i = 0; i < key.length; i++) {
total += key.charCodeAt(i);
}
return total % this.buckets.length;
};
45. Insert Method
HashTable.prototype.insert = function(key, value) {
var index = this.hash(key);
if (this.buckets[index]) {
this.buckets[index] = new HashNode(key, value);
} else {
let currentNode = this.buckets[index];
while(currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = new HashNode(key, value);
}
};
46. Testing Insert Method
myHT.insert('dean', 'dean@gmail.com');
myHT.insert('rocky', 'rocky@gmail.com');
myHT.insert('dane', 'dane@gmail.com'); // This will get the same hash as that of 'dean',
// but will be stored in a LinkedList in the bucket.
console.log(myHT);
47. Refactoring Insert Method
We can use the same insert() to also update the items by refactoring a little.
HashTable.prototype.insert = function(key, value) {
var index = this.hash(key);
if (this.buckets[index]) {
this.buckets[index] = new HashNode(key, value);
} else {
let currentNode = this.buckets[index];
if (currentNode.key === key) {
currentNode.value = value;
return;
}
while(currentNode.next) {
if (currentNode.next.key === key) {
currentNode.next.value = value;
return;
}
currentNode = currentNode.next;
}
currentNode.next = new HashNode(key, value);
}
};
48. Testing Refactored Insert Method
myHT.insert('dean', 'dean@gmail.com');
...
myHT.insert('dean', 'dean@yahoo.com'); // This will update the previous dean value.
49. Get Method
HashTable.prototype,get = function(key) {
var index = this.hash(key);
if (this.buckets[index]) {
var currentNode = this.buckets[index];
while (currentNode) {
if (currentNode.key === key) {
return currentNode.value;
}
currentNode = currentNode.next;
}
return null;
} else {
return null;
}
};
50. Testing Get Method
...
myHT.get('dean'); // Should log the email.
51. HashTable – Independent Exercise
HashTable.prototype.retrieveAll = function() {
const list = [];
for (var i = 0; i < this.buckets.length; i++) {
let node = this.buckets[i]
if (node) {
list.push({key: node.key, value: node.value});
while (node.next) {
node = node.next;
if (node) {
list.push({key: node.key, value: node.value});
}
}
}
}
return list;
}; // Also have a simplified version.
52. HashTable – Exercise Review
53. HashTable Wrap Up
HashTable are very fast in storing and fetching data with constant time complexity of O (1)
Pros:
– Constant time insertion
– Constant time lookup
Practical Uses:
– Email provider storing database
– Users of an application with the username as the key and the user object as the value;
Cons:
Data doesn’t store references to other pieces of data in the data structure. // This can be achieved by using other properties.
54. HashTable Source Code
function HashTable(size) {
this.buckets = Array(size);
this.numBuckets = this.buckets.length;
}
function HashNode(key, value, next) {
this.key = key;
this.value = value;
this.next = next || null;
}
HashTable.prototype.hash = function(key) {
var total = 0;
for (var i = 0; i < key.length; i++) {
total += key.charCodeAt(i);
}
var bucket = total % this.numBuckets;
return bucket;
};
HashTable.prototype.insert = function(key, value) {
var index = this.hash(key);
if (!this.buckets[index]) {
this.buckets[index] = new HashNode(key, value);
} else if (this.buckets[index].key === key) {
this.buckets[index].value = value;
} else {
var currentNode = this.buckets[index];
while (currentNode.next) {
if (currentNode.next.key === key) {
currentNode.next.value = value;
return;
}
currentNode = currentNode.next;
}
currentNode.next = new HashNode(key, value);
}
};
HashTable.prototype.get = function(key) {
var index = this.hash(key);
if (!this.buckets[index]) return null;
else {
var currentNode = this.buckets[index];
while (currentNode) {
if (currentNode.key === key) return currentNode.value;
currentNode = currentNode.next;
}
return null;
}
};
HashTable.prototype.retrieveAll = function() {
var allNodes = [];
for (var i = 0; i < this.numBuckets; i++) {
var currentNode = this.buckets[i];
while(currentNode) {
allNodes.push(currentNode);
currentNode = currentNode.next;
}
}
return allNodes;
};
var myHT = new HashTable(30);
myHT.insert('Dean', 'dean@gmail.com');
myHT.insert('Megan', 'megan@gmail.com');
myHT.insert('Dane', 'dane@yahoo.com');
myHT.insert('Dean', 'deanmachine@gmail.com');
myHT.insert('Megan', 'megansmith@gmail.com');
myHT.insert('Dane', 'dane1010@outlook.com');
You can also check out ‘Algorithms in JavaScript‘.