JavaScript Data Structure

doubly-linked-list.js

// Node
var Node = function(key) {
  this.key = key;
  this.next = null;
  this.prev = null;
};

Node.prototype = {
  getKey: function() { return this.key; }
  ,
  getNext: function() { return this.next; }
  ,
  setNext: function(next) { this.next = next; }
  ,
  getPrev: function() { return this.prev; }
  ,
  setPrev: function(prev) { this.prev = prev; }
  ,
  connect: function(node) {
    if (this.next !== null) {
      node.connect(this.next);
    }
    this.next = node;
    node.setPrev(this);
  },
  disconnect: function() { 
    var next = this.next,
        prev = this.prev;
    this.next = null;
    this.prev = null;
    prev.connect(next); 
  }
};

// Linked List
var DoublyLinkedList = function() {
  this.size = 0;
  this.head = new Node(null);
  this.tail = new Node(null);
  this.head.connect(this.tail);
};

DoublyLinkedList.prototype = {
  length: function() { return this.size; }
  ,
  first: function() { return this.head.getNext(); }
  ,
  last: function() { return this.tail.getPrev(); }
  ,
  search: function(key) {
    var node = this.head;
    for (var i=0; i<this.size; i++) {
      node = node.getNext();
      if (node !== null && node.getKey() === key) {
        return node;
      }
    }
    return null;
  },
  next: function(key) { return this.search(key) ? this.search(key).getNext() : null; }
  ,
  prev: function(key) { return this.search(key) ? this.search(key).getPrev() : null; }
  ,
  insert: function(key) {
    this.head.connect(new Node(key));
    this.size++;
  },
  insertBack: function(key) {
    var node = this.last();
    node.connect(new Node(key));
    this.size++;
  },
  insertAt: function(key, loc) {
    var node = this.search(loc);
    if (!node) {
      this.insert(new Node(key));
    } else {
      node.connect(new Node(key));
    }
    this.size++;
  },
  delete: function(key) {
    var node = this.search(key);
    if (!node) {
      node.disconnect();
      this.size--;
    }
  }
}