A JavaScript prototypal class that implements both a sorted list and a stack using linked lists

LinkedSortedIntStack.js

// Usage:
// var a = new LinkedSortedIntStack(1, 2, 5);
// a.push(4, 3);
// a.getStackAsArray();
// a.getSortedListAsArray();

var LinkedSortedIntStack = function() {
  this.nodeCount = 0;

  // Push all arguments (varargs-style)
  if (arguments) { this.push.apply(this, arguments); }
};

LinkedSortedIntStack.prototype.push = function() {
  for (var i = 0; i < arguments.length; i++) {
    var newNode = {val: arguments[i], prevStackNode: this.lastStackNode};

    if (this.nodeCount === 0) {
      // Stack was empty...
      this.firstStackNode = newNode;
      this.lastStackNode = newNode;
      this.lowestSortedNode = newNode;
    } else {
      // Stack was not empty...

      // Append to LIFO stack
      this.lastStackNode.nextStackNode = newNode;
      this.lastStackNode = newNode;

      // Find insertion index in sorted list
      if (this.lowestSortedNode.val > newNode.val) {
        // Insert new node at beginning of sorted list
        newNode.nextSortedNode = this.lowestSortedNode;
        this.lowestSortedNode.prevSortedNode = newNode;
        this.lowestSortedNode = newNode;
      } else {
        // Find insertion index in sorted list
        var prevNode = this.lowestSortedNode;
        while (prevNode.nextSortedNode && prevNode.nextSortedNode.val < newNode.val) {
          prevNode = prevNode.nextSortedNode;
        }
        // Insert after prevNode in sorted list
        newNode.prevSortedNode = prevNode;
        newNode.nextSortedNode = prevNode.nextSortedNode;
        prevNode.nextSortedNode = newNode;
        if (newNode.nextSortedNode) { newNode.nextSortedNode.prevSortedNode = newNode; }
      }
    }

    this.nodeCount++;
  }

  // Like native JavaScript array.push, return resultant length
  return this.nodeCount;
};

LinkedSortedIntStack.prototype.pop = function() {
  if (this.nodeCount === 0) { return; }
  var popNode = this.lastStackNode;
  this.nodeCount--;

  if (this.nodeCount === 0) {
    // Stack is now empty...
    this.firstStackNode = null;
    this.lastStackNode = null;
    this.lowestSortedNode = null;
  } else {
    // Stack still has nodes...

    // Remove from LIFO stack
    this.lastStackNode = popNode.prevStackNode;
    this.lastStackNode.nextStackNode = null;

    // Remove from sorted list
    if (popNode.prevSortedNode) {
      // popNode was not lowest
      popNode.prevSortedNode.nextSortedNode = popNode.nextSortedNode;
      if (popNode.nextSortedNode) { popNode.nextSortedNode.prevSortedNode = popNode.prevSortedNode; }
    } else {
      // popNode was lowest
      this.lowestSortedNode = popNode.nextSortedNode;
      this.lowestSortedNode.prevSortedNode = null;
    }
  }

  // Return the associated value
  return popNode.val;
};

LinkedSortedIntStack.prototype.getStackAsArray = function() {
  var a = [];
  var n = this.firstStackNode;
  while (n) {
    a.push(n.val);
    n = n.nextStackNode;
  }
  return a;
};

LinkedSortedIntStack.prototype.getSortedListAsArray = function() {
  var a = [];
  var n = this.lowestSortedNode;
  while (n) {
    a.push(n.val);
    n = n.nextSortedNode;
  }
  return a;
};

// export
if (window) window.LinkedSortedIntStack = LinkedSortedIntStack;