链表(Linked List)

链表(Linked List)

链表是有序的列表,但是它在内存中是存储如下的:

• 链表是以节点的方式存储的,链式存储
• 每个节点包含data域,next域指向下一个节点
• 如上图:链表的各个节点不一定是连续存放的.
• 链表分带头节点的链表和没有头节点的链表(根据实际的需求来确定)

 使用带head头的单项链表实现-水浒英雄排行榜管理
1.完成对英雄人物的增删改查操作,注意:删除和修改,查找
2,第一种方式,在添加英雄时直接添加到英雄的尾部,
3.第二种方式在添加英雄时,根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,并给出提示)

当链表的创建示意图,显示当下链表的分析

1.创建一个head头节点,作用是代表表示单链表的头.
2.后面没添加一个节点我们就加入到链表的最后
3.遍历:通过一个辅助遍历,帮助我们遍历这个链表
4.我们是以上面的题进行的解析,所有羡慕我们的classHeroNode中前三个都是数据,HerNode next 是next 域.

代码如下,第一种(按照顺序添加,直接添加到链表的尾部)

package com.atguigu.linkedlist;public class SingleLinkedListDemo {public static void main(String[] args) {//进行测试//先创建节点HeroNode hero1=  new HeroNode(1,"宋江","及时雨");HeroNode hero2= new HeroNode(2,"卢俊义","玉麒麟");HeroNode hero3= new HeroNode(3,"吴用","智多星");HeroNode hero4= new HeroNode(4,"林冲","豹子头");//创建一个链表SingleLinkedList singleLinkedList=new SingleLinkedList();//加入singleLinkedList.add(hero1);singleLinkedList.add(hero2);singleLinkedList.add(hero3);singleLinkedList.add(hero4);//显示一把singleLinkedList.show();}
}
//3,定义一个SilgleLinkedList管理我们的英雄
class SingleLinkedList{//先初始化一个头节点,头节点不要动,不存放具体数据private HeroNode head=new HeroNode(0,"","");//添加节点到单项链表//思路:当不考虑当前链表的顺序时//1,我们找到当前链表的最后节点//2.将最后这个节点的next 指向新的节点public void add(HeroNode heroNode){//因为head节点不能动,因此我们需要衣蛾辅助变量 tempHeroNode temp=head;//遍历链表找到最后一个while (true){//找到链表的最后==null){break;}//如果没哟找到最后,将temp后移temp&#;}//当退出whle循环时,说明temp指向了链表的最后//将最后这个节点next指向了新的节点=heroNode;}/*显示遍历*/public void show(){//先判断链表是否为空==null){System.out.println("链表为空");return;}//因为头节点不能动,因此我们需要一个辅助变量来遍历HeroNode temp&#;while (true){//判断是否到了链表的最后if(temp==null){break;}//输出节点的信息System.out.println(temp);//将temp后移,一定要后移,不然死循环temp&#;}}
}//定义一个HeroNode,每个HeroNode对象就是一个节点
class HeroNode{public int no;public  String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public  HeroNode(int hNo,String hName ,String hNickname){=hNo;this.name=hName;this.nickname=hNickname;}//为了显示方便,我们重新toString方法
//toString这里我们不要打出next域,看起来清晰一些@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + ''' +", nickname='" + nickname +'}';}
}

2,根据排名将英雄插入指定的位置.

1.首先找到新添加的节点的位置.是通过辅助变量(指针)
2,新的节点.next&#(就是将新的节点域变成原来那个(temp)节点域)
3,让=新的节点(原来的节点的next域指向新的新的节点的)

 代码实现

package com.atguigu.linkedlist;public class SingleLinkdeListDemo2 {public static void main(String[] args) {//进行测试//先创建节点HeroNode1 hero1=  new HeroNode1(1,"宋江","及时雨");HeroNode1 hero2= new HeroNode1(2,"卢俊义","玉麒麟");HeroNode1 hero3= new HeroNode1(3,"吴用","智多星");HeroNode1 hero4= new HeroNode1(4,"林冲","豹子头");//创建一个链表SingleLinkedList1 singleLinkedList1=new SingleLinkedList1();//加入按照编号的顺序singleLinkedList1.addByOrder(hero1);singleLinkedList1.addByOrder(hero4);singleLinkedList1.addByOrder(hero2);singleLinkedList1.addByOrder(hero3);/*    singleLinkedList1.addByOrder(hero3);这句测试准备添加的英雄已经存在
*///显示一把singleLinkedList1.show();}
}
//3,定义一个SilgleLinkedList1管理我们的英雄
class SingleLinkedList1{//先初始化一个头节点,头节点不要动,不存放具体数据private HeroNode1 head=new HeroNode1(0,"","");/*第二种添加英雄的方式,更根据排名将英雄插入到指定的位置* 如果有这个排名,则添加失败,并给出提示*/public void addByOrder(HeroNode1 heroNode1){//因为头节点不能动,因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置//因为单链表,因此我们找的这个temp是位于这个添加位置的前一个节点,否则插入不了HeroNode1 temp=head;boolean flag=false;//标识英雄添加的编号是否存在,默认为falsewhile (true){==null){//说明到来链表的最后,添加到最后break;//无论找没有找到,我们都要退出}o&){//编号大于插入的上一个编号,说明找到了,我们插入,在temp的后面添加break;}else o=&#) {//说明希望添加的heroNode编号存在flag = true;//说明编号存在break;}temp&#;//后移,遍历当前链表}//判断flag的值,if(flag){//flag为真不能添加,说明编号存在System.out.println("准备插入的英雄的编号"&#+"已经存在了,不能加入");}else {//插入到链表中,temp的后面&#;=heroNode1;}}/*显示遍历*/public void show(){//先判断链表是否为空==null){System.out.println("链表为空");return;}//因为头节点不能动,因此我们需要一个辅助变量来遍历HeroNode1 temp&#;while (true){//判断是否到了链表的最后if(temp==null){break;}//输出节点的信息System.out.println(temp);//将temp后移,一定要后移,不然死循环temp&#;}}
}//定义一个HeroNode,每个HeroNode对象就是一个节点
class HeroNode1{public int no;public  String name;public String nickname;public HeroNode1 next;//指向下一个节点//构造器public  HeroNode1(int hNo,String hName ,String hNickname){=hNo;this.name=hName;this.nickname=hNickname;}//为了显示方便,我们重新toString方法
//toString这里我们不要打出next域,看起来清晰一些@Overridepublic String toString() {return "HeroNode1{" +"no=" + no +", name='" + name + ''' +", nickname='" + nickname + ''' +'}';}}

节点的修改
1.找到待修改的节点,同通过遍历
2.temp.name=newHeroNod.name:temp.nickname=newHeroNode=nickname;

   /*修改节点的信息,根据no编号来修改,即no编号不能改变*///1.根据newHeroNode1的no来修改即可public void update(HeroNode1 newHeroNode1){//判断是否为空==null){System.out.println("链表为空");return;}//如果不为空,找到需要修改的节点//1.先定义一个辅助变量tempHeroNode1 temp&#;boolean flag1=false;//表示是否找到该节点while (true){if(temp==null){break;//已经遍历完链表}=&#){//找到flag1=true;break;}temp&#;}//根据flag判断是否找到要修改的节点if(flag1){//turetemp.name= newHeroNode1.name;;temp.nickname=newHeroNode1.nickname;}else {//没有找到编号等于这个的节点System.out.println("没有找到编号为"&#+"节点");}}

节点的删除

从单链表中删除一个节点的思路
1.我们先找到需要删除的这个节点的前一个节点temp
&#ext,(这里相当于我们直接跳过了被删除的节点,没有其它的引用指向,会被垃圾回收机制回收).

代码:

    /*删除节点*///1.head不能动,因此我们需要一个temp辅助节点找到待删除节点的前一个节点//2.说明我们在比较时,是 和需要删除的节点的no比较
public void del(int no){HeroNode1 temp=head;boolean flag=false;//标志是否找到待删除的节点while (true){==null){//已经找到最后,都没有找到break;}o==no){flag=true;break;}temp&#;//temp后移,遍历}//判断flagif(flag){//true 找到//可以删除&#ext;}else {System.out.println("没有找到要删除的节点"+no+"号节点");}
}

当链表面试题

求当链表中有效节点的个数

/*方法,获取到当链表节点的个数(如果是带头节点的链表,需要不统计头节点)*//**** @param head 链表的头节点* @return  返回的是有效节点的个数*/public static int getLength(HeroNode1 head){==null){//链表空return 0;}int length=0;//定义一个辅助变量HeroNode1 cur&#;//我们这里看出我们没有同意头节点while (cur!=null){length++;cur&#;//遍历}return length;}

求单链表节点倒数第k个节点

/*查找单链表的倒数第k个节点
* 思路:
* 1.写一个方法接受这个这个head节点同时接受一个
* 2,index表示倒数第index节点
* 3,单链表不能逆向遍历,先把链表从头到尾遍历,得到链表的总的长度size
* 4,得到size后,我们从链表的第一个开始遍历,遍历size-index个,就得到了我们倒数第k个
* 5.如果找到了,就返回该节点,找不动返回空*/public static HeroNode1 findLastIndexNode(HeroNode1 head,int index){==null){return null;//此时链表为空,我们没有找到}//第一次遍历,我们得到链表的格式int size=getLength(head);//第二次遍历,我们遍历size-index个,就是我们倒数的第k个节点//先做一个数据的校验if(index<=0||index>size){return null;}//定义一个辅助变量,for  循环定位到倒数的indexHeroNode1 cur&#;for(int i=0;i<size-index;i++){cur&#;}return cur;}

当链表的反转

思路:
1.先定义一个节点,reverseHead=new HeroNode();
2.从头到尾变量原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead的最前端
3.原来的链表的&#;

/*单链表的反转
* */public static void reversetList(HeroNode1 head){//如果当前列表为空,或者只有一个节点,无需反转,直接返回==null||==null){return;}//先定义一个辅助的指针(变量)HeroNode1 cur&#;HeroNode1 next=null;//指向当前节点(cur的节点,因为我们取出cur以后,我们没有指向下一个节点的标识)的下一个节点HeroNode1 reverseHead=new HeroNode1(0,"","");//变量原来的链表,每遍历一个节点,就将其取出,并方在新的链表reverseHead的最前端while (cur!=null){next&#;//这里next保存了当前节点的下一个节点,就是第一次因为我们一旦取出cur,那么这个节点就没有指向,我们之后找不到了&#;//将cur的下一个节点指向新的链表的头部,就是最前端=cur;//将这个cur连接到新的链表上cur=next;//让cur后移}//将这个指向实现单链表的反转&#;}

从尾到头打印链表

思路:上面这个题的要求就是逆序打印单链
2.方式1.先将单链表进行反装,然后遍历即可,这样做的问题是会破坏原来的单链表的结构(不建议)
3,方式2.可以利用栈这个数据结构,将各个节点压入到栈中,利用栈的先进后出的特点,就实现了逆序打印(这样会实现逆序打印,还不破坏单链表的结构)

/*使用方式二,压入栈进行逆向打印*/
public static void reversePrint(HeroNode1 head){==null){return;//空链表不能打印}//创建一个栈,将各个节点压入栈中.Stack<HeroNode1> stack=new Stack<HeroNode1>();HeroNode1 cur&#;//先保存当前节点//将链表的所有节点压入栈中,while (cur!=null){stack.push(cur);cur&#;//cur后移,这样就可以压入下一个节点}//将栈中的节点进行打印,pop进行出栈while (stack.size()>0){System.out.println(stack.pop());//栈的特点是先进入后出}
}

上面的整体的代码如下:

package com.atguigu.linkedlist;import jdk.nashorn.internal.objects.NativeUint8Array;import java.util.Stack;public class SingleLinkdeListDemo2 {public static void main(String[] args) {//进行测试//先创建节点HeroNode1 hero1=  new HeroNode1(1,"宋江","及时雨");HeroNode1 hero2= new HeroNode1(2,"卢俊义","玉麒麟");HeroNode1 hero3= new HeroNode1(3,"吴用","智多星");HeroNode1 hero4= new HeroNode1(4,"林冲","豹子头");HeroNode1 hero5= new HeroNode1(5,"林有","有有");HeroNode1 hero6= new HeroNode1(6,"林无","无无");//创建一个链表SingleLinkedList1 singleLinkedList1=new SingleLinkedList1();SingleLinkedList1 singleLinkedList2=new SingleLinkedList1();//加入按照编号的顺序singleLinkedList1.addByOrder(hero1);singleLinkedList1.addByOrder(hero4);singleLinkedList1.addByOrder(hero6);singleLinkedList1.addByOrder(hero2);singleLinkedList2.addByOrder(hero5);singleLinkedList2.addByOrder(hero3);/*    singleLinkedList1.addByOrder(hero3);这句测试准备添加的英雄已经存在
*///显示一把singleLinkedList1.show();System.out.println("=============");singleLinkedList2.show();//测试节点的修改HeroNode1 newHeroNode= new HeroNode1(2,"卢俊义...","玉麒麟...");singleLinkedList1.update(newHeroNode);System.out.println("修改后的链表请情况");singleLinkedList1.show();//测试节点的删除singleLinkedList1.del(1);singleLinkedList1.del(7);System.out.println("删除后的链表情况");singleLinkedList1.show();//测试单链表的有效节点个数System.out.println("有效的节点的个数="&#Head()));//测试一下,我们是否得到 了我们的倒数第一个元素System.out.println("倒数第一个元素是"+SingleLinkedList1.Head() ,1));//测试一下单链表的反转System.out.println("原来链表的情况");singleLinkedList1.show();System.out.println("反转单链表");Head());singleLinkedList1.show();//逆序打印单链表System.out.println("逆序打印单独链表");Head());}}
//3,定义一个SilgleLinkedList1管理我们的英雄
class SingleLinkedList1{//先初始化一个头节点,头节点不要动, 存放具体数据private HeroNode1 head=new HeroNode1(0,"","");public HeroNode1 getHead() {return head;}public void setHead(HeroNode1 head) {this.head = head;}/*第二种添加英雄的方式,更根据排名将英雄插入到指定的位置* 如果有这个排名,则添加失败,并给出提示*/public void addByOrder(HeroNode1 heroNode1){//因为头节点不能动,因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置//因为单链表,因此我们找的这个temp是位于这个添加位置的前一个节点,否则插入不了HeroNode1 temp=head;boolean flag=false;//标识英雄添加的编号是否存在,默认为falsewhile (true){==null){//说明到来链表的最后,添加到最后break;//无论找没有找到,我们都要退出}o&){//编号大于插入的上一个编号,说明找到了,我们插入,在temp的后面添加break;}else o=&#) {//说明希望添加的heroNode编号存在flag = true;//说明编号存在break;}temp&#;//后移,遍历当前链表}//判断flag的值,if(flag){//flag为真不能添加,说明编号存在System.out.println("准备插入的英雄的编号"&#+"已经存在了,不能加入");}else {//插入到链表中,temp的后面&#;=heroNode1;}}/*修改节点的信息,根据no编号来修改,即no编号不能改变*///1.根据newHeroNode1的no来修改即可public void update(HeroNode1 newHeroNode1){//判断是否为空==null){System.out.println("链表为空");return;}//如果不为空,找到需要修改的节点//1.先定义一个辅助变量tempHeroNode1 temp&#;boolean flag1=false;//表示是否找到该节点while (true){if(temp==null){break;//已经遍历完链表}=&#){//找到flag1=true;break;}temp&#;}//根据flag判断是否找到要修改的节点if(flag1){//turetemp.name= newHeroNode1.name;;temp.nickname=newHeroNode1.nickname;}else {//没有找到编号等于这个的节点System.out.println("没有找到编号为"&#+"节点");}}/*删除节点*///1.head不能动,因此我们需要一个temp辅助节点找到待删除节点的前一个节点//2.说明我们在比较时,是 和需要删除的节点的no比较
public void del(int no){HeroNode1 temp=head;boolean flag=false;//标志是否找到待删除的节点while (true){==null){//已经找到最后,都没有找到break;}o==no){flag=true;break;}temp&#;//temp后移,遍历}//判断flagif(flag){//true 找到//可以删除&#ext;}else {System.out.println("没有找到要删除的节点"+no+"号节点");}
}/*使用方式二,压入栈进行逆向打印*/
public static void reversePrint(HeroNode1 head){==null){return;//空链表不能打印}//创建一个栈,将各个节点压入栈中.Stack<HeroNode1> stack=new Stack<HeroNode1>();HeroNode1 cur&#;//先保存当前节点//将链表的所有节点压入栈中,while (cur!=null){stack.push(cur);cur&#;//cur后移,这样就可以压入下一个节点}//将栈中的节点进行打印,pop进行出栈while (stack.size()>0){System.out.println(stack.pop());//栈的特点是先进入后出}
}/*单链表的反转
* */public static void reversetList(HeroNode1 head){//如果当前列表为空,或者只有一个节点,无需反转,直接返回==null||==null){return;}//先定义一个辅助的指针(变量)HeroNode1 cur&#;HeroNode1 next=null;//指向当前节点(cur的节点,因为我们取出cur以后,我们没有指向下一个节点的标识)的下一个节点HeroNode1 reverseHead=new HeroNode1(0,"","");//变量原来的链表,每遍历一个节点,就将其取出,并方在新的链表reverseHead的最前端while (cur!=null){next&#;//这里next保存了当前节点的下一个节点,就是第一次因为我们一旦取出cur,那么这个节点就没有指向,我们之后找不到了&#;//将cur的下一个节点指向新的链表的头部,就是最前端=cur;//将这个cur连接到新的链表上cur=next;//让cur后移}//将这个指向实现单链表的反转&#;}/*查找单链表的倒数第k个节点
* 思路:
* 1.写一个方法接受这个这个head节点同时接受一个
* 2,index表示倒数第index节点
* 3,单链表不能逆向遍历,先把链表从头到尾遍历,得到链表的总的长度size
* 4,得到size后,我们从链表的第一个开始遍历,遍历size-index个,就得到了我们倒数第k个
* 5.如果找到了,就返回该节点,找不动返回空*/public static HeroNode1 findLastIndexNode(HeroNode1 head,int index){==null){return null;//此时链表为空,我们没有找到}//第一次遍历,我们得到链表的格式int size=getLength(head);//第二次遍历,我们遍历size-index个,就是我们倒数的第k个节点//先做一个数据的校验if(index<=0||index>size){return null;}//定义一个辅助变量,for  循环定位到倒数的indexHeroNode1 cur&#;for(int i=0;i<size-index;i++){cur&#;}return cur;}/*方法,获取到当链表节点的个数(如果是带头节点的链表,需要不统计头节点)*//**** @param head 链表的头节点* @return  返回的是有效节点的个数*/public static int getLength(HeroNode1 head){==null){//链表空return 0;}int length=0;//定义一个辅助变量HeroNode1 cur&#;//我们这里看出我们没有统计头节点while (cur!=null){length++;cur&#;//遍历}return length;}/*显示遍历*/public void show(){//先判断链表是否为空==null){System.out.println("链表为空");return;}//因为头节点不能动,因此我们需要一个辅助变量来遍历HeroNode1 temp&#;while (true){//判断是否到了链表的最后if(temp==null){break;}//输出节点的信息System.out.println(temp);//将temp后移,一定要后移,不然死循环temp&#;}}
}//定义一个HeroNode1,每个HeroNode1对象就是一个节点
class HeroNode1{public int no;public  String name;public String nickname;public HeroNode1 next;//指向下一个节点//构造器public  HeroNode1(int hNo,String hName ,String hNickname){=hNo;this.name=hName;this.nickname=hNickname;}//为了显示方便,我们重新toString方法
//toString这里我们不要打出next域,看起来清晰一些@Overridepublic String toString() {return "HeroNode1{" +"no=" + no +", name='" + name + ''' +", nickname='" + nickname + ''' +'}';}}