function LinkedList() {}
LinkedList.prototype = {
  length: 0,
  first: null,
  last: null
};

LinkedList.Node = function(data) {
  this.prev = null; this.next = null;
  this.data = data;
};

LinkedList.Circular = function() {};
LinkedList.Circular.prototype = new LinkedList();

LinkedList.Circular.prototype.append = function(node) {
  if (this.first === null) {
    node.prev = node;
    node.next = node;
    this.first = node;
    this.last = node;
  } else {
    node.prev = this.last;
    node.next = this.first;
    this.first.prev = node;
    this.last.next = node;
    this.last = node;
  }
  this.length++;
};

LinkedList.Circular.prototype.insertAfter = function(node, newNode) {
  newNode.prev = node;
  newNode.next = node.next;
  node.next.prev = newNode;
  node.next = newNode;
  if (newNode.prev == this.last) { this.last = newNode; }
  this.length++;
};

LinkedList.Circular.prototype.insertBefore = function(node, newNode) {
	newNode.prev = node.prev;
	newNode.next = node;

	if (node.prev == this.last) {
		this.first = newNode;
		this.last.next = newNode;
	}
	else 
	{
		node.prev.next = newNode;
	}
	node.prev = newNode;
	this.length++;
};

LinkedList.Circular.prototype.remove = function(node) {
  if (this.length > 1) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    if (node == this.first) { this.first = node.next; }
    if (node == this.last) { this.last = node.prev; }
  } else {
    this.first = null;
    this.last = null;
  }
  node.prev = null;
  node.next = null;
  this.length--;
};

LinkedList.Circular.prototype.getFirst = function() {
  return this.first;
};

LinkedList.Circular.prototype.getLast = function() {
  return this.last;
};

LinkedList.Circular.prototype.getLength = function() {
  return this.length;
};

LinkedList.Circular.prototype.removeFirst = function() {
  var tempNode = this.first;
  this.remove(tempNode);
  return tempNode;
};

LinkedList.Circular.prototype.removeLast = function() {
  var tempNode = this.last;
  this.remove(tempNode);
  return tempNode;
};
                              
LinkedList.Circular.prototype.insertAtBeginning = function(node) {
  if (this.first == null)
  {
    this.append(node); 
  } 
  else 
  {
    this.insertBefore(this.first, node);
  }
};

LinkedList.Circular.prototype.getFirst = function() {
  return this.first;
};