Basic operations for Linked Lists: appending a Node, checking cycles, deleting Nodes by value, prepending a Node, and inserting a Node.
// ES5 compliant.
window.onload = function() {
function append(head, val) {
if (head == null) head = new LinkedList(val, null);
else {
var current = head;
while (current.next != null) {
current = current.next;
}
current.next = new LinkedList(val, null);
}
return head;
};
function prepend(head, val) {
if (head == null) head = new LinkedList(val, null);
else {
var current = head;
head = new LinkedList(val, current);
}
return head;
};
/** Remove by value not by index. */
function del(head, val) {
let current = head, arr = []
while (current != null) {
if (current.val != val) arr.push(current.val)
current = current.next
}
return buildList(arr);
};
/** - Starting At 1 */
function insrt(head, val, position) {
if (head == null) head = new LinkedList(val, null);
else {
var current = head;
var last = head;
for (var i = 1; i < position; i++) {
last = current;
current = current.next;
}
current = new LinkedList(val, current);
last.next = current;
}
return head;
};
function checkCycle(head) {
if (head == null) return false;
else {
var alreadyIn = [];
var current = head;
while (current != null) {
if (alreadyIn.indexOf(current.val) == -1) alreadyIn.push(current.val);
else return true;
current = current.next;
}
return false;
}
};
// Reinitialize each time
function init() {
return new LinkedList(1, new LinkedList(2, new LinkedList(3, new LinkedList(4, null))));
}
function cycle() {
return new LinkedList(1, new LinkedList(2, new LinkedList(1, null)));
}
var testA = init();
var expectationA = new LinkedList(1, new LinkedList(2, new LinkedList(3, new LinkedList(4, new LinkedList(5, null)))));
var resultA = append(testA, 5);
declare_result(traverseList(testA) + " append 5", traverseList(expectationA), traverseList(resultA), array_equals(traverseList(expectationA), traverseList(resultA)));
var testB = init();
var resultB = checkCycle(testB)
declare_result(traverseList(testB) + " check is cycle", false, resultB, resultB === false);
var testC = cycle();
var resultC = checkCycle(testC)
declare_result(traverseList(testC) + " check is cycle", true, resultC, resultC === true);
var testD = init();
var expectationD = new LinkedList(5, new LinkedList(1, new LinkedList(2, new LinkedList(3, new LinkedList(4, null)))));
var resultD = prepend(testD, 5)
declare_result(traverseList(testD) + " prepend 5", traverseList(expectationD), traverseList(resultD), array_equals(traverseList(expectationD), traverseList(resultD)));
var testE = null;
var resultE = del(testE, 3);
declare_result("null delete 3", null, null, null === resultE);
var testF = init();
var expectationF = new LinkedList(1, new LinkedList(2, new LinkedList(4, null)));
var resultF = del(testF, 3)
declare_result(traverseList(testF) + " delete 3", traverseList(expectationF), traverseList(resultF), array_equals(traverseList(expectationF), traverseList(resultF)));
var testG = init();
var expectationG =new LinkedList(1, new LinkedList(2, new LinkedList(3, null)));
var resultG = del(testG, 4)
declare_result(traverseList(testG) + " delete 4", traverseList(expectationG), traverseList(resultG), array_equals(traverseList(expectationG), traverseList(resultG)));
var testH = init();
var expectationH = new LinkedList(1, new LinkedList(5, new LinkedList(2, new LinkedList(3, new LinkedList(4, null)))));
var resultH = insrt(init(), 5, 2)
declare_result(traverseList(testH) + " insert 5 at 2", traverseList(expectationH), traverseList(resultH), array_equals(traverseList(expectationH), traverseList(resultH)));
};