用js来实现那些数据结构08（链表02-双向链表）

function DoublyLinkedList() {
  let Node = function (element) {
    this.element = element;
    this.next = null;
    //在双向链表中，这里多了个指向前一个节点元素的指针prev
    this.prev = null;
  }

  let length = 0;
  let head = null;
  //同样的这里多了一个保存链表最后一项节点的引用变量，为什么要加这个变量？
  //因为是双向链表，普通链表只能从头到尾的迭代各节点元素，一方面是因为普通链表中只有一个存储头部节点元素的head变量。
  //但是双向链表可以从尾部开始迭代，这就是tail的意义。
  let tail = null;
}

//我们来看看双向链表中insert方法,普通链表中，我们只需要控制next指针就可以了，但是在双向链表中，在控制next指针的同时，我们还要控制prev指针
this.insert = function (position,element) {
  //在普通链表中在任意位置添加元素有两种情况，一个是添加到头部，另外一个是除了头部以外的其他位置，
  //在双向链表中除了这两种情况，还多了一种，添加在链表尾部
  if(position >= 0 && position <= length) {
    let node = new Node(element);
    let current = head;
    let previous;
    let index = 0;
    //添加到头部的情况
    if(position === 0) {
      //这里，如果head为null，也就是说该链表是没有任何节点元素的情况，那么加入的这个节点元素在链表中是唯一的
      //所以，head引用为node，tail的引用也为node
      if(!head) {
        head = node;
        tail = node;
      //那么如果，head不为null，说明链表中存在至少一个元素。
      } else {
        //由于current就是head，那么要插入节点元素的话只要把node的next指针指向current，就说明我们在current前面插入了该节点元素。
        node.next = current;
        //因为是双向列表，我们还要给current.prev一个指向。
        current.prev = node;
        //那么既然我们在current前面插入了元素，这里也就要改变head的引用，变为我们插入的node
        head = node;
      }
      //如果我们想要插入尾部的情况
    } else if(position === length) {
      //这里稍微有趣一点，这里我们要在尾部加入元素，不用像普通链表那样迭代到最后一项再操作。
      //我们只需要把current直接置为tail的引用就可以了，方便快捷
      current = tail;
      //那么我们已经拿到了最后一项节点元素的引用并且设置为了current。
      //我们只需要把current（tail）的next指向node节点元素，并且把node的prev只想current。
      //其实就是说，current节点的next指针不再是null了，因为我们在它的后面增加了一个“插入元素”，所以它的next指针为node
      //而此时node的prev指针也就理所当然的指向了current。
      current.next = node;
      node.prev = current;
      //插入元素完成，但是我们此时的tail其实是current不是node，所以更改一下tail的引用。
      tail = node;
    } else {
      while(index++ < position) {
        //依次往后移动...不多说
        previous = current;
        current = current.next;
      }
      //在移动到需要插入节点元素的位置时。
      //我们要插入在current的前面，自然就会有下面的结果了
      node.next = current;
      previous.next = node;
      //但是我们由于是双向链表，我们不仅仅要修改next指针，还要修改prev指针
      current.prev = node;
      node.prev = previous;
    }
    length++;
    return true;
  } else {
    return false;
  }
}

this.removeAt = function (position) {
  if(position > -1 && position < length) {
    let current = head,previous,index = 0;

    if(position === 0) {
      head = current.next;
      if(length === 1) {
        tail = null
      } else {
        head.prev = null;
      }
    } else if(position === length - 1) {
      current = tail;
      tail = current.prev;
      tail.next = null;
    } else {
      while(index++ < position) {
        previous = current;
        current = current.next;
      }

      previous.next = current.next;
      current.next.prev = previous;
    }

    length --;
    return current.element;
  } else {
    return null;
  }
}