基本介绍链表是一个有序列表，但是它在内存中的存储方式如下。链表以节点的形式存储。每个节点包含一个数据字段，next字段：指向下一个节点。如图：找到每个链表的每个节点不一定是连续存储的链表，分为有头节点的链表和没有头节点的链表。根据实际需要确定。单链表介绍单链表（首节点）的逻辑结构示意图如下。链表实现——水浒英雄排行榜管理包com.structures.linkedlist；publicclassSingleLinkedListDemo{publicstaticvoidmain(String[]args){HeroNodeheroNode1=newHeroNode(1,"宋江","及时雨");HeroNodeheroNode2=newHeroNode(2,"卢俊义","玉麒麟");HeroNodeheroNode3=newHeroNode(3,"吴用","智多星");HeroNodeheroNode4=newHeroNode(4,"林冲","豹头");SingleLinkedListsingleLinkedList=newSingleLinkedList();singleLinkedList.add(heroNode3);singleLinkedList.add(heroNode2);singleLinkedList.add(heroNode4);singleLinkedList.add(heroNode1);singleLinkedList.list();}}//定义SingleLinkedList来管理我们的英雄类SingleLinkedList{//先初始化一个头节点，头节点不能以后使用privateHeroNodehead=newHeroNode(0,"","");//向单向链表添加节点//思路：当不考虑数字顺序时//1.找到当前链表的最后一个节点//2.将最后一个节点的next字段指向新节点publicvoidadd(HeroNodenode){//因为头节点不能移动，所以我们需要一个辅助遍历linkedlist//如果没有找到temp，则往回移动temp=temp.next;}temp.next=node;}//显示链表[traversal]publicvoidlist(){//判断链表是否存在isemptyif(head.next==null){System.out.println("Thelinkedlistisempty");}//因为头节点不能移动，我们需要一个辅助变量来遍历HeroNodetemp=head.next;while(temp!=null){//判断是否在末尾//输出节点信息System.out.println(temp);//将temp移回temp=temp.next;}}}//定义一个HeroNode,每个HeroNode对象都是一个节点classHeroNode{publicintno;publicStringname;publicStringnickName;publicHeroNodenext;//指向下一个节点//构造函数this.next=next;}@OverridepublicStringtoString(){return"HeroNode{"+"no="+no+",name='"+name+'\''+",nickName='"+nickName+'\''+'}';}}/*HeroNode{no=3,name='吴庸',nickName='智多星'}HeroNode{no=2,name='卢俊义',nickName='于麒麟'}HeroNode{no=4,name='林冲',nickName='豹头'}HeroNode{no=1,name='宋江',nickName='及时雨'}*/可以看到上面链表的实现，添加英雄时，并没有按照排序英雄的数量。接下来重写一个加法实现插入英雄时按序号排序packagecom.structures.linkedlist；"卢俊义","玉麒麟");HeroNodeheroNode3=newHeroNode(3,"吴庸","智多星");HeroNodeheroNode4=newHeroNode(4,"林冲","豹头");SingleLinkedListsingleLinkedList=newSingleLinkedList();singleLinkedList.addByNo(heroNode3);singleLinkedList.addByNo(heroNode2);singleLinkedList.addByNo(heroNode4);singleLinkedList.addByNo(heroNode1);singleLinkedList.list();}}//定义SingleLinkedList来管理我们的英雄classSingleLinkedList{//先初始化一个头节点，头节点不能移动，使用privateHeroNodehead=newHeroNode(0,"","");//向单向链表添加节点//思路：当数字的顺序为不考虑//1。找到当前链表的最后一个节点//2。将上一个节点的next字段指向新节点publicvoidadd(HeroNodenode){//因为头节点不能移动，我们需要辅助遍历tempHeroNodetemp=head;//遍历链表，找到链表的尾部while(temp.next!=null){//找到链表的尾部//如果没有找到temp，则向后移动temp=temp.next;}temp.next=node;}//第二种添加英雄的方式，添加英雄时，根据排名将英雄插入到指定位置//如果有这个排名，则添加失败，并提示给publicvoidaddByNo(HeroNodeheroNode){//因为头节点不能移动，所以我们需要一个辅助遍历temp//因为是单链表，我们要找的temp是添加位置的前一个节点，否则HeroNodetemp=head;booleanflag=false;//判断加入的数字是否存在，默认为falsewhile(true){if(temp.next==null){break;}if(temp.next.no>heroNode.no){//位置找到了，在temp后面插入break即可;}elseif(temp.next.no==heroNode.no){//数字已经存在flag=true;break;}temp=temp.next;}if(flag){System.out.printf("要插入的英雄编号%dl已经存在，不能添加\n",heroNode.no);}else{//在链表temp后面插入heroNode.next=temp.next;temp.next=heroNode;}}//显示链表[遍历]publicvoidlist(){//判断链表是否为空if(head.next==null){System.out.println("Thelinkedlistisempty");}//因为头节点不能移动，我们需要辅助变量遍历HeroNodetemp=head.next;while(temp!=null){//判断是否在末尾//输出节点信息System.out.println(temp);//将temp移回temp=temp.next;}}}//定义一个HeroNode,每个HeroNode对象都是一个节点classHeroNode{publicintno;publicStringname;publicStringnickName;publicHeroNodeext;//指向下一个节点//构造器){this.next=next;}@OverridepublicStringtoString(){return"HeroNode{"+"no="+no+",name='"+name+'\''+",nickName='"+nickName+'\''+'}';}}/*HeroNode{no=1,name='宋江',nickName='及时雨'}HeroNode{no=2,name='卢俊义',nickName='玉麒麟'}HeroNode{no=3,name='吴勇',nickName='支多星'}HeroNode{no=4,name='林冲',nickName='豹头'}*/再次完善功能，增加功能ofmodifyingthenode//修改节点信息根据no编号修改，即编号no不可修改。publicvoidupdate(HeroNodeheroNode){//判断是否为空if(head.next==null){System.out.println("链表为空");}//找到需要修改的节点,根据编号heroNodetemp=head.next;booleanflag=false;//表示是否找到节点while(true){if(temp==null){break;}if(temp.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){temp.name=heroNode.name;temp.nickName=heroNode.nickName;}else{System.out.printf("没有节点找到%d号，无法修改\n"，heroNode.no);}}再次完善函数，增删节点函数//删除节点publicvoidremove(HeroNodeheroNode){//判断是否为空if(head.next==null){System.out.println("链表为空");}HeroNodetemp=head.next;booleanflag=false;//标识是否找到要删除的点while(true){if(temp==null){break;}if(temp.next.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){temp.next=temp.next.next;}else{System.out.printf("Cannotdeletenodenumber%d,\n",heroNode.no);}}再次完善功能，增加统计单链表有效节点数的功能/***获取有效节点数单向链表，不计头节点*@paramhead链表的头节点*@return有效节点数*/publicstaticintgetLength(HeroNodehead){if(head.next==null){return0;}intcount=0;HeroNodetemp=head.next;while(temp.next!=null){count++;temp=temp.next;}returncount;}再次完善功能，补充ng求单链表倒数第K个节点的函数/***求单链表倒数第K个节点【新浪面试题】*思路：*1.先把链表从头到尾遍历，得到链表总长度*2。得到大小后，从链表的第一个开始遍历到(size-index)，可以得到**@paramhead*@paramindex表示最后一个索引节点*@return*/publicstaticHeroNodefindLastIndexNode(HeroNodehead,intindex){if(head.next==null){returnnull;}intsize=getLength(head);if(index<=0||index>size){returnnull;}HeroNodetemp=head.next;for(inti=0;i<(size-index);i++){temp=temp.next;}returntemp;}再次完善功能，增加单链表的反向功能/***反向链表【腾讯面试题】*思路：*1。首先定义一个reverseHead=newHeroHead();*2.从头到尾遍历原链表，取出遍历的每个节点，放在新链表的最前面；*3。Head.next=reverseHead.next原链表;*/publicstaticvoidreverseList(HeroNodehead){if(head.next==null||head.next.next==null){return;}HeroNodecurr=head。next;HeroNodeext=null;//指向当前节点的下一个节点[curr]HeroNodereverseHead=newHeroNode(0,"","");while(curr!=null){next=curr.next;//保存临时curr节点的下一个节点curr.next=reverseHead.next;//将curr的下一个节点指向新链表的前面reverseHead.next=curr;//将curr连接到新链表curr=next;//让curr向后移动}head.next=reverseHead.next;}再次完善功能，增加从头到尾打印单链表的功能/***使用栈倒序打印【百度面试题】*/publicstaticvoidreversePrint(HeroNodehead){if(head.next==null){return;}Stack
