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

2.List [10, 11, 12, 13]
2.begin.distance(2.end): 4

1.begin.step.splice(2.begin, 2.end)
1.List [4, 10, 11, 12, 13, 3, 2, 1, 0]
1.begin.distance(1.end): 9
1.front: 4
1.back: 0

2.List []
2.begin.distance(2.end): 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/yp9Xwr
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!