第六章链表

链表简介

双向链表

双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

//节点 function Node(element) { this.element=element; this.next=null;//向后节点的指向 this.previous=null;//向前节点的指向 } //对链表进行操作的方法 function List() { this.head=new Node("head"); this.find=find; this.findPrevious=findPrevious; this.findLast=findLast; this.insert=insert; this.remove=remove; this.display=display; this.dispReverse=dispReverse; this.currNode=this.head; } //查找节点 function find(item) { let currNode=this.head; while(currNode.element !=item) { currNode=currNode.next; } return currNode; } function findPrevious(item) { let currNode=this.head; while(!(currNode.next==null)&&(currNode.next.element!=item)) { currNode=currNode.next; } return currNode; } //插入节点 function insert(newElement,item) { let newNode=new Node(newElement); let currNode=this.find(item); newNode.next=currNode.next; newNode.previous=currNode; currNode.next=newNode; } //删除节点 function remove(item) { let currNode=this.find(item); if (!(currNode.next==null)) { currNode.previous.next=currNode.next; currNode.next.previous=currNode.previous; currNode.next=null; currNode.previous=null; } } //查找最后的节点 function findLast() { let currNode=this.head; while(!(currNode.next==null)){ currNode=currNode.next; } return currNode; } //反序显示 function dispReverse() { let currNode=this.findLast(); while(!(currNode.previous==null)) { console.log(currNode.element); currNode=currNode.previous; } } function display() { let currNode=this.head; while(!(currNode.next==null)){ console.log(currNode.next.element); currNode=currNode.next; } } module.exports=List; //测试 let cities=new List(); cities.insert("Conway", "head"); cities.insert("Russellville", "Conway"); cities.insert("Alma", "Russellville"); cities.display(); cities.remove("Russellville"); console.log("删除后:"); cities.display(); console.log("反序显示:"); cities.dispReverse();

循环列表

循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让 其头节点的 next 属性指向它本身，即：head.next = head
这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。换 句话说，链表的尾节点指向头节点，形成了一个循环链表，如图所示。

//循环列表 //节点 function Node(element) { this.element=element; this.next=null; } //对链表进行操作的方法 function List() { this.head=new Node("head"); this.head.next=this.head; this.find=find; this.findPrevious=findPrevious; this.insert=insert; this.remove=remove; this.display=display; this.currNode=this.head; this.back=back; this.count=count; } //查找节点 function find(item) { let currNode=this.head; while(currNode.element !=item) { currNode=currNode.next; } return currNode; } function findPrevious(item) { let currNode=this.head; while(!(currNode.next==null)&&(currNode.next.element!=item)) { currNode=currNode.next; } return currNode; } //插入节点 function insert(newElement,item) { let newNode=new Node(newElement); let currNode=this.find(item); newNode.next=currNode.next; currNode.next=newNode; } //删除节点 function remove(item) { let prevNode=this.findPrevious(item); if (!(prevNode.next==null)) { prevNode.next=prevNode.next.next; } } //向后移动n个节点 function back(n) { while(n>0) { if (this.currNode.next.element=="head") { this.currNode=this.currNode.next.next; }else{ this.currNode=this.currNode.next; } n--; } } //当前链表的元素个数 function count() { let node=this.head; let i=0; while(!(node.next.element=="head")) { node=node.next; i++; } return i; } function display() { let currNode=this.head; while(!(currNode.next==null)&&!(currNode.next.element=="head")){ console.log(currNode.next.element); currNode=currNode.next; } } let cities = new List(); cities.insert("Conway", "head"); cities.insert("Russellville", "Conway"); cities.insert("Carlisle", "Russellville"); cities.insert("Alma", "Carlisle"); cities.display(); cities.remove("Carlisle"); console.log("删除后:"); cities.display() module.exports=List;

链表习题

1.向前移动n个节点

const List=require('./lesson5-1.js'); List.prototype.advance=function(n){ while((n>0) && !(this.currNode==null)) { this.currNode=this.currNode.previous; n--; } }

2.向后移动n个节点

List.prototype.back=function(n){ while((n>0) && !(this.currNode==null)) { this.currNode=this.currNode.next; n--; } }

3.只显示当前节点上的数据

List.prototype.show=function(){ return this.currNode?this.currNode.element:'溢出'; }

测试

let test=new List(); test.insert('A','head'); test.insert('B','A'); test.insert('C','B'); test.insert('D','C'); test.insert('E','D'); test.display(); console.log("向后移动三个节点"); test.back(3); console.log(test.show()); console.log("向前移动二个节点"); test.advance(2); console.log(test.show());

4.传说在公元 1 世纪的犹太战争中，犹太历史学家弗拉维奥·约瑟夫斯和他的40个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏，于是商量出了一个自杀方案。他们围成一个圈，从一个人开始，数到第三个人时将第三个人杀死，然后再数，直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏，他们快速地计算出了两个位置，站在那里得以幸存。写一段程序将 n 个人围成一圈，并且第 m 个人会被杀掉，计算一圈人中哪两个人最后会存活。使用循环链表解决该问题。

const cycList=require('./lesson5-2.js'); /** * @param cycList 链表 * @param n 移动数 * @param m 剩余人数 * @return */ function survice(cycList,n=3,m=2) { while(person.count()>m) { person.back(n); person.remove(person.currNode.element); console.log("剩余人："); person.display(); } } let person=new cycList(); person.insert('1','head'); person.insert('2', '1'); person.insert('3', '2'); person.insert('4', '3'); person.insert('5', '4'); person.insert('6', '5'); person.insert('7', '6'); person.insert('8', '7'); person.insert('9', '8'); person.insert('10','9'); person.display(); survice(person);