fork(1) download
copy 
  1. // @file list.js
  2. // @ingroup utility
  3. // Doubly linked list.
  4. // @date 12/05/2025
  5.  
  6. function ListNode(value) {
  7.     this._next = this;
  8.     this._prev = this;
  9.     this.value = value;
  10. }
  11.  
  12. Object.defineProperty(ListNode.prototype, 'next', {
  13.     get: function () {
  14.         return this._next;
  15.     }
  16. });
  17.  
  18. Object.defineProperty(ListNode.prototype, 'prev', {
  19.     get: function () {
  20.         return this._prev;
  21.     }
  22. });
  23.  
  24. ListNode.prototype.insert = function (value) {
  25.     let node = new ListNode(value);
  26.     node._next = this;
  27.     node._prev = this._prev;
  28.     this._prev._next = node;
  29.     this._prev = node;
  30.     return this;
  31. };
  32.  
  33. ListNode.prototype.remove = function (last = this._next) {
  34.     let next = last;
  35.     let prev = this._prev;
  36.     next._prev = prev;
  37.     prev._next = next;
  38.     return next;
  39. };
  40.  
  41. ListNode.prototype.splice = function (first, last = first._next) {
  42.     if (first === last || last === this)
  43.         return;
  44.     last._prev._next = this;
  45.     first._prev._next = last;
  46.     this._prev._next = first;
  47.  
  48.     let temp = this._prev;
  49.     this._prev = last._prev;
  50.     last._prev = first._prev;
  51.     first._prev = temp;
  52.     return this;
  53. };
  54.  
  55. ListNode.prototype.step = function (n = 1) {
  56.     let result = this;
  57.     for (let i = 0; i < n; i++) {
  58.         result = result._next;
  59.     }
  60.     for (let i = 0; i > n; i--) {
  61.         result = result._prev;
  62.     }
  63.     return result;
  64. };
  65.  
  66. ListNode.prototype.distance = function (last) {
  67.     let result = 0;
  68.     for (let first = this; first !== last; first = first._next) {
  69.         result++;
  70.     }
  71.     return result;
  72. };
  73.  
  74. // List.
  75.  
  76. function List(iterable = []) {
  77.     this.head = new ListNode();
  78.     for (const x of iterable) {
  79.         this.pushBack(x);
  80.     }
  81. }
  82.  
  83. Object.defineProperty(List.prototype, 'begin', {
  84.     get: function () {
  85.         return this.head.next;
  86.     }
  87. });
  88.  
  89. Object.defineProperty(List.prototype, 'end', {
  90.     get: function () {
  91.         return this.head;
  92.     }
  93. });
  94.  
  95. Object.defineProperty(List.prototype, 'empty', {
  96.     get: function () {
  97.         return this.begin === this.end;
  98.     }
  99. });
  100.  
  101. Object.defineProperty(List.prototype, 'front', {
  102.     get: function () {
  103.         if (this.empty)
  104.             throw new Error("Data access in empty list");
  105.         return this.begin.value;
  106.     }
  107. });
  108.  
  109. Object.defineProperty(List.prototype, 'back', {
  110.     get: function () {
  111.         if (this.empty)
  112.             throw new Error("Data access in empty list");
  113.         return this.end.prev.value;
  114.     }
  115. });
  116.  
  117. List.prototype.pushFront = function (value) {
  118.     this.begin.insert(value);
  119.     return this;
  120. };
  121.  
  122. List.prototype.pushBack = function (value) {
  123.     this.end.insert(value);
  124.     return this;
  125. };
  126.  
  127. List.prototype.popFront = function () {
  128.     if (this.empty)
  129.         throw new Error("Pop in empty list");
  130.     this.begin.remove();
  131.     return this;
  132. };
  133.  
  134. List.prototype.popBack = function () {
  135.     if (this.empty)
  136.         throw new Error("Pop in empty list");
  137.     this.end.prev.remove();
  138.     return this;
  139. };
  140.  
  141. List.prototype.clear = function () {
  142.     this.begin.remove(this.end);
  143.     return this;
  144. };
  145.  
  146. List.prototype[Symbol.iterator] = function* () {
  147.     const last = this.end;
  148.     for (let first = this.begin; first !== last; first = first.next) {
  149.         yield first.value;
  150.     }
  151. };
  152.  
  153. List.prototype.map = function (callbackFn, ...args) {
  154.     let result = new List();
  155.     for (const x of this) {
  156.         result.pushBack(callbackFn(x, ...args));
  157.     }
  158.     return result;
  159. };
  160.  
  161. List.prototype.forEach = function (callbackFn, ...args) {
  162.     for (const x of this) {
  163.         callbackFn(x, ...args);
  164.     }
  165. };
  166.  
  167. List.prototype.reduce = function (callbackFn, initial, ...args) {
  168.     for (const x of this) {
  169.         initial = callbackFn(initial, x, ...args);
  170.     }
  171.     return initial;
  172. }
  173.  
  174. List.prototype.toString = function () {
  175.     return `List {${Array.from(this).join(", ")}}`;
  176. };
  177.  
  178. // Exports.
  179.  
  180. module.exports = {
  181.     List,
  182.     ListNode
  183. };
  184. // END
  185.  
  186.  
  187. // @file list_test.js
  188. // @ingroup testing
  189. // Test List module.
  190.  
  191. // const { List } = require("list");
  192. // const colorize = require("colorize");
  193. const colorize = (str, color) => str;
  194.  
  195. // Utility.
  196.  
  197. function report(condition, message) {
  198.     console.log(message.padEnd(30, ".")
  199.         + (condition
  200.             ? colorize("Pass", "green")
  201.             : colorize("Fail", "red")));
  202. }
  203.  
  204. function iota(n, start = 0, step = 1) {
  205.     return Array.from({length: n}, (_, i) => i*step + start);
  206. }
  207.  
  208. function listSize(list) {
  209.     return list.begin.distance(list.end);
  210. }
  211.  
  212. function arrayEquals(a1, a2) {
  213.     if (a1.length !== a2.length)
  214.         return false;
  215.     return a1.every((v, i) => v === a2[i]);
  216. }
  217.  
  218. function listEqualsArray(list, array) {
  219.     return arrayEquals(array, Array.from(list));
  220. }
  221.  
  222. // Test.
  223.  
  224. function testConstructor() {
  225.     console.log(colorize("constructor", "blue"));
  226.  
  227.     let keys = iota(10);
  228.     let list = new List();
  229.  
  230.     report(listSize(list) === 0, "size  (default)");
  231.     report(list.empty,           "empty (default)");
  232.  
  233.     list = new List(keys);
  234.     report(listSize(list) === keys.length, "size  (iterable)");
  235.     report(!list.empty,                    "empty (iterable)");
  236.  
  237.     report(listEqualsArray(list, keys), "order");
  238. }
  239.  
  240. function testPushFront() {
  241.     console.log(colorize("pushFront", "blue"));
  242.  
  243.     let keys = iota(10);
  244.     let list = new List();
  245.  
  246.     keys.forEach(v => list.pushFront(v));
  247.  
  248.     report(listSize(list) === keys.length, "size");
  249.     report(!list.empty, "empty");
  250.  
  251.     report(listEqualsArray(list, keys.reverse()), "order");
  252. }
  253.  
  254. function testPushBack() {
  255.     console.log(colorize("pushBack", "blue"));
  256.  
  257.     let keys = iota(10);
  258.     let list = new List();
  259.  
  260.     keys.forEach(v => list.pushBack(v));
  261.  
  262.     report(listSize(list) === keys.length, "size");
  263.     report(!list.empty, "empty");
  264.  
  265.     report(listEqualsArray(list, keys), "order");
  266. }
  267.  
  268. function testPopFront() {
  269.     console.log(colorize("popFront", "blue"));
  270.  
  271.     let keys = iota(10);
  272.     let list = new List(keys);
  273.  
  274.     for (let i = 0; i < 5; i++) {
  275.         list.popFront();
  276.     }
  277.  
  278.     report(listSize(list) === 5, "size  (midpoint)");
  279.     report(!list.empty,          "empty (midpoint)");
  280.  
  281.     report(listEqualsArray(list, keys.slice(5)), "order");
  282.  
  283.     for (let i = 0; i < 5; i++) {
  284.         list.popFront();
  285.     }
  286.  
  287.     report(listSize(list) === 0, "size");
  288.     report(list.empty, "empty");
  289.  
  290.     let except = false;
  291.  
  292.     try {
  293.         list.popFront();
  294.     } catch (_) {
  295.         except = true;
  296.     }
  297.  
  298.     report(except, "exception");
  299. }
  300.  
  301. function testPopBack() {
  302.     console.log(colorize("popBack", "blue"));
  303.  
  304.     let keys = iota(10);
  305.     let list = new List(keys);
  306.  
  307.     for (let i = 0; i < 5; i++) {
  308.         list.popBack();
  309.     }
  310.  
  311.     report(listSize(list) === 5, "size  (midpoint)");
  312.     report(!list.empty,          "empty (midpoint)");
  313.  
  314.     report(listEqualsArray(list, keys.slice(0, 5)), "order");
  315.  
  316.     for (let i = 0; i < 5; i++) {
  317.         list.popBack();
  318.     }
  319.  
  320.     report(listSize(list) === 0, "size");
  321.     report(list.empty, "empty");
  322.  
  323.     let except = false;
  324.  
  325.     try {
  326.         list.popBack();
  327.     } catch (_) {
  328.         except = true;
  329.     }
  330.  
  331.     report(except, "exception");
  332. }
  333.  
  334. function testFront() {
  335.     console.log(colorize("front", "blue"));
  336.  
  337.     let keys = iota(3, 1);
  338.     let list = new List(keys);
  339.  
  340.     for (let i of keys) {
  341.         report(list.front == i, `value (${i})`);
  342.         list.popFront();
  343.     }
  344.  
  345.     let except = false;
  346.  
  347.     try {
  348.         list.front;
  349.     } catch (_) {
  350.         except = true;
  351.     }
  352.  
  353.     report(except, "exception");
  354. }
  355.  
  356. function testBack() {
  357.     console.log(colorize("back", "blue"));
  358.  
  359.     let keys = iota(3, 1);
  360.     let list = new List(keys);
  361.  
  362.     for (let i of keys.reverse()) {
  363.         report(list.back == i, `value (${i})`);
  364.         list.popBack();
  365.     }
  366.  
  367.     let except = false;
  368.  
  369.     try {
  370.         list.back;
  371.     } catch (_) {
  372.         except = true;
  373.     }
  374.  
  375.     report(except, "exception");
  376. }
  377.  
  378. function testForEach() {
  379.     console.log(colorize("forEach", "blue"));
  380.  
  381.     let keys = iota(10);
  382.     let list = new List(keys);
  383.     let temp = [];
  384.  
  385.     list.forEach((x, a) => a.push(x), temp);
  386.  
  387.     report(temp.length === keys.length, "size");
  388.     report(arrayEquals(temp, keys), "order");
  389. }
  390.  
  391. function testMap() {
  392.     console.log(colorize("map", "blue"));
  393.  
  394.     let keys = iota(10);
  395.     let list = new List(keys);
  396.     let temp = list.map(x => x, list);
  397.  
  398.     report(listSize(temp) === keys.length, "size");
  399.     report(listEqualsArray(temp, keys), "order");
  400. }
  401.  
  402. function testReduce() {
  403.     console.log(colorize("reduce", "blue"));
  404.  
  405.     let keys = iota(10);
  406.     let list = new List(keys);
  407.  
  408.     let result1 = keys.reduce((a, x) => a + x, 0);
  409.     let result2 = list.reduce((a, x) => a + x, 0);
  410.  
  411.     report(result1 == result2, "value");
  412. }
  413.  
  414. function testInsert() {
  415.     console.log(colorize("insert", "blue"));
  416.  
  417.     let keys = iota(2, 1, 3);
  418.     let list = new List(keys);
  419.  
  420.     keys.splice(1, 0, 2);
  421.     list.begin.next.insert(2);
  422.  
  423.     report(listSize(list) === keys.length, "size  [1]");
  424.     report(listEqualsArray(list, keys),    "order [1]");
  425.  
  426.     keys.splice(keys.length-1, 0, 3);
  427.     list.end.prev.insert(3);
  428.  
  429.     report(listSize(list) === keys.length, "size  [n-1]");
  430.     report(listEqualsArray(list, keys),    "order [n-1]");
  431. }
  432.  
  433. function testRemove() {
  434.     console.log(colorize("remove", "blue"));
  435.  
  436.     let keys = iota(6, 1);
  437.     let list = new List(keys);
  438.  
  439.     keys.splice(1, 1);
  440.     list.begin.next.remove();
  441.  
  442.     report(listSize(list) === keys.length, "size  [1]");
  443.     report(listEqualsArray(list, keys),    "order [1]");
  444.  
  445.     keys.splice(keys.length-1, 1);
  446.     list.end.prev.remove();
  447.  
  448.     report(listSize(list) === keys.length, "size  [n-1]");
  449.     report(listEqualsArray(list, keys),    "order [n-1]");
  450.  
  451.     keys.splice(1, keys.length-2);
  452.     list.begin.next.remove(list.end.prev);
  453.  
  454.     report(listSize(list) === keys.length, "size  [1, n-1]");
  455.     report(listEqualsArray(list, keys),    "order [1, n-1]");
  456. }
  457.  
  458. function testSplice() {
  459.     console.log(colorize("splice", "blue"));
  460.  
  461.     let keys1 = iota(10);
  462.     let keys2 = iota(2, 11, 11);
  463.     let list1 = new List(keys1);
  464.     let list2 = new List(keys2);
  465.     let temp;
  466.  
  467.     temp = keys1.slice();
  468.     temp.splice(0, 0, ...keys2);
  469.     list1.begin.splice(list2.begin, list2.end);
  470.  
  471.     report(listSize(list1) === temp.length, "size  [0] (dst)");
  472.     report(listSize(list2) === 0,           "size  [0] (src)");
  473.     report(listEqualsArray(list1, temp),    "order [0]");
  474.  
  475.     list1 = new List(keys1);
  476.     list2 = new List(keys2);
  477.  
  478.     temp = keys1.slice();
  479.     temp.splice(temp.length, 0, ...keys2);
  480.     list1.end.splice(list2.begin, list2.end);
  481.  
  482.     report(listSize(list1) === temp.length, "size  [n] (dst)");
  483.     report(listSize(list2) === 0,           "size  [n] (src)");
  484.     report(listEqualsArray(list1, temp),    "order [n]");
  485.  
  486.     list1 = new List(keys1);
  487.     list2 = new List(keys2);
  488.  
  489.     temp = keys1.slice();
  490.     temp.splice(5, 0, ...keys2);
  491.     list1.begin.step(5).splice(list2.begin, list2.end);
  492.  
  493.     report(listSize(list1) === temp.length, "size  [5] (dst)");
  494.     report(listSize(list2) === 0,           "size  [5] (src)");
  495.     report(listEqualsArray(list1, temp),    "order [5]");
  496. }
  497.  
  498. // Entry.
  499.  
  500. testConstructor();
  501. testPushFront();
  502. testPushBack();
  503. testPopFront();
  504. testPopBack();
  505. testFront();
  506. testBack();
  507. testForEach();
  508. testMap();
  509. testReduce();
  510. testInsert();
  511. testRemove();
  512. testSplice();
Success #stdin #stdout 0.05s 42976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
constructor
size  (default)...............Pass
empty (default)...............Pass
size  (iterable)..............Pass
empty (iterable)..............Pass
order.........................Pass
pushFront
size..........................Pass
empty.........................Pass
order.........................Pass
pushBack
size..........................Pass
empty.........................Pass
order.........................Pass
popFront
size  (midpoint)..............Pass
empty (midpoint)..............Pass
order.........................Pass
size..........................Pass
empty.........................Pass
exception.....................Pass
popBack
size  (midpoint)..............Pass
empty (midpoint)..............Pass
order.........................Pass
size..........................Pass
empty.........................Pass
exception.....................Pass
front
value (1).....................Pass
value (2).....................Pass
value (3).....................Pass
exception.....................Pass
back
value (3).....................Pass
value (2).....................Pass
value (1).....................Pass
exception.....................Pass
forEach
size..........................Pass
order.........................Pass
map
size..........................Pass
order.........................Pass
reduce
value.........................Pass
insert
size  [1].....................Pass
order [1].....................Pass
size  [n-1]...................Pass
order [n-1]...................Pass
remove
size  [1].....................Pass
order [1].....................Pass
size  [n-1]...................Pass
order [n-1]...................Pass
size  [1, n-1]................Pass
order [1, n-1]................Pass
splice
size  [0] (dst)...............Pass
size  [0] (src)...............Pass
order [0].....................Pass
size  [n] (dst)...............Pass
size  [n] (src)...............Pass
order [n].....................Pass
size  [5] (dst)...............Pass
size  [5] (src)...............Pass
order [5].....................Pass
https://ideone.com/br1GAj
language:
Node.js (node 20.14)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!