fork download
copy 
  1. // Doubly linked list. (3.01)
  2.  
  3. function _ListNode(value) {
  4.     this._next = this;
  5.     this._prev = this;
  6.     this.value = value;
  7. }
  8.  
  9. Object.defineProperty(_ListNode.prototype, 'next', {
  10.     get: function () {
  11.         return this._next;
  12.     }
  13. });
  14.  
  15. Object.defineProperty(_ListNode.prototype, 'prev', {
  16.     get: function () {
  17.         return this._prev;
  18.     }
  19. });
  20.  
  21. _ListNode.prototype.insert = function (value) {
  22.     let node = new _ListNode(value);
  23.     node._next = this;
  24.     node._prev = this._prev;
  25.     this._prev._next = node;
  26.     this._prev = node;
  27.     return this;
  28. };
  29.  
  30. _ListNode.prototype.remove = function (last = this._next) {
  31.     let next = last;
  32.     let prev = this._prev;
  33.     next._prev = prev;
  34.     prev._next = next;
  35.     return next;
  36. };
  37.  
  38. _ListNode.prototype.splice = function (first, last = first._next) {
  39.     if (first === last || last === this)
  40.         return;
  41.     last._prev._next = this;
  42.     first._prev._next = last;
  43.     this._prev._next = first;
  44.  
  45.     let temp = this._prev;
  46.     this._prev = last._prev;
  47.     last._prev = first._prev;
  48.     first._prev = temp;
  49.     return this;
  50. };
  51.  
  52. _ListNode.prototype.step = function (n = 1) {
  53.     let result = this;
  54.     for (let i = 0; i < n; i++) {
  55.         result = result._next;
  56.     }
  57.     for (let i = 0; i > n; i--) {
  58.         result = result._prev;
  59.     }
  60.     return result;
  61. };
  62.  
  63. _ListNode.prototype.distance = function (last) {
  64.     let result = 0;
  65.     for (let first = this; first !== last; first = first._next) {
  66.         result++;
  67.     }
  68.     return result;
  69. };
  70.  
  71. //
  72. // List.
  73. //
  74.  
  75. function List(iterable = []) {
  76.     this.head = new _ListNode();
  77.     for (const x of iterable) {
  78.         this.pushBack(x);
  79.     }
  80. }
  81.  
  82. Object.defineProperty(List.prototype, 'begin', {
  83.     get: function () {
  84.         return this.head.next;
  85.     }
  86. });
  87.  
  88. Object.defineProperty(List.prototype, 'end', {
  89.     get: function () {
  90.         return this.head;
  91.     }
  92. });
  93.  
  94. Object.defineProperty(List.prototype, 'empty', {
  95.     get: function () {
  96.         return this.begin === this.end;
  97.     }
  98. });
  99.  
  100. Object.defineProperty(List.prototype, 'front', {
  101.     get: function () {
  102.         if (this.empty)
  103.             throw new Error("Data access in empty list");
  104.         return this.begin.value;
  105.     }
  106. });
  107.  
  108. Object.defineProperty(List.prototype, 'back', {
  109.     get: function () {
  110.         if (this.empty)
  111.             throw new Error("Data access in empty list");
  112.         return this.end.prev.value;
  113.     }
  114. });
  115.  
  116. List.prototype.pushFront = function (value) {
  117.     this.begin.insert(value);
  118.     return this;
  119. };
  120.  
  121. List.prototype.pushBack = function (value) {
  122.     this.end.insert(value);
  123.     return this;
  124. };
  125.  
  126. List.prototype.popFront = function () {
  127.     if (this.empty)
  128.         throw new Error("Pop in empty list");
  129.     this.begin.remove();
  130.     return this;
  131. };
  132.  
  133. List.prototype.popBack = function () {
  134.     if (this.empty)
  135.         throw new Error("Pop in empty list");
  136.     this.end.prev.remove();
  137.     return this;
  138. };
  139.  
  140. List.prototype.clear = function () {
  141.     this.begin.remove(this.end);
  142.     return this;
  143. };
  144.  
  145. List.prototype[Symbol.iterator] = function* () {
  146.     const last = this.end;
  147.     for (let first = this.begin; first !== last; first = first.next) {
  148.         yield first.value;
  149.     }
  150. };
  151.  
  152. List.prototype.forEach = function (callbackFn, ...args) {
  153.     for (const x of this) {
  154.         callbackFn(x, ...args);
  155.     }
  156. };
  157.  
  158. List.prototype.map = function (callbackFn, ...args) {
  159.     let result = new List();
  160.     this.forEach(x => result.pushBack(callbackFn(x, ...args)));
  161.     return result;
  162. };
  163.  
  164. List.prototype.toString = function () {
  165.     return `List {${Array.from(this).join(", ")}}`;
  166. };
  167.  
  168. //
  169. // Main.
  170. //
  171.  
  172. let list1 = new List();
  173.  
  174. for (let i = 0; i < 5; i++) {
  175.     list1.pushBack(i);
  176.     console.log("1." + list1);
  177. }
  178.  
  179. console.log("1.size:", list1.begin.distance(list1.end));
  180. console.log("1.empty:", list1.empty);
  181. console.log();
  182.  
  183. while (!list1.empty) {
  184.     list1.popFront()
  185.     console.log("1." + list1);
  186. }
  187.  
  188. console.log("1.size:", list1.begin.distance(list1.end));
  189. console.log("1.empty:", list1.empty);
  190. console.log();
  191.  
  192. for (let i = 0; i < 5; i++) {
  193.     list1.pushFront(i);
  194. }
  195.  
  196. console.log("1." + list1);
  197. console.log("1.size:", list1.begin.distance(list1.end));
  198. console.log();
  199.  
  200. let list2 = new List([10, 11, 12, 13]);
  201.  
  202. console.log("2." + list2);
  203. console.log("2.size:", list2.begin.distance(list2.end));
  204. console.log();
  205.  
  206. console.log("1.begin.next.splice(2.begin, 2.end)");
  207. list1.begin.next.splice(list2.begin, list2.end);
  208. console.log("1." + list1);
  209. console.log("1.size:", list1.begin.distance(list1.end));
  210. console.log();
  211.  
  212. console.log("2." + list2);
  213. console.log("2.size:", list2.begin.distance(list2.end));
  214. console.log();
  215.  
  216. console.log("1.begin.next.remove(1.end.step(-4))");
  217. list1.begin.next.remove(list1.end.step(-4));
  218. console.log("1." + list1);
  219. console.log("1.size:", list1.begin.distance(list1.end));
  220. console.log("1.front:", list1.front);
  221. console.log("1.back:", list1.back);
  222. console.log();
  223.  
  224. try {
  225.     list2.front();
  226. } catch (error) {
  227.     console.log("2.front:", error.message);
  228. }
  229. try {
  230.     list2.back();
  231. } catch (error) {
  232.     console.log("2.back:", error.message);
  233. }
  234.  
  235. try {
  236.     list2.popFront();
  237. } catch (error) {
  238.     console.log("2.popFront:", error.message);
  239. }
  240. try {
  241.     list2.popBack();
  242. } catch (error) {
  243.     console.log("2.popBack:", error.message);
  244. }
Success #stdin #stdout 0.06s 41120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1.List {0}
1.List {0, 1}
1.List {0, 1, 2}
1.List {0, 1, 2, 3}
1.List {0, 1, 2, 3, 4}
1.size: 5
1.empty: false

1.List {1, 2, 3, 4}
1.List {2, 3, 4}
1.List {3, 4}
1.List {4}
1.List {}
1.size: 0
1.empty: true

1.List {4, 3, 2, 1, 0}
1.size: 5

2.List {10, 11, 12, 13}
2.size: 4

1.begin.next.splice(2.begin, 2.end)
1.List {4, 10, 11, 12, 13, 3, 2, 1, 0}
1.size: 9

2.List {}
2.size: 0

1.begin.next.remove(1.end.step(-4))
1.List {4, 3, 2, 1, 0}
1.size: 5
1.front: 4
1.back: 0

2.front: Data access in empty list
2.back: Data access in empty list
2.popFront: Pop in empty list
2.popBack: Pop in empty list
https://ideone.com/gahhzL
language:
Node.js (node 20.14)
created:
5 days 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!