单链表的插入
实现思路如下：
Java中的插入和C语言中的插入思路是一样的
都是改变指针的指向，Java中没有被引用的对象会被垃圾回收
删除的思路
单链表的插入与删除
package com.caq.linkedlist; /** * @Date 2021/12/8 17:11 * @Version 1.0 */ public class SingleLinkedListDemo { public static void main(String[] args) { //进行测试 HeroNode hero1 = new HeroNode(1, "宋江", "及时雨"); HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吴用", "智多星"); //创建要给链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); //按照编号的顺序 // singleLinkedList.add(hero1); // singleLinkedList.add(hero2); // singleLinkedList.add(hero3); //不按照编号的顺序 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero3); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero2); //显示 singleLinkedList.list(); System.out.println("***************"); //修改节点的代码 HeroNode heroNode = new HeroNode(2, "库里", "萌神"); singleLinkedList.update(heroNode); singleLinkedList.list(); System.out.println("***************"); //删除节点 singleLinkedList.delete(2); singleLinkedList.delete(2);//没有找到要删除的结点2! singleLinkedList.delete(1); singleLinkedList.delete(3);//没有找到要删除的结点3! singleLinkedList.delete(3);//链表为空 singleLinkedList.list(); } } //定义SingleLinkedList 管理英雄 class SingleLinkedList { //先初始化一个头结点，头结点不要动，不存放具体的数据 private HeroNode head = new HeroNode(0, "", ""); //添加节点到单向链表 public void add(HeroNode heroNode) { HeroNode temp = head; //遍历链表，找到最后 while (true) { //找到链表的最后 if (temp.next == null) { break; } //如果没有找到最后，就讲temp后移 /**这里的next是对象变量 * 什么是对象变量呢？在Java核心卷1中97页提出，对象变量引用新构造的对象 * 我们学过C语言可以知道，这个对象变量就类似与指针指向我们的对象 * 再去看上面的程序temp.next == null代表head结点后面没有新的结点了 * 因为next变量（可以理解为c语言的指针）在堆中没有指向任何数据，因此可以判断是尾结点 */ temp = temp.next;//将我们的这个临时对象变量后移指向头接点的下一个元素 } //当退出while循环时，temp就指向了链表的最后 //将最后这个节点的next指向了新的节点 temp.next = heroNode;//把这个对象变量指向heroNode也就是我们的新节点 } //第二种方式添加，我们按顺序来添加根据排名 public void addByOrder(HeroNode heroNode) { //头结点不动，仍然通过temp来操作 HeroNode temp = head; boolean flag = false; while (true) { //这个判断的是head后面没有元素，直接添加 if (temp.next == null) { break; } //有元素的时候，比较number大小， if (temp.next.number > heroNode.number) {//位置找到，就在temp的后面插入（temp.next就是temp的后面） break; } else if (temp.next.number == heroNode.number) { flag = true; //说明编号存在 break; } temp = temp.next; } //判断flag的值 if (flag) { System.out.println("不能插入，因为" + heroNode.number + "已经存在"); } else { //可以插入 heroNode.next = temp.next; temp.next = heroNode; } } //修改节点的信息，根据number编号来修改，既number编号不能改 public void update(HeroNode heroNode) { HeroNode temp = head.next; boolean flag = false; while (true) { if (temp.next == null) { break; } //匹配节点 if (temp.number == heroNode.number) { flag = true; break; } temp = temp.next; } if (flag) { temp.name = heroNode.name; temp.nickname = heroNode.nickname; } else { System.out.println("没有找到编号为" + heroNode.number + ""); } } //删除节点 public void delete(int number) { HeroNode temp = head; boolean flag = false; //是否找到 while (true) { if (temp.next == null) { //到最后了 break; } if (temp.next.number == number) { flag = true; break; } temp = temp.next; //temp后移，遍历链表 } //被删除的结点，不会有其他引用指向，会被垃圾回收机制回收 //这和c语言一模一样啊！ if (flag) { temp.next = temp.next.next; }else { System.out.println("没有找到要删除的结点"+number+"!"); } } //显示链表[遍历] public void list() { if (head.next == null) { System.out.println("链表为空"); return; } //因为头结点，不能动，我们需要一个辅助变量来遍历 /** 这个遍历的时候容易出错，我们自己学习的时候可以多用debug来进行学习 我们看67行，我们搞了一个辅助变量temp因为头结点不能动，我们让temp = 头结点的下一个对象 好，我们进入while循环，直接打印temp的信息，因为我们上边重写了toString方法可以直接打印 之后！我们将temp在后移，此时的temp已经是头结点的下一个对象了，之后在后移这样就可以实现 打印链表中的所有对象了！ */ HeroNode temp = head.next; while (true) { //判断是否到链表最后 if (temp == null) { break; } //输出节点信息 System.out.println(temp); //将next后移，一定小心 temp = temp.next; } } } //定义HereNode,每一个HeroNode对象就是一个节点 class HeroNode { public int number; public String name; public String nickname; public HeroNode next; //指向下一个节点 //构造器 public HeroNode(int number, String name, String nickname) { this.number = number; this.name = name; this.nickname = nickname; } @Override public String toString() { return "HeroNode{" + "number=" + number + ", name='" + name + '\'' + ", nickname='" + nickname + '\'' + " }"; } }
输出结果
不能插入，因为2已经存在 HeroNode{number=1, name='宋江', nickname='及时雨' } HeroNode{number=2, name='卢俊义', nickname='玉麒麟' } HeroNode{number=3, name='吴用', nickname='智多星' } *************** HeroNode{number=1, name='宋江', nickname='及时雨' } HeroNode{number=2, name='库里', nickname='萌神' } HeroNode{number=3, name='吴用', nickname='智多星' } *************** 没有找到要删除的结点2! 没有找到要删除的结点3! 链表为空
单链表新浪面试题
思路分析
定义一个辅助变量和一个计数器变量
让辅助变量一直往后指，只要不为空，计数器就加+1
最后return计数器的值
//显示有效结点的个数（头结点不统计） public static int getLength(HeroNode head) { if (head.next == null) {//证明是空链表 return 0; } int len = 0; HeroNode temp = head.next; while (temp != null) { len++; temp = temp.next; //向后遍历 } return len; }
输出结果
HeroNode{number=1, name='宋江', nickname='及时雨' } HeroNode{number=2, name='卢俊义', nickname='玉麒麟' } HeroNode{number=3, name='吴用', nickname='智多星' }
查找单链表中的倒数第k个结点
思路分析
1.编写一个方法，接受head节点，同时接收一个index
2.index表示是倒数第index个结点
3.先把链表从头到尾遍历，得到链表的总长度getLength
4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
singleLinkedList.list(); System.out.println(getLength(singleLinkedList.getHead())); //查看倒数第一个 System.out.println(findLastIndexNode(singleLinkedList.getHead(),1)); //查看倒数第二个 System.out.println(findLastIndexNode(singleLinkedList.getHead(),2)); public static HeroNode findLastIndexNode(HeroNode head, int index) { if (head.next == null) { return null;//没有找到 } //第一个遍历得到的链表的有效长度 int size = getLength(head); //第二个遍历size-index 位置，就是我们倒数的第k个结点 if (index <= 0 || index > size) { return null; } //定义辅助变量，for循环定位到倒数的i //比如我们要找倒数第二个，我们的有效数据是3个的话size-index = 1,也就是往后移动一位即可 HeroNode temp = head.next; for (int i =0;i<size-index;i++){ temp = temp.next; } return temp; }
输出结果为HeroNode{number=1, name='宋江', nickname='及时雨' }HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }HeroNode{number=3, name='吴用', nickname='智多星' }3HeroNode{number=3, name='吴用', nickname='智多星' }HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }
1
单链表的反转
思路分析
1.先定义一个节点reverseHead = new HeroNode();
2.从头到尾遍历原来的链表，每遍历出来一个节点，就将其取出，并放在新的链表的最前端
3.原来的链表的head.next = reverseHead.next
/** * 单链表的反转 */public static void reversetList(HeroNode head) { //如果当前链表为空，或者只有一个节点，无需反转 if (head.next == null || head.next.next == null) { return; } //定义一个辅助的指针（变量）,帮助我们遍历原来的链表 HeroNode temp = head.next; HeroNode next = null;//指向当前节点的下一个节点 HeroNode reverseHead = new HeroNode(0, "", ""); //遍历原来的链表，并从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新链表reverseHead的最前端 while (temp != null) { next = temp.next;//先暂时保持当前节点的下一个节点。因为后面需要使用 temp.next = reverseHead.next;// reverseHead.next = temp;//将temp连接到新的链表上 temp = next;//让temp后移 } //将head.next指向reverseHead.next,实现单链表的反转 head.next = reverseHead.next;}
输出结果
//反转单链表System.out.println("*********");reversetList(singleLinkedList.getHead());singleLinkedList.list();HeroNode{number=1, name='宋江', nickname='及时雨' }HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }HeroNode{number=3, name='吴用', nickname='智多星' }*********HeroNode{number=3, name='吴用', nickname='智多星' }HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }HeroNode{number=1, name='宋江', nickname='及时雨' }
逆序打印链表
思路分析
不改变链表的结构情况下，利用栈先进后出的特性，将对象全放到栈里，最后在一个一个的弹出来
//通过栈来实现链表的反转打印public static void stacktest(HeroNode head){ if (head.next ==null){ return; } //创建一个栈，将各个结点压入栈 Stack<HeroNode> stack = new Stack<>(); HeroNode temp = head.next; //将链表的所有节点压入栈 while (temp != null){ stack.push(temp); temp = temp.next;//temp后移，这样就可以压入下一个节点 } //将栈中的结点进行打印，pop出栈 while (stack.size() > 0){ System.out.println(stack.pop()); }}
输出结果
HeroNode{number=3, name='吴用', nickname='智多星' }HeroNode{number=2, name='卢俊义', nickname='玉麒麟' }HeroNode{number=1, name='宋江', nickname='及时雨' }
双向链表
上图是C语言中的双向链表插入元素 的时候指针的变化
同样适用于我们Java中！
今天算是深刻体会到了C语言的重要性
上面的标注中，有个重要的点是
我们是把p赋值给s的前驱或者说是s的前驱指向了p
之后我们只能说是把p->next赋值给了s->next（不能说把s->next赋值给p->next）
双向链表的添加节点
