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