find 方法同时展示了如何在链表上移动。首先,创建一个新节点,将链表的头节点赋给这个新创建的节点,然后在链表上循环,如果当前节点的 element 属性和我们要找的信息不符,就将当前节点移动到下一个节点,如果查找成功,该方法返回包含该数据的节点;否则,就会返回null。
一旦找到了节点,我们就可以将新的节点插入到链表中了,将新节点的 next 属性设置为后面节点的 next 属性对应的值,然后设置后面节点的 next 属性指向新的节点,具体实现如下:
//插入节点 function insert ( newElement , item ) { var newNode = new Node( newElement ); var currNode = this.find( item ); newNode.next = currNode.next; currNode.next = newNode; }
现在我们可以测试我们的链表了。等等,我们先来定义一个 display 方法显示链表的元素,不然我们怎么知道对不对呢?
display:显示链表
//显示链表元素 function display () { var currNode = this.head; while ( !(currNode.next == null) ){ console.log( currNode.next.element ); currNode = currNode.next; } }
实现原理同上,将头节点赋给一个新的变量,然后循环链表,直到当前节点的 next 属性为 null 时停止循环,我们循环过程中将每个节点的数据打印出来就好了。
var fruits = new LList(); fruits.insert('Apple' , 'head'); fruits.insert('Banana' , 'Apple'); fruits.insert('Pear' , 'Banana'); console.log(fruits.display()); // Apple // Banana // Pear
remove:从链表中删除一个节点
从链表中删除节点时,我们先要找个待删除节点的前一个节点,找到后,我们修改它的 next 属性,使其不在指向待删除的节点,而是待删除节点的下一个节点。那么,我们就得需要定义一个 findPrevious 方法遍历链表,检查每一个节点的下一个节点是否存储待删除的数据。如果找到,返回该节点,这样就可以修改它的 next 属性了。 findPrevious 的实现如下: //查找带删除节点的前一个节点 function findPrev( item ) { var currNode = this.head; while ( !( currNode.next == null) && ( currNode.next.element != item )){ currNode = currNode.next; } return currNode; }
这样,remove 方法的实现也就迎刃而解了
//删除节点 function remove ( item ) { var prevNode = this.findPrev( item ); if( !( prevNode.next == null ) ){ prevNode.next = prevNode.next.next; } }
我们接着写一段测试程序,测试一下 remove 方法:
// 接着上面的代码,我们再添加一个水果 fruits.insert('Grape' , 'Pear'); console.log(fruits.display()); // Apple // Banana // Pear // Grape // 我们把香蕉吃掉 fruits.remove('Banana'); console.log(fruits.display()); // Apple // Pear // Grape
Great!成功了,现在你已经可以实现一个基本的单向链表了。
双向链表尽管从链表的头节点遍历链表很简单,但是反过来,从后向前遍历却不容易。我们可以通过给Node类增加一个previous属性,让其指向前驱节点的链接,这样就形成了双向链表,如下图:
双向链表
此时,向链表插入一个节点就要更改节点的前驱和后继了,但是删除节点的效率提高了,不再需要寻找待删除节点的前驱节点了。
双向链表的实现要实现双向链表,首先需要给 Node 类增加一个 previous 属性:
//节点类 function Node(element) { this.element = element; //当前节点的元素 this.next = null; //下一个节点链接 this.previous = null; //上一个节点链接 }
双向链表的 insert 方法与单链表相似,但需要设置新节点的 previous 属性,使其指向该节点的前驱,定义如下:
//插入节点 function insert ( newElement , item ) { var newNode = new Node( newElement ); var currNode = this.find( item ); newNode.next = currNode.next; newNode.previous = currNode; currNode.next = newNode; }
双向链表的删除 remove 方法比单链表效率高,不需要查找前驱节点,只要找出待删除节点,然后将该节点的前驱 next 属性指向待删除节点的后继,设置该节点后继 previous 属性,指向待删除节点的前驱即可。定义如下:
//删除节点 function remove ( 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; } }