SOURCE

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

function DLinkedList() {
  this.length = 0;
  this.head = null;
  this.tail = null;
}

// 添加元素到链表尾部
DLinkedList.prototype.append = function(item) {
  if (this.length === 0) {
    this.head = item;
    this.tail = item;
  } else {
    var current = this.head;
    while(current.next) {
      current = current.next;
    }
    current.next = item;
    item.prev = current;
    this.tail = item;
  }
  this.length++;
}

// 添加元素到链表指定位置
DLinkedList.prototype.insert = function(position, item) {
  var current = this.head;
  
  if (position === 0) {
    if (this.head === null) {
      this.head = item;
      this.tail = item;
    } else {
      this.head.prev = item;
      item.next = this.head;
      this.head = item;
    }
  } else if (position >= this.length) { 
    this.tail.next = item;
    item.prev = this.tail;
    this.tail = item;
  } else {
    var index = 0;
    while (position > index) {
      current = current.next;
      index++;
    }
    current.prev.next = item;
    item.prev = current.prev;
    item.next = current;
  }
  
  this.length++;
}

// 移除链表中某个位置的元素
DLinkedList.prototype.removeAt = function(postion) {
  var current = this.head;
  var index = 0;
  if (postion === this.length - 1) {
    this.tail.prev.next = null;
    this.tail = this.tail.prev;
  } else {
    while(current.next) {
      if (postion === index) {
        if (postion === 0) {
          this.head = this.head.next;
          this.head.prev = null;
        } else {
          current.next.prev = current.prev;
          current.prev.next = current.next;
        }
        return;
      }
      current = current.next;
      index++;
    }
  }
  
  this.length--;
}

// 返回链表头部
DLinkedList.prototype.showHead = function() {
  return this.head;
}

// 返回链表尾部
DLinkedList.prototype.showTail = function() {
  return this.tail;
}

// 返回链表长度
DLinkedList.prototype.size = function() {
  return this.length;
}

// 将链表所有内容以字符串输出
DLinkedList.prototype.toString = function() {
  var current = this.head;
  var content = current.item.toString();
  while(current.next) {
    current = current.next;
    content += current.item.toString();
  }
  return content;
}


var n1 = new Node(9);
var n2 = new Node(8);
var n3 = new Node(6);
var l = new DLinkedList();
l.append(n1);
l.append(n2);
l.insert(3, n3);
console.log(l.toString());
l.removeAt(1);
console.log(l.toString());