数据结构与算法－双向链表(js实现)

为什么需要双向链表

　　对于单向链表来说，从链表的头节点遍历到尾节点很简单，但反过来,从后向前遍历则没那么简单。另外，删除节点时我们需要借助于findPrevious这样一个辅助方法来实现，显得很繁琐。(此文章是对上一篇文章的后续，点击此处进入上一篇文章)

双向链表的实现

　　首先Node类需要增加一个previous属性:

function Node(element) {
  this.element = element;
  this.next = null;
  this.previous = null;
}

　　insert方法需要添加previous属性，使其指向该节点的前驱: 

insert: function(newElement, item) {
  var newNode = new Node(newElement);
  var current = this.find(item);
  newNode.next = current.next;
  newNode.previous = current;
  current.next = newNode;
}

 　　remove方法将不再依赖于findPrevious方法，只需要在链表中找出存储待删除数据的节点,然后设置该节前驱的 next 属性,使其指向待删除节点的后继;设置该节点后继的 previous 属性,使其指向待删除节点的前驱。如下图所示：

remove: function(item) {
  var currNode = this.find(item);
  if (!(currNode.next == null)) {
    currNode.previous.next = currNode.next;
    currNode.next.previous = currNode.previous;
    currNode.next = null;
    currNode.previous = null;
  }
}

 　　增加反序显示链表的方法dispReverse: 

//我们需要一个工具方法findLast来查找链表中的最后一个节点
findLast: function() {
  var currNode = this.head;
  while (!(currNode.next == null)) {
    currNode = currNode.next;
  }
  return currNode;
}
//反序显示链表数据
dispReverse: function() {
  var currNode = this.head;
  currNode = this.findLast();
  while (!(currNode.previous == null)) {
    console.log(currNode.element);
    currNode = currNode.previous;
  }
}

　　完整的双向链表实现代码：

//节点类
function Node(element) {
  this.element = element;
  this.next = null;
  this.previous = null;
}
//链表类
function LList() {
  this.head = new Node("head");
}
LList.prototype={
　//反向显示所有节点
  dispReverse:function(){
    var currNode = this.head;
    currNode = this.findLast();
    while (!(currNode.previous == null)) {
      console.log(currNode.element);
      currNode = currNode.previous;
    }
  },
　//查找尾节点
  findLast:function(){
    var currNode = this.head;
    while (!(currNode.next == null)) {
      currNode = currNode.next;
    }
    return currNode;
  },
　//删除节点
  remove:function(item){
    var currNode = this.find(item);
    if (!(currNode.next == null)) {
      currNode.previous.next = currNode.next;
      currNode.next.previous = currNode.previous;
      currNode.next = null;
      currNode.previous = null;
    }
  },
　//查找节点
  find:function(item) {
    var currNode = this.head;
    while (currNode.element != item) {
      currNode = currNode.next;
    }
    return currNode;
  },
　//插入节点
  insert:function(newElement, item) {
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    newNode.previous = current;
    current.next = newNode;
  },
　//正常显示所有节点
  display:function() {
    var currNode = this.head;
    while (!(currNode.next == null)) {
      console.log(currNode.next.element);
      currNode = currNode.next;
    }
  }
}

　　测试：

var lk=new LList();
//添加4个节点
lk.insert("likek","head");
lk.insert("zhangsan","likek");
lk.insert("lisi","zhangsan");
lk.insert("wangba","lisi");
//正常显示
lk.display();
/*likek
 zhangsan
 lisi
 wangba*/
//反向显示
lk.dispReverse();
/*wangba
 lisi
 zhangsan
 likek*/
//删除节点
lk.remove("lisi");
lk.display();
/*likek
 zhangsan
 wangba*/