fork download
copy 
  1. // Doubly linked list prototype. (3.00)
  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 result = 0;
  49.     for (let first = this; first !== last; first = first.next) {
  50.         result++;
  51.     }
  52.     return result;
  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. Object.defineProperty(List.prototype, 'begin', {
  65.     get: function () {
  66.         return this.head.next;
  67.     }
  68. });
  69.  
  70. Object.defineProperty(List.prototype, 'end', {
  71.     get: function () {
  72.         return this.head;
  73.     }
  74. });
  75.  
  76. Object.defineProperty(List.prototype, 'empty', {
  77.     get: function () {
  78.         return this.begin === this.end;
  79.     }
  80. });
  81.  
  82. Object.defineProperty(List.prototype, 'front', {
  83.     get: function () {
  84.         if (this.empty)
  85.             throw new Error("Data access in empty list");
  86.         return this.begin.data;
  87.     }
  88. });
  89.  
  90. Object.defineProperty(List.prototype, 'back', {
  91.     get: function () {
  92.         if (this.empty)
  93.             throw new Error("Data access in empty list");
  94.         return this.end.prev.data;
  95.     }
  96. });
  97.  
  98. List.prototype.clear = function () {
  99.     this.head = new Node();
  100.     return this;
  101. };
  102.  
  103. List.prototype.pushFront = function (value) {
  104.     this.begin.insert(new Node(value));
  105.     return this;
  106. };
  107.  
  108. List.prototype.pushBack = function (value) {
  109.     this.end.insert(new Node(value));
  110.     return this;
  111. };
  112.  
  113. List.prototype.popFront = function () {
  114.     if (this.empty)
  115.         throw new Error("Pop in empty list");
  116.     this.begin.remove();
  117.     return this;
  118. };
  119.  
  120. List.prototype.popBack = function () {
  121.     if (this.empty)
  122.         throw new Error("Pop in empty list");
  123.     this.end.prev.remove();
  124.     return this;
  125. };
  126.  
  127. List.prototype[Symbol.iterator] = function* () {
  128.     const last = this.end;
  129.     for (let first = this.begin; first !== last; first = first.next) {
  130.         yield first.data;
  131.     }
  132. };
  133.  
  134. List.prototype.forEach = function (callbackFn, ...args) {
  135.     for (let x of this) {
  136.         callbackFn(x, ...args);
  137.     }
  138. };
  139.  
  140. List.prototype.map = function (callbackFn, ...args) {
  141.     let result = new List();
  142.     this.forEach(x => result.pushBack(callbackFn(x, ...args)));
  143.     return result;
  144. };
  145.  
  146. List.prototype.toString = function () {
  147.     return `List [${Array.from(this).join(", ")}]`;
  148. };
  149.  
  150. // Main.
  151.  
  152. let list1 = new List();
  153.  
  154. console.log("1." + list1);
  155. console.log("1.begin.distance(1.end):", list1.begin.distance(list1.end));
  156. console.log("1.empty:", list1.empty);
  157.  
  158. for (let i = 0; i < 5; i++) {
  159.     list1.pushFront(i);
  160. }
  161.  
  162. console.log("1." + list1);
  163. console.log("1.begin.distance(1.end):", list1.begin.distance(list1.end));
  164. console.log("1.empty:", list1.empty);
  165. console.log();
  166.  
  167. let list2 = new List([10, 11, 12, 13]);
  168.  
  169. console.log("2." + list2);
  170. console.log("2.begin.distance(2.end):", list2.begin.distance(list2.end));
  171. console.log();
  172.  
  173. console.log("1.begin.step().splice(2.begin, 2.end)");
  174. list1.begin.step().splice(list2.begin, list2.end);
  175. console.log("1." + list1);
  176. console.log("1.begin.distance(1.end):", list1.begin.distance(list1.end));
  177. console.log("1.front:", list1.front);
  178. console.log("1.back:", list1.back);
  179. console.log();
  180.  
  181. console.log("2." + list2);
  182. console.log("2.begin.distance(2.end):", list2.begin.distance(list2.end));
  183. try {
  184.     list2.front;
  185. } catch (error) {
  186.     console.log("2.front:", error.message);
  187. }
  188. try {
  189.     list2.back;
  190. } catch (error) {
  191.     console.log("2.back:", error.message);
  192. }
  193.  
  194. try {
  195.     list2.popFront();
  196. } catch (error) {
  197.     console.log("2.popFront:", error.message);
  198. }
  199. try {
  200.     list2.popBack();
  201. } catch (error) {
  202.     console.log("2.popBack:", error.message);
  203. }
Success #stdin #stdout 0.04s 40360KB
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/ap5plz
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!