Listish

Basic list structures implemented using WeakMaps as the underlying data storage.

Lists are superior to arrays for data where items need to be removed, inserted, concatenated, or split. They are inferior to arrays for indexed lookup and require more memory per item. They are equivalent for iteration.

Common properties and functions

All of the below data structures share the following:

{ length:   'Number of items contained',
  toArray:  'Create a new array containing the items in the structure' }

SinglyLinkedList

{ current:  'Current item',
  head:     'First item in the list',
  tail:     'Last item in the list',
  prepend:  'Insert a new item at beginning of the list',
  append:   'Insert a new item at end of the list',
  shift:    'Remove item from beginning of the list and return it',
  insert:   'Insert item directly after the current item',
  remove:   'Remove the current item and return its value',
  next:     'Move to the next item and return its value',
  rewind:   'Move to the head of the list and return its value',
  concat:   'Append a list to the end of this list, points to the same underlying data' }

Stack

FILO (first in, last out) data structure.

/**
 *  push          pop
 *  \__\         /__/
 *     --> top --^   _
 *        |___|       |
 *        |___|     length
 *        |___|      _|
 */

{ top:      'Top value which will be removed by pop or pushed down by push',
  push:     'Add a new value top the top of the stack',
  pop:      'Remove a value from the top of the stack and return it',
  concat:   'Append a stack to the top of this stack, points to the same underlying data' }

Queue

FIFO (First in, first out) data structure.

/**
 * dequeue
 *  \___\    front
 *       ^--|____|____|____|
 *                          ^-- \___\
 *                             enqueue
 *          |-----length----|
 */

{ front:     'Front value of the list which will be removed and returned by dequeue',
  enqueue:   'Add an item to the end of the queue',
  dequeue:   'Remove an item from the front of the queue and return it',
  concat:    'Append another queue to end of this queue, points to the same underlying data' }