javascript LinkedList:
function Node(elem, prev, next) {
this.elem = elem;
this.prev = prev ? prev : null;
this.next = next ? prev : null;
}
function LinkedList() {
this.length = 0;
this.head = null;
var that = this;
if (arguments.length > 0) {
var a = arguments[0];
if (a instanceof Array) {
a.forEach(function(elem) {
that.push(elem);
});
}
}
}
LinkedList.prototype.push = function(elem) {
var newNode = new Node(elem);
if (this.length === 0) {
this.head = newNode;
this.head.prev = newNode;
this.head.next = newNode;
} else {
newNode.next = this.head;
newNode.prev = this.head.prev;
this.head.prev.next = newNode; // !!! CAUTION !!!
this.head.prev = newNode;
}
++this.length;
return this.length;
};
// alias for push
LinkedList.prototype.append = function(elem) {
return this.push(elem);
};
LinkedList.prototype.unshift = function(elem) {
var newNode = new Node(elem);
if (this.length === 0) {
this.head = newNode;
this.head.prev = newNode;
this.head.next = newNode;
} else {
newNode.next = this.head;
newNode.prev = this.head.prev;
this.head.prev.next = newNode; // !!! CAUTION !!!
this.head.prev = newNode;
}
this.head = newNode;
++this.length;
return this.length;
};
LinkedList.prototype.shift = function() {
if (this.length === 0) {
return null;
}
var head = this.head,
node = new Node(head.elem);
head.next.prev = head.prev;
head.prev.next = head.next;
delete(head);
this.head = head.next;
--this.length;
return node.elem;
};
LinkedList.prototype.pop = function() {
if (this.length === 0) {
return null;
}
var tail = this.head.prev,
node = new Node(tail.elem);
tail.prev.next = tail.next;
tail.next.prev = tail.prev;
delete(tail);
--this.length;
return node.elem;
};
LinkedList.prototype._get = function(index) {
if (index < 0 || index >= this.length) {
throw new DOMException("LinkedList index out of bounds!");
}
if (index===0) {
return this.head;
}
var pivot = Math.round(this.length / 2);
var p = null, i;
if (index <= pivot) {
p = this.head; // head => tail
for (i = 0; i < index; i++) {
p = p.next;
}
} else {
p = this.head.prev; // tail => head
for (i = this.length - 1; i > index; i--) {
p = p.prev;
}
}
return p;
};
LinkedList.prototype._delete = function(node) {
var retNode = new Node(node.elem);
node.prev.next = node.next;
node.next.prev = node.prev;
var p = node.next;
if (node===this.head) {
this.head = p;
}
node = null;
this.length--;
return {
p: 0 <this.length ? p : null,
v: retNode.elem
}
};
LinkedList.prototype._insertBefore = function(node, elem) {
var newNode = new Node(elem);
newNode.next = node;
newNode.prev = node.prev;
node.prev.next = newNode;
node.prev = newNode;
++this.length;
return newNode;
};
LinkedList.prototype.get = function(index) {
var p = this._get(index);
return p.elem;
};
LinkedList.prototype.splice = function(start,deleteCount,items) {
var p = this._get(start), o, list = new LinkedList();
while (deleteCount--) {
o = this._delete(p);
p = o.p;
list.push(o.v);
if (null===p) {break;}
}
var that = this;
if (typeof items !== "undefined") {
var i = 0;
if (items instanceof Array) {
for (i = 0; i < items.length; i++) {
p = that._insertBefore(p, items[i]);
}
} else if (items instanceof LinkedList) {
for (i = 0; i < items.length; i++) {
p = that._insertBefore(p, items.get(i));
}
} else {
that._insertBefore(p, items);
}
}
return list;
};
LinkedList.prototype.forEach = function(callback) {
var p = this.head,
index = 0;
do {
callback(p.elem, index);
p = p.next;
index++;
} while (p != this.head);
return this;
};
LinkedList.prototype.map = function(callback) {
var newList = new this.__proto__.constructor();
this.forEach(function(elem) {
newList.push(callback(elem));
});
return newList;
};
LinkedList.prototype.reduce = function(callback, initValue) {
if (this === null) {
throw new TypeError('LinkedList.prototype.reduce ' +
'called on null or undefined');
}
if (typeof callback !== 'function') {
throw new TypeError(callback + ' is not a function');
}
var acc = initValue,
p = this.head;
do {
acc = callback(acc, p.elem);
p = p.next;
} while (p != this.head);
return acc;
};
LinkedList.prototype.join = function(sep) {
var s = "";
if (this.length === 0) {
return s;
}
if (this.length === 1) {
return this.head.elem;
}
var p = this.head;
do {
s += p.elem.toString() + sep;
p = p.next;
} while (p != this.head.prev);
s += p.elem.toString();
return s;
};
LinkedList.prototype.toString = function() {
return '[' + this.join(',') + ']';
};
LinkedList.prototype.insertBeforeIndex = function(index, elem) {
if (index === 0) {
this.unshift(elem);
return this.length;
}
if (index >this.length) {
throw new DOMException('index out of bounds');
}
if (index === this.length) {
this.append(elem);
return this.length;
}
var node = new Node(elem);
if (index === this.length-1) {
var tail = this.head.prev;
node.next = tail;
node.prev = tail.prev;
tail.prev.next = node;
tail.prev = node;
} else {
var p = this._get(index);
node.next = p;
node.prev = p.prev;
p.prev.next = node;
p.next.prev = node;
}
++this.length;
return this.length;
};
// Array like
1 // test 2 var list = new LinkedList(); 3 4 for (var i = 1; i < 10; i++) { 5 list.push(i); 6 } 7 for (i = 0; i < list.length; i++) { 8 console.log(list.get(i)); // 1,2,3,4,5,6,7,8,9 9 } 10 11 // list.forEach(function(elem) {console.log(elem);}); 12 var newList = list.map(function(elem) { 13 return elem - 1; 14 }); 15 console.log(newList.toString()); // 0,1,2,3,4,5,6,7,8 16 newList.shift(); 17 console.log(newList.toString()); // 1,2,3,4,5,6,7,8 18 19 var oList = new LinkedList(); 20 oList.push({ x: 2 }); 21 oList.push({ x: 2 }); 22 oList.push({ x: 3 }); 23 24 var mul = oList.reduce(function(a, c) { 25 return a * c.x; 26 }, 1); 27 console.log(mul); // 12
// test 2
var a = [3, 12, 17, 16, 73, 32, 61, 46, 52, 49, 6, 5]; var list = new LinkedList(a); console.log(list.toString()); console.log('array: ' + a.length + ' list: ' + list.length); list.insertBeforeIndex(0, 99); console.log(list.toString()); list.insertBeforeIndex(3, 99); console.log(list.toString()); list.insertBeforeIndex(list.length, 100); console.log(list.toString()); list.insertBeforeIndex(list.length-1, 98); console.log(list.toString()); console.log(list.length);
// test splice
function getTopN(a, n) {
function _getMaxElem(a) {
if (a.length === 0)
throw "empty array";
if (a.length === 1)
return { index: 0, value: a[0] };
var max = a.get(0), index = 0, c;
for (var i = 0; i < a.length; i++) {
c = a.get(i);
if (c > max) {
max = c;
index = i;
}
}
return {
index: index,
value: max
}
}
var o = {}, b = [];
while (n--) {
o = _getMaxElem(a);
b.push(o.value);
a.splice(o.index, 1);
}
return b;
}
/**
* 5 largest elements: [73,61,52,49,46]
* -------------sorted------------------
* [ 73, 61, 52, 49, 46, 32, 17, 16, 12, 6, 5, 3 ]
*/
var a = [3, 12, 17, 16, 73, 32, 61, 46, 52, 49, 6, 5];
var list = new LinkedList(a);
var top5 = getTopN(list, 5);
console.log('5 largest elements: [' + top5.toString() + ']');
console.log('-------------sorted------------------');
console.log(a.sort(function(a, b) { return b - a; }));