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
|
