fork(2) download 
  1. // Doubly linked list prototype. (1.01)
  2.  
  3. function Node(data) {
  4.     this.next = this;
  5.     this.prev = this;
  6.     this.data = data;
  7. }
  8.  
  9. Node.prototype.step = function (n = 1) {
  10.     let result = this;
  11.     for (let i = 0; i < n; i++) {
  12.         result = result.next;
  13.     }
  14.     for (let i = 0; i > n; i--) {
  15.         result = result.prev;
  16.     }
  17.     return result;
  18. };
  19.  
  20. function nodeRemove(at) {
  21.     let next = at.next;
  22.     let prev = at.prev;
  23.     next.prev = prev;
  24.     prev.next = next;
  25. }
  26.  
  27. function nodeInsertBefore(at, node) {
  28.     node.next = at;
  29.     node.prev = at.prev;
  30.     at.prev.next = node;
  31.     at.prev = node;
  32. }
  33.  
  34. function nodeTransferBefore(at, first, last) {
  35.     if (first === last || last === at)
  36.         return;
  37.     at.prev.next = first;
  38.     last.prev.next = at;
  39.     first.prev.next = last;
  40.  
  41.     let temp = at.prev;
  42.     at.prev = last.prev;
  43.     last.prev = first.prev;
  44.     first.prev = temp;
  45. }
  46.  
  47. // List.
  48.  
  49. function List(arrayLike = []) {
  50.     this.clear();
  51.     for (let x of arrayLike) {
  52.         this.pushBack(x);
  53.     }
  54. }
  55.  
  56. List.prototype.clear = function () {
  57.     this.head = new Node();
  58.     return this;
  59. };
  60.  
  61. List.prototype.begin = function () {
  62.     return this.head.next;
  63. };
  64.  
  65. List.prototype.end = function () {
  66.     return this.head;
  67. };
  68.  
  69. List.prototype.empty = function () {
  70.     return this.begin() === this.end();
  71. };
  72.  
  73. List.prototype.front = function () {
  74.     if (this.empty())
  75.         throw new Error("Data access in empty list");
  76.     return this.begin().data;
  77. };
  78.  
  79. List.prototype.back = function () {
  80.     if (this.empty())
  81.         throw new Error("Data access in empty list");
  82.     return this.end().prev.data;
  83. };
  84.  
  85. List.prototype.pushFront = function (value) {
  86.     nodeInsertBefore(this.begin(), new Node(value));
  87.     return this;
  88. };
  89.  
  90. List.prototype.pushBack = function (value) {
  91.     nodeInsertBefore(this.end(), new Node(value));
  92.     return this;
  93. };
  94.  
  95. List.prototype.popFront = function () {
  96.     if (this.empty())
  97.         throw new Error("Pop in empty list");
  98.     nodeRemove(this.begin());
  99.     return this;
  100. };
  101.  
  102. List.prototype.popBack = function () {
  103.     if (this.empty())
  104.         throw new Error("Pop in empty list");
  105.     nodeRemove(this.end().prev);
  106.     return this;
  107. };
  108.  
  109. List.prototype.splice = function (at, first, last) {
  110.     nodeTransferBefore(at, first, last);
  111.     return this;
  112. };
  113.  
  114. List.prototype[Symbol.iterator] = function* () {
  115.     let first = this.begin(), last = this.end();
  116.     for (; first !== last; first = first.next) {
  117.         yield first.data;
  118.     }
  119. };
  120.  
  121. List.prototype.forEach = function (callbackFn, ...args) {
  122.     for (let x of this) {
  123.         callbackFn(x, ...args);
  124.     }
  125. };
  126.  
  127. List.prototype.map = function (callbackFn, ...args) {
  128.     let result = new List();
  129.     this.forEach(x => result.pushBack(callbackFn(x, ...args)));
  130.     return result;
  131. };
  132.  
  133. List.prototype.size = function () {
  134.     let count = 0;
  135.     this.forEach(_ => ++count);
  136.     return count;
  137. };
  138.  
  139. List.prototype.toString = function () {
  140.     return `List {${Array.from(this).join(", ")}}`;
  141. };
  142.  
  143. // Main.
  144.  
  145. let list1 = new List();
  146.  
  147. console.log("1." + list1);
  148. console.log("1.size:", list1.size());
  149. console.log("1.empty:", list1.empty());
  150.  
  151. for (let i = 0; i < 5; i++) {
  152.     list1.pushFront(i);
  153. }
  154.  
  155. console.log("1." + list1);
  156. console.log("1.size:", list1.size());
  157. console.log("1.empty:", list1.empty());
  158. console.log();
  159.  
  160. let list2 = new List([10, 11, 12, 13]);
  161.  
  162. console.log("2." + list2);
  163. console.log("2.size:", list2.size());
  164. console.log();
  165.  
  166. console.log("1.splice(1.begin.step, 2.begin, 2.end)");
  167. list1.splice(list1.begin().step(), list2.begin(), list2.end());
  168. console.log("1." + list1);
  169. console.log("1.size:", list1.size());
  170. console.log("1.front:", list1.front());
  171. console.log("1.back:", list1.back());
  172. console.log();
  173.  
  174. console.log("2." + list2);
  175. console.log("2.size:", list2.size());
  176. try {
  177.     list2.front();
  178. } catch (error) {
  179.     console.log("2.front:", error.message);
  180. }
  181. try {
  182.     list2.back();
  183. } catch (error) {
  184.     console.log("2.back:", error.message);
  185. }
  186.  
  187. try {
  188.     list2.popFront();
  189. } catch (error) {
  190.     console.log("2.popFront:", error.message);
  191. }
  192. try {
  193.     list2.popBack();
  194. } catch (error) {
  195.     console.log("2.popBack:", error.message);
  196. }
Success #stdin #stdout 0.04s 40312KB
comments (?)
stdin 
Standard input is empty
stdout 
1.List {}
1.size: 0
1.empty: true
1.List {4, 3, 2, 1, 0}
1.size: 5
1.empty: false

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

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

2.List {}
2.size: 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/GvEZ7d
language:
Node.js (node 20.14)
created:
2 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!