由于链表的特殊性，我们a->b->c->d ，如果要删除c那么就必须修改b.next->c为 b.next->d，所以找到前一个节修改其链表next地址，这个有点像dom操作中removeChild找到其父节点调用移除子节点
同样的我们也在remove方法的设计中，需要设计一个遍历往上回溯一个父节点即可
//找到前一个节 var findPrevious = function(currNode) { return function(key){ while (!(currNode.next == null) && (currNode.next.data != key)) { currNode = currNode.next; } return currNode; } }(headNode); //插入方法 this.remove = function(key) { var prevNode = findPrevious(key); if (!(prevNode.next == null)) { //修改链表关系 prevNode.next = prevNode.next.next; } };
测试代码：
<!doctype html><button>插入多条数据</button> <button>删除Russellville数据</button><div><br /></div><script type="text/javascript"> ////////// //创建链表 // ////////// function createLinkList() { //创建节 function createNode(data) { this.data = data; this.next = null; } //初始化头部节 //从headNode开始形成一条链条 //通过next衔接 var headNode = new createNode("head"); //在链表中找到对应的节 var findNode = function createFindNode(currNode) { return function(key) { //循环找到执行的节，如果没有返回本身 while (currNode.data != key) { currNode = currNode.next; } return currNode; } }(headNode); //找到前一个节 var findPrevious = function(currNode) { return function(key) { while (!(currNode.next == null) && (currNode.next.data != key)) { currNode = currNode.next; } return currNode; } }(headNode); //插入一个新节 this.insert = function(data, key) { //创建一个新节 var newNode = new createNode(data); //在链条中找到对应的数据节 //然后把新加入的挂进去 var current = findNode(key); //插入新的接，更改引用关系 //1:a-b-c-d //2:a-b-n-c-d newNode.next = current.next; current.next = newNode; }; //插入方法 this.remove = function(key) { var prevNode = findPrevious(key); if (!(prevNode.next == null)) { //修改链表关系 prevNode.next = prevNode.next.next; } }; this.display = function(fn) { var currNode = headNode; while (!(currNode.next == null)) { currNode = currNode.next; fn(currNode.data) } }; } var cities = new createLinkList(); function create() { var text = ''; cities.display(function(data) { text += '-' + data; }); var div = document.createElement('div') div.innerHTML = text; document.getElementById("listshow").appendChild(div) } document.getElementById("test1").onclick = function() { cities.insert("Conway", "head"); cities.insert("Russellville", "Conway"); cities.insert("Carlisle", "Russellville"); cities.insert("Alma", "Carlisle"); create(); } document.getElementById("test2").onclick = function() { cities.remove("Russellville"); create() } </script>
双链表
原理跟单链表是一样的，无非就是给每一个节增加一个前链表的指针
增加节
//插入一个新节 this.insert = function(data, key) { //创建一个新节 var newNode = new createNode(data); //在链条中找到对应的数据节 //然后把新加入的挂进去 var current = findNode(headNode,key); //插入新的接，更改引用关系 newNode.next = current.next; newNode.previous = current current.next = newNode; };
删除节
this.remove = function(key) { var currNode = findNode(headNode,key); if (!(currNode.next == null)) { currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; } };
在删除操作中有一个明显的优化：不需要找到父节了，因为双链表的双向引用所以效率比单链要高
测试代码：