首页 > 代码库 > javascript中的链表结构—从链表中删除元素
javascript中的链表结构—从链表中删除元素
1.概念
上一个博文我们讲到链表,其中有一个方法remove()是暂时注释的,这个方法有点复杂,需要添加一个Previous()方法找到要删除的元素的前一个节点,这一个博文我们来分析一下这个remove()方法。
从链表中删除节点的时候,需要先找到这个待删除节点的前面的节点。找到这个节点之后修改它的next属性,使其指向待删除节点的下一个节点,这样就把待删除节点给删除了,是不是很简单呢?但是问题来了,我们是不是要找到待删除节点的前面一个节点呢?这样就需要添加一个findPrevious()方法来做这件事情。
findPrevious()方法遍历链表中的元素,检查每一个节点的下一个节点是否存储着待删除数据。如果找到,返回该节点(即前面的节点),这样就可以修改它的next属性了。findPrevious()方法定义如下:
function findPrevious(item){ var currNode = this.head; while ( (currNode.next != null) && (currNode.next.element != item) ){ currNode = currNode.next; } return currNode;}
有了这个findPrevious()方法之后就可以考虑如何写这个remove()方法了。代码如下:
function remove(item){ var preNode = this.findPrevious(item); if(preNode.next != null){ preNode.next = preNode.next.next; }}
该方法中有一句preNode.next = preNode.next.next;这个使用了javascript中的对象属性,看起来有点奇怪,但是完全能说得通。
2.代码实现
下面的是完整的代码和测试代码:
function Node(element) { this.element = element; this.next = null;}function LList() { this.head = new Node(‘head‘); this.find = find; this.insert = insert; this.findPrevious = findPrevious; this.remove = remove; this.display = display;}function find(item) { var currNode = this.head; while(currNode.element != item) { currNode = currNode.next; } return currNode;}//插入一个元素function insert(newElement, item) { var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; current.next = newNode;}function findPrevious(item){ var currNode = this.head; while ( (currNode.next != null) && (currNode.next.element != item) ){ currNode = currNode.next; } return currNode;}function remove(item){ var preNode = this.findPrevious(item); if(preNode.next != null){ preNode.next = preNode.next.next; }}function display() { var currNode = this.head; while(!(currNode.next == null)) { document.write(currNode.next.element + ‘ ‘); currNode = currNode.next; }}//测试程序var cities = new LList();cities.insert("Conway", "head");cities.insert("Russellville", "Conway");cities.insert("Carlise", "Russellville");cities.insert("Alma", "Carlise");cities.display();document.write(‘<br>‘);cities.remove(‘Carlise‘);cities.display();
最后的输出结果如下:
javascript中的链表结构—从链表中删除元素
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。