欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-01-23 21:16:28
...

为什么需要双向链表

  对于单向链表来说,从链表的头节点遍历到尾节点很简单,但反过来,从后向前遍历则没那么简单。另外,删除节点时我们需要借助于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 属性,使其指向待删除节点的前驱。如下图所示:

数据结构与算法-双向链表(js实现)
            
    
    博客分类: 数据结构与算法学习笔记 javascript数据结构算法web 

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*/
  • 数据结构与算法-双向链表(js实现)
            
    
    博客分类: 数据结构与算法学习笔记 javascript数据结构算法web 
  • 大小: 31.9 KB