I recently decided to make a LinkedList
and binary search tree using JavaScript. I wanted to reach out to a wider audience and see how I did, and where could I improve.
var Node = function(value) {
this.value = value;
this.next=null;
return this;
};
var LinkedList = function(node){
this.head = node;
return this;
};
LinkedList.prototype.insertEnd = function(newNode, currentNode) {
var currentNode = currentNode || this.head;
if(currentNode.next !== null) {
return this.insertEnd(newNode, currentNode.next);
} else {
currentNode.next = newNode;
}
};
LinkedList.prototype.insertBeginning = function(newNode) {
newNode.next = this.head;
this.head = newNode;
};
LinkedList.prototype.search = function(searchValue, currentNode) {
var currentNode = currentNode || this.head;
if(currentNode.value == searchValue) {
console.log("true");
return true;
} else if(currentNode.next !== null) {
return this.search(searchValue, currentNode.next);
}
console.log("not found");
return false;
};
LinkedList.prototype.remove = function(deleteValue, currentNode, parentNode) {
currentNode = currentNode || this.head;
if(currentNode.value === deleteValue) {
if(currentNode.next !== null) {
parentNode.next = currentNode.next;
} else {
parentNode.next = null;
}
} else if(currentNode.next !== null) {
return this.remove(deleteValue, currentNode.next, currentNode);
}
};
LinkedList.prototype.size = function(currentNode, size) {
var currentNode = currentNode || this.head;
var size = size || 1;
if(currentNode.next !== null) {
return this.size(currentNode.next, size+1);
} else {
console.log(size);
return size;
}
};
(function(){
// LinkedList Example
var linkedList = new LinkedList(new Node("oldHead"));
linkedList.insertEnd(new Node(2));
linkedList.insertEnd(new Node("cat"));
linkedList.insertEnd(new Node("dog"));
linkedList.insertEnd(new Node(100));
linkedList.search("cat");
linkedList.size();
linkedList.remove("cat");
linkedList.size();
linkedList.search("cat");
console.log("current head: "+linkedList.head.value);
linkedList.insertBeginning(new Node("testBeginningInsert"));
console.log("current head: "+linkedList.head.value);
linkedList.size();
})();
var Node = function(value) {
this.value = value;
this.left = null;
this.right = null;
return this;
};
Node.prototype.insert = function(newNode) {
if(newNode.value < this.value) {
if(this.left === null) {
this.left = newNode;
} else {
this.left.insert(newNode);
}
} else if(newNode.value > this.value) {
if(this.right === null) {
this.right = newNode;
} else {
this.right.insert(newNode);
}
} else {
return true;
}
};
Node.prototype.depthFirstSearch = function(searchValue) {
console.log(searchValue+": "+this.value);
if(this.value === searchValue) {
console.log("search item found");
return true;
} else if(searchValue < this.value && this.left !== null) {
return this.left.depthFirstSearch(searchValue);
} else if(searchValue > this.value && this.right !== null) {
return this.right.depthFirstSearch(searchValue);
} else {
console.log("could not find "+searchValue);
return false;
}
};
Node.prototype.inorderTraversal = function() {
if(this.left !== null) {
this.left.inorderTraversal();
}
console.log(this.value);
if(this.right !== null) {
this.right.inorderTraversal();
}
};
Node.prototype.preOrderTraversal = function() {
console.log(this.value);
if(this.left !== null) {
this.left.preOrderTraversal();
}
if(this.right !== null) {
this.right.preOrderTraversal();
}
};
Node.prototype.postOrderTraversal = function() {
if(this.left !== null) {
this.left.postOrderTraversal();
}
if(this.right !== null) {
this.right.postOrderTraversal();
}
console.log(this.value);
};
var BinarySearchTree = function(insertNode) {
if(insertNode instanceof Node) {
this.root = insertNode;
} else {
this.root = new Node(insertNode);
}
return this;
};
BinarySearchTree.prototype.insert = function(insert) {
if(insert instanceof Node) {
this.root.insert(insert);
} else {
this.root.insert(new Node(insert));
}
};
BinarySearchTree.prototype.depthFirstSearch = function(searchValue) {
this.root.depthFirstSearch(searchValue);
};
BinarySearchTree.prototype.breadthFirstTraversal = function() {
console.log("Breadth First Traversal");
// For our intensive purposes,
// our array is acting as a queue for us.
var queue = [],
current = this.root;
if(current !== null) {
queue.push(current);
}
// start off enqueing root
while(queue.length > 0) {
var tempNode = queue.shift();
console.log(tempNode.value); // Visit current node
if(tempNode.left !== null) {
queue.push(tempNode.left);
}
if(tempNode.right !== null) {
queue.push(tempNode.right);
}
}
};
BinarySearchTree.prototype.inOrderTraversal = function(){
this.root.inorderTraversal();
};
BinarySearchTree.prototype.preOrderTraversal = function(){
this.root.preOrderTraversal();
};
BinarySearchTree.prototype.postOrderTraversal = function(){
this.root.postOrderTraversal();
};
// Gotta not hurt dat global namespace
(function(){
// Example BinBinarySearchTree
var bst = new BinarySearchTree(50);
bst.insert(25);bst.insert(75);bst.insert(12);bst.insert(37);bst.insert(87);bst.insert(63);
console.log("Inorder Traversal");
bst.inOrderTraversal();
console.log("Preorder Traversal");
bst.preOrderTraversal();
console.log("Postorder Traversal");
bst.postOrderTraversal();
console.log("Search for valid (63)");
bst.depthFirstSearch(63);
console.log("Search for invalid (19)");
bst.depthFirstSearch(19);
bst.breadthFirstTraversal();
})();