node js связанный список
Написал связанный список для своих нужд (знаю есть готовые, но этж велосипед и опыт).
PHP код:
function LinkedList() { this.first = null; this.last = null; this.length = 0; }
module.exports = LinkedList;
LinkedList.prototype.addToStart = function (value) { var first = this.first; var newItem = { before: null, after: first, value: value };
if (first) { first.before = newItem; }
if (this.last == null) { this.last = newItem; }
this.first = newItem; this.length++;
return newItem; }; LinkedList.prototype.add = LinkedList.prototype.addToEnd = function (value) { var last = this.last; var newItem = { before: last, after: null, value: value };
if (last) { last.after = newItem; }
if (this.first == null) { this.first = newItem; }
this.last = newItem; this.length++;
return newItem; };
LinkedList.prototype.insertBefore = function (value, listItem) { if (!listItem) { throw new Error('listItem == null'); }
var newItem = { before: listItem.before, after: listItem, value: value };
if (newItem.before == null) { this.first = newItem; } else { newItem.before.after = newItem; }
listItem.before = newItem;
this.length++; return newItem; };
LinkedList.prototype.insertAfter = function (value, listItem) { if (!listItem) { throw new Error('listItem == null'); }
var newItem = { before: listItem, after: listItem.after, value: value };
if (newItem.after == null) { this.last = newItem; } else { newItem.after.before = newItem; }
listItem.after = newItem;
this.length++;
return newItem; };
LinkedList.prototype.remove = function (listItem) {
if (listItem.before) { listItem.before.after = listItem.after; } else { this.first = listItem.after; }
if (listItem.after) { listItem.after.before = listItem.before; } else { this.last = listItem.before; } this.length--; };
LinkedList.prototype.foreach = function (processItemCallback, onEndCallback) { var item = this.first;
function nextItemProcessor(item) { return function () { if (item) { processItemCallback(item, nextItemProcessor(item.after)); } else { if (onEndCallback) onEndCallback(); } }; }
if (item) { processItemCallback(item, nextItemProcessor(item.after)); } else { if (onEndCallback) onEndCallback(); } };
тесты:
PHP код:
var util = require('util'); var LinkedList = require('./LinkedList');
var list = new LinkedList();
list.add('one'); // добавление в конец list.add('two'); // добавление в конец var three = list.add("three"); // добавление в конец
var items = []; console.log(list.length); list.foreach(function (item, next) { items.push(item.value); next(); }, function () { console.log(util.inspect(items)); });
var five = list.insertAfter('five', three); // вставка после
list.insertBefore('four', five); // вставка до
list.insertAfter('six', five); // вставка после
items = []; console.log(list.length); list.foreach(function (item, next) { items.push(item.value); next(); }, function () { console.log(util.inspect(items)); });
items = [];
var two = three.before; list.remove(three); // удаление list.insertAfter(3, two); // вставка после list.remove(list.last); // удаление
console.log(list.length);
list.foreach(function (item, next) { items.push(item.value); next(); }, function () { console.log(util.inspect(items)); });
list.addToEnd(6); // добавление в конец списка items = [];
console.log(list.length);
list.foreach(function (item, next) { items.push(item.value); next(); }, function () { console.log(util.inspect(items)); });
list.remove(list.first); // удаление первого элемента list.remove(list.first); // удаление первого элемента list.addToStart(1); // добавление в начало list.insertAfter('два', list.first); // добавление после первого list.insertBefore('zero', list.first); // добавление перед первым items = [];
console.log(list.length);
list.foreach(function (item, next) { items.push(item.value); next(); }, function () { console.log(util.inspect(items)); });
результаты тестов:
Код:
C:\nodejs\node.exe LinkedList.js
3
[ 'one', 'two', 'three' ]
6
[ 'one', 'two', 'three', 'four', 'five', 'six' ]
5
[ 'one', 'two', 3, 'four', 'five' ]
6
[ 'one', 'two', 3, 'four', 'five', 6 ]
7
[ 'zero', 1, 'два', 3, 'four', 'five', 6 ]
Process finished with exit code 0
|