数据结构与算法-双向链表(js实现)
程序员文章站
2024-01-23 21:24:58
...
为什么需要双向链表
对于单向链表来说,从链表的头节点遍历到尾节点很简单,但反过来,从后向前遍历则没那么简单。另外,删除节点时我们需要借助于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*/
上一篇: Java代码中可以优化性能的小细节