File Explorer

1/**2 * Mnemonist Linked List3 * ======================4 *5 * Singly linked list implementation. Uses raw JavaScript objects as nodes6 * as benchmarks proved it was the fastest thing to do.7 */8var Iterator = require('obliterator/iterator'),9    forEach = require('obliterator/foreach');10 11/**12 * Linked List.13 *14 * @constructor15 */16function LinkedList() {17  this.clear();18}19 20/**21 * Method used to clear the list.22 *23 * @return {undefined}24 */25LinkedList.prototype.clear = function() {26 27  // Properties28  this.head = null;29  this.tail = null;30  this.size = 0;31};32 33/**34 * Method used to get the first item of the list.35 *36 * @return {any}37 */38LinkedList.prototype.first = function() {39  return this.head ? this.head.item : undefined;40};41LinkedList.prototype.peek = LinkedList.prototype.first;42 43/**44 * Method used to get the last item of the list.45 *46 * @return {any}47 */48LinkedList.prototype.last = function() {49  return this.tail ? this.tail.item : undefined;50};51 52/**53 * Method used to add an item at the end of the list.54 *55 * @param  {any}    item - The item to add.56 * @return {number}57 */58LinkedList.prototype.push = function(item) {59  var node = {item: item, next: null};60 61  if (!this.head) {62    this.head = node;63    this.tail = node;64  }65  else {66    this.tail.next = node;67    this.tail = node;68  }69 70  this.size++;71 72  return this.size;73};74 75/**76 * Method used to add an item at the beginning of the list.77 *78 * @param  {any}    item - The item to add.79 * @return {number}80 */81LinkedList.prototype.unshift = function(item) {82  var node = {item: item, next: null};83 84  if (!this.head) {85    this.head = node;86    this.tail = node;87  }88  else {89    if (!this.head.next)90      this.tail = this.head;91    node.next = this.head;92    this.head = node;93  }94 95  this.size++;96 97  return this.size;98};99 100/**101 * Method used to retrieve & remove the first item of the list.102 *103 * @return {any}104 */105LinkedList.prototype.shift = function() {106  if (!this.size)107    return undefined;108 109  var node = this.head;110 111  this.head = node.next;112  this.size--;113 114  return node.item;115};116 117/**118 * Method used to iterate over the list.119 *120 * @param  {function}  callback - Function to call for each item.121 * @param  {object}    scope    - Optional scope.122 * @return {undefined}123 */124LinkedList.prototype.forEach = function(callback, scope) {125  if (!this.size)126    return;127 128  scope = arguments.length > 1 ? scope : this;129 130  var n = this.head,131      i = 0;132 133  while (n) {134    callback.call(scope, n.item, i, this);135    n = n.next;136    i++;137  }138};139 140/**141 * Method used to convert the list into an array.142 *143 * @return {array}144 */145LinkedList.prototype.toArray = function() {146  if (!this.size)147    return [];148 149  var array = new Array(this.size);150 151  for (var i = 0, l = this.size, n = this.head; i < l; i++) {152    array[i] = n.item;153    n = n.next;154  }155 156  return array;157};158 159/**160 * Method used to create an iterator over a list's values.161 *162 * @return {Iterator}163 */164LinkedList.prototype.values = function() {165  var n = this.head;166 167  return new Iterator(function() {168    if (!n)169      return {170        done: true171      };172 173    var value = n.item;174    n = n.next;175 176    return {177      value: value,178      done: false179    };180  });181};182 183/**184 * Method used to create an iterator over a list's entries.185 *186 * @return {Iterator}187 */188LinkedList.prototype.entries = function() {189  var n = this.head,190      i = 0;191 192  return new Iterator(function() {193    if (!n)194      return {195        done: true196      };197 198    var value = n.item;199    n = n.next;200    i++;201 202    return {203      value: [i - 1, value],204      done: false205    };206  });207};208 209/**210 * Attaching the #.values method to Symbol.iterator if possible.211 */212if (typeof Symbol !== 'undefined')213  LinkedList.prototype[Symbol.iterator] = LinkedList.prototype.values;214 215/**216 * Convenience known methods.217 */218LinkedList.prototype.toString = function() {219  return this.toArray().join(',');220};221 222LinkedList.prototype.toJSON = function() {223  return this.toArray();224};225 226LinkedList.prototype.inspect = function() {227  var array = this.toArray();228 229  // Trick so that node displays the name of the constructor230  Object.defineProperty(array, 'constructor', {231    value: LinkedList,232    enumerable: false233  });234 235  return array;236};237 238if (typeof Symbol !== 'undefined')239  LinkedList.prototype[Symbol.for('nodejs.util.inspect.custom')] = LinkedList.prototype.inspect;240 241/**242 * Static @.from function taking an arbitrary iterable & converting it into243 * a list.244 *245 * @param  {Iterable} iterable   - Target iterable.246 * @return {LinkedList}247 */248LinkedList.from = function(iterable) {249  var list = new LinkedList();250 251  forEach(iterable, function(value) {252    list.push(value);253  });254 255  return list;256};257 258/**259 * Exporting.260 */261module.exports = LinkedList;262