1. 什么是单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素

结点结构 ┌───┬───┐ │data │next │ └───┴───┘ data域–存放结点值的数据域 next域–存放结点的直接后继的地址（位置）的指针域（链域） 链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked List）。

头指针head和终端结点 单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。 终端结点无后继，故终端结点的指针域为空，即NULL。

注意事项：

我们认为当节点的next域为空时，单链表就结束了head节点是不允许被改变的，所以我们如果需要使用，就需要使用一个临时变量来代替head头结点

2.创建一个单链表的节点的类(注意，这里不是单链表，这里指的是他的每一个节点)

no name nickName 指的就是节点的data域next我们乍一看这是一个对象，但是他指向了我们的下一个节点的位置，下面我会向大家解释 //定义一个HeroNode，每个HeroNode对象就是一个节点 class HerNode{ public int no; //编号 public String name; // 姓名 public String nickName; // 外号 public HerNode next;//指向下一个节点 //构造器 public HerNode(int no, String name, String nickName) { this.no = no; this.name = name; this.nickName = nickName; } //为了显示方改变我们重写toString方法 @Override public String toString() { return "HerNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } }

3.创建一个管理整合类，把节点整合为单链表

3.1将节点插入到单链表中，按照代码顺序插入

头结点永远不能动，所以我们需要创建一个临时变量 //定义SingleLinkedListDemo 来把我们的节点变成单链表 class SingleLinkedListDemo{ //先初始化一个头结点，头结点不要动 private HerNode head = new HerNode(0,"","");//不存放具体的数据 //添加节点到单向链表 //思路：当不考虑编号顺序时 //1. 找到当前链表的最后一个节点 //2. 将最后一个节点的next域，指向新的节点 public void add(HerNode herNode){ //因为head节点不能动，因此我们需要一个辅助变量temp HerNode temp = head; //遍历链表，找到最后 while (true){ //找到链表的最后，才能跳出循环 if (temp.next==null){ break; } //如果没有找到最后,就将temp后移 temp = temp.next; } //当退出while循环时，temp就指向了链表的最后，然后我们把节点插入到他的next对象中，就实现了链表的插入 temp.next = herNode; } }

3.2创建单链表的遍历方法

这里的next指的是对象 class SingleLinkedListDemo{ //显示链表【遍历】 public void list(){ //判断链表是否为空 if (head.next==null){ //这里的head指的是初始化的头结点 System.out.println("链表为空"); return; } //因为头结点不能动，因此我们需要一个辅助变量来遍历 HerNode temp = head.next; while (true){ //判断是否到最后了 if (temp == null){ break; } //输出节点的信息 System.out.println(temp); //将temp的后移,一定小心 temp = temp.next; } } }

3.3创建单链表并打印

public class SingleLinkedList { public static void main(String[] args) { //测试 //创建节点 HerNode her6= new HerNode(6, "鲁智深", "花和尚"); HerNode her2= new HerNode(2, "卢俊义", "玉麒麟"); HerNode her7= new HerNode(7, "李颖", "天府行"); HerNode her8= new HerNode(8, "行者", "武松"); //创建一个链表 SingleLinkedListDemo singleLinkedList = new SingleLinkedListDemo(); //把节点按顺序插入 singleLinkedList.add(her6); singleLinkedList.add(her2); singleLinkedList.add(her7); singleLinkedList.add(her8); //打印单链表 singleLinkedList.list(); } }

这里我们发现了一个问题，他的链表插入是按照我们代码的顺序插入的，并不是按照我们编号的大小进行排序的，我希望我不按照代码顺序插入，而是编号排序

3.4将节点插入到单链表中，按照no顺序插入

//定义SingleLinkedListDemo 来把我们的节点变成单链表 class SingleLinkedListDemo{ //第二种方式再添加英雄的时候，根据排名将英雄插入到指定位置 //如果有这个排名，则添加失败，并给出提示 public void add2(HerNode herNode){ //因为头结点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置 //因为单链表，因此我们找的temp位于添加位置的前一个节点，否则插入不了 HerNode temp = head; boolean flag = false; //标识添加的编号是否存在，默认为false while (true){ if(temp.next==null){ //说明temp在链表的最后 break; } if (temp.next.no>herNode.no){ //位置找到了，就在这个temp的后面插入 break; }else if (temp.next.no==herNode.no){ //说明天添加的hero存在，不能添加 flag = true; break; } temp = temp.next; //后移，遍历当前的链表 } //判断flag的值 if (flag){ //不能添加说明有了这个编号存在 System.out.printf("准备插入的编号 %d 已经存在，无法添加\n",herNode.no); }else { //插入到链表中，temp的后面 herNode.next = temp.next; temp.next = herNode; } } }

3.5创建单链表并打印

public class SingleLinkedList { public static void main(String[] args) { //测试 //创建节点 HerNode her6= new HerNode(6, "鲁智深", "花和尚"); HerNode her2= new HerNode(2, "卢俊义", "玉麒麟"); HerNode her7= new HerNode(7, "李颖", "天府行"); HerNode her8= new HerNode(8, "行者", "武松"); //创建一个链表 SingleLinkedListDemo singleLinkedList = new SingleLinkedListDemo(); //把节点按顺序插入 singleLinkedList.add2(her6); singleLinkedList.add2(her2); singleLinkedList.add2(her7); singleLinkedList.add2(her8); //打印单链表 singleLinkedList.list(); } }

3.6修改单链表的某个节点

//定义SingleLinkedListDemo 来把我们的节点变成单链表 class SingleLinkedListDemo{ //修改节点的信息，根据no编号来修改，即no不能改 //根据 newHeroNode的no来修改即可 public void update(HerNode newHerNode){ //判断是否为空 if (head.next == null){ System.out.println("链表为空"); return; } //找到需要修改的节点，根据no来找 //定义一个辅助变量 HerNode temp = head.next; boolean flag = false; //表示是否找到该节点 while(true){ if (temp==null){ break;//表示链表已经遍历完了 } if (temp.no==newHerNode.no){ //找到了 flag = true; break; } temp = temp.next; } //根据flag，判断是否找到要修改的节点 if (flag = true){ temp.name = newHerNode.name; temp.nickName = newHerNode.nickName; }else { //没有这个节点 System.out.printf("没有找到编号等于%d的节点，不能修改\n",newHerNode.no); } } }

3.7修改单链表的某个节点数据

//测试修改节点的代码 System.out.println("修改节点信息后"); HerNode newHer2= new HerNode(2, "卢俊义2", "玉麒麟2"); singleLinkedList2.update(newHer2); singleLinkedList2.list(); //修改节点后 System.out.println("=======================================");

3.8删除单链表的节点

//定义SingleLinkedListDemo 来把我们的节点变成单链表 class SingleLinkedListDemo{ //删除节点 //我们需要先找到删除节点的前一个节点 //temp.next=temp.next.next即可，这就删除了 //被删除的节点，将会被垃圾回收机制回收 public void delete(int no){ //因为头结点不能动，因此我们需要一个辅助变量来遍历 HerNode temp = head; boolean flag = false; //标志是否找到删除节点的前一个节点 while (true){ if (temp.next==null){ //已经到链表的最后了 break; } if (temp.next.no==no){ //找到了需要删除的节点的前一个节点 flag = true; break; } temp = temp.next; //temp后移 } if (flag==true){ //说明找到 temp.next = temp.next.next; }else{ //要删除的节点，不存在无法删除 System.out.printf("要删除的节点%d不存在\n",no); } } }

3.9删除单链表的节点

//删除一个节点 singleLinkedList2.delete(1); //删除后 singleLinkedList2.list(); System.out.println("=======================================");

3.10统计单链表的节点个数（除去+头结点）

public HerNode getHead() { return head; } /* * 获取到单链表的节点的个数（如果是带头结点的链表，需要不统计头结点） * */ public int getLength(HerNode head){ if (head.next==null){ //这是一个带头结点的空链表 return 0; } int length = 0 ; //定义一个辅助变量 HerNode cur = head.next; while(cur != null){ length++; cur = cur.next; //遍历 } return length; }

3.11测试统计单链表的节点个数（除去+头结点）

//测试单链表的节点有效个数 HerNode head = singleLinkedList.getHead(); System.out.println("有效的节点个数"+singleLinkedList.getLength(head)); System.out.println("==========================");

3.12得到单链表的倒数第k个节点的数据

//查找单链表的倒数第k个节点 //思路 //1.编写一个方法，接收一个head节点，同时接收一个index //2.index表示倒数第index个节点 //3.先把链表从头到尾遍历一下，得到链表的总的长度 //4.我们在得到长度length后，我们从链表的第一个开始遍历length-index个，就得到了 //5.如果找到了，则返回该节点，否则返回null public HerNode findLastIndexNode(HerNode head,int index){ //判断链表为空，返回null if (head.next==null){ return null;//没有找到 } //第一次遍历得到链表的长度，节点的有效个数 int length = getLength(head); //第二次遍历 length-index 位置，这就是我们倒数的第k个节点 //先做一个index效验 if (index <= 0 || index > length){ return null; } //定义一个辅助变量 HerNode temp = head.next; for (int i = 0 ;i<length-index;i++){ //for循环定位倒数的index temp=temp.next; } return temp; }

3.13得到单链表的倒数第1个节点的数据

//测试一下是否得到了倒数第k个节点 HerNode lastIndexNode = singleLinkedList.findLastIndexNode(head, 1); System.out.println("倒数节点的数据为:"+lastIndexNode);

3.14翻转单链表

//将单链表实现翻转 public void reverseList(HerNode head){ //如果当前链表为空，或者只有一个节点，就无需翻转，直接返回 if(head.next==null||head.next.next==null){ return; } //定义一个辅助的变量，帮助我们遍历原来的链表 HerNode cur = head.next; HerNode next = null ;//指向当前节点的下一个节点 HerNode reverseHead = new HerNode(0,"",""); //遍历原来的链表 //每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前面 while (cur!=null){ next = cur.next;//先展示保存当前节点的下一个节点，因为后面需要使用 cur.next = reverseHead.next; //将cur的下一个节点，指向新链表的最前端 reverseHead.next = cur; //将cur连接到新的链表上 cur = next; //让cur后移 } //将head.next指向reverseHead，实现单链表的翻转 head.next=reverseHead.next; }

3.15测试翻转单链表

System.out.println("=========================="); System.out.println("翻转单链表"); singleLinkedList.reverseList(head); singleLinkedList.list();

4 整合代码

外加一个使用栈来翻转单链表。这样不会破坏原有链表的结构 import java.util.Stack; public class SingleLinkedList { public static void main(String[] args) { //测试 //创建节点 HerNode her1= new HerNode(1, "鲁智深", "花和尚"); HerNode her2= new HerNode(2, "卢俊义", "玉麒麟"); HerNode her3= new HerNode(3, "李颖", "天府行"); HerNode her4= new HerNode(4, "行者", "武松"); HerNode her8= new HerNode(8, "鲁智深", "花和尚"); HerNode her5= new HerNode(5, "卢俊义", "玉麒麟"); HerNode her6= new HerNode(6, "李颖", "天府行"); HerNode her7= new HerNode(7, "行者", "武松"); //创建一个链表 SingleLinkedListDemo singleLinkedList = new SingleLinkedListDemo(); //加入 //顺序插入 singleLinkedList.add(her1); singleLinkedList.add(her4); singleLinkedList.add(her2); singleLinkedList.add(her3); //修改前 System.out.println("修改前"); singleLinkedList.list(); System.out.println("======================================="); //创建一个排序的链表 SingleLinkedListDemo singleLinkedList2 = new SingleLinkedListDemo(); //按编号插入，在内存里面就解决问题了，比在数据库里面排序要快得多 singleLinkedList2.add2(her8); singleLinkedList2.add2(her5); singleLinkedList2.add2(her6); singleLinkedList2.add2(her7); //修改后 System.out.println("修改后"); singleLinkedList2.list(); System.out.println("======================================="); //测试修改节点的代码 System.out.println("修改节点信息后"); HerNode newHer2= new HerNode(5, "卢俊义2", "玉麒麟2"); singleLinkedList2.update(newHer2); singleLinkedList2.list(); //修改节点后 System.out.println("======================================="); //删除一个节点 System.out.println("删除节点后"); singleLinkedList.delete(1); //删除后 singleLinkedList.list(); System.out.println("======================================="); //测试单链表的节点有效个数 HerNode head = singleLinkedList.getHead(); System.out.println("有效的节点个数"+singleLinkedList.getLength(head)); System.out.println("=========================="); //测试一下是否得到了倒数第k个节点 HerNode lastIndexNode = singleLinkedList.findLastIndexNode(head, 1); System.out.println("倒数节点的数据为:"+lastIndexNode); System.out.println("=========================="); System.out.println("翻转单链表"); singleLinkedList.reverseList(head); singleLinkedList.list(); //测试用栈的方式，来翻转，因为他不会破坏链表本身的结构 System.out.println("=========================="); System.out.println("使用stack的方式逆序打印"); singleLinkedList.reverseStack(head); } } //定义SingleLinkedListDemo 来把我们的节点变成单链表 class SingleLinkedListDemo{ //先初始化一个头结点，头结点不要动 private HerNode head = new HerNode(0,"","");//不存放具体的数据 public HerNode getHead() { return head; } //添加节点到单向链表 //思路：当不考虑编号顺序时 //1. 找到当前链表的最后一个节点 //2. 将最后一个节点的next域，指向新的节点 public void add(HerNode herNode){ //因为head节点不能动，因此我们需要一个辅助变量temp HerNode temp = head; //遍历链表，找到最后 while (true){ //找到链表的最后 if (temp.next==null){ break; } //如果没有找到最后,就将temp后移 temp = temp.next; } //当退出while循环时，temp就指向了链表的最后 temp.next = herNode; } //第二种方式再添加英雄的时候，根据排名将英雄插入到指定位置 //如果有这个排名，则添加失败，并给出提示 public void add2(HerNode herNode){ //因为头结点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置 //因为单链表，因此我们找的temp位于添加位置的前一个节点，否则插入不了 HerNode temp = head; boolean flag = false; //标识添加的编号是否存在，默认为false while (true){ if(temp.next==null){ //说明temp在链表的最后 break; } if (temp.next.no>herNode.no){ //位置找到了，就在这个temp的后面插入 break; }else if (temp.next.no==herNode.no){ //说明天添加的hero存在，不能添加 flag = true; break; } temp = temp.next; //后移，遍历当前的链表 } //判断flag的值 if (flag){ //不能添加说明有了这个编号存在 System.out.printf("准备插入的编号 %d 已经存在，无法添加\n",herNode.no); }else { //插入到链表中，temp的后面 herNode.next = temp.next; temp.next = herNode; } } //修改节点的信息，根据no编号来修改，即no不能改 //根据 newHeroNode的no来修改即可 public void update(HerNode newHerNode){ //判断是否为空 if (head.next == null){ System.out.println("链表为空"); return; } //找到需要修改的节点，根据no来找 //定义一个辅助变量 HerNode temp = head.next; boolean flag = false; //表示是否找到该节点 while(true){ if (temp==null){ break;//表示链表已经遍历完了 } if (temp.no==newHerNode.no){ //找到了 flag = true; break; } temp = temp.next; } //根据flag，判断是否找到要修改的节点 if (flag = true){ temp.name = newHerNode.name; temp.nickName = newHerNode.nickName; }else { //没有这个节点 System.out.printf("没有找到编号等于%d的节点，不能修改\n",newHerNode.no); } } //删除节点 //我们需要先找到删除节点的前一个节点 //temp.next=temp.next.next即可，这就删除了 //被删除的节点，将会被垃圾回收机制回收 public void delete(int no){ //因为头结点不能动，因此我们需要一个辅助变量来遍历 HerNode temp = head; boolean flag = false; //标志是否找到删除节点的前一个节点 while (true){ if (temp.next==null){ //已经到链表的最后了 break; } if (temp.next.no==no){ //找到了需要删除的节点的前一个节点 flag = true; break; } temp = temp.next; //temp后移 } if (flag==true){ //说明找到 temp.next = temp.next.next; }else{ //要删除的节点，不存在无法删除 System.out.printf("要删除的节点%d不存在\n",no); } } //显示链表【遍历】 public void list(){ //判断链表是否为空 if (head.next==null){ System.out.println("链表为空"); return; } //因为头结点不能动，因此我们需要一个辅助变量来遍历 HerNode temp = head.next; while (true){ //判断是否到最后了 if (temp == null){ break; } //输出节点的信息 System.out.println(temp); //将temp的后移,一定小心 temp = temp.next; } } /* * 获取到单链表的节点的个数（如果是带头结点的链表，需要不统计头结点） * */ public int getLength(HerNode head){ if (head.next==null){ //这是一个带头结点的空链表 return 0; } int length = 0 ; //定义一个辅助变量 HerNode cur = head.next; while(cur != null){ length++; cur = cur.next; //遍历 } return length; } //查找单链表的倒数第k个节点 //思路 //1.编写一个方法，接收一个head节点，同时接收一个index //2.index表示倒数第index个节点 //3.先把链表从头到尾遍历一下，得到链表的总的长度 //4.我们在得到长度length后，我们从链表的第一个开始遍历length-index个，就得到了 //5.如果找到了，则返回该节点，否则返回null public HerNode findLastIndexNode(HerNode head,int index){ //判断链表为空，返回null if (head.next==null){ return null;//没有找到 } //第一次遍历得到链表的长度，节点的有效个数 int length = getLength(head); //第二次遍历 length-index 位置，这就是我们倒数的第k个节点 //先做一个index效验 if (index <= 0 || index > length){ return null; } //定义一个辅助变量 HerNode temp = head.next; for (int i = 0 ;i<length-index;i++){ //for循环定位倒数的index temp=temp.next; } return temp; } //将单链表实现翻转 public void reverseList(HerNode head){ //如果当前链表为空，或者只有一个节点，就无需翻转，直接返回 if(head.next==null||head.next.next==null){ return; } //定义一个辅助的变量，帮助我们遍历原来的链表 HerNode cur = head.next; HerNode next = null ;//指向当前节点的下一个节点 HerNode reverseHead = new HerNode(0,"",""); //遍历原来的链表 //每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前面 while (cur!=null){ next = cur.next;//先展示保存当前节点的下一个节点，因为后面需要使用 cur.next = reverseHead.next; //将cur的下一个节点，指向新链表的最前端 reverseHead.next = cur; //将cur连接到新的链表上 cur = next; //让cur后移 } //将head.next指向reverseHead，实现单链表的翻转 head.next=reverseHead.next; } //使用方式二，用栈来实现翻转，但是不破坏链表的原有结构 public void reverseStack(HerNode head){ if (head.next==null){ //空链表无法打印 return; } //创建一个栈，将各个节点压入栈中 Stack<HerNode> stack = new Stack<HerNode>(); HerNode cur = head.next; //将链表的所有节点压入栈中 while (cur!=null){ stack.push(cur); cur = cur.next;//cur后移，这样就可以压入下一个节点 } //将栈中的节点打印出来pop while (stack.size()>0){ System.out.println(stack.pop()); } } } //定义一个HeroNode，每个HeroNode对象就是一个节点 class HerNode{ public int no; public String name; public String nickName; public HerNode next;//指向下一个节点 //构造器 public HerNode(int no, String name, String nickName) { this.no = no; this.name = name; this.nickName = nickName; } //为了显示方改变我们重写toString方法 @Override public String toString() { return "HerNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } }