首页/JavaScript

数据结构与算法java，【尚硅谷】Java数据结构与算法详细整理笔记（附代码）更新中…………

 2023-09-24 阅读 29 评论 0

摘要：目录一、线性结构和非线性结构线性结构非线性结构二、稀疏 sparsearray数组1. 基本介绍2. 稀疏数组的处理方法3. 二维数组转稀疏数组的思路4. 稀硫数组转原始的二维数组的思路代码——稀疏数组三、队列1. 代码——模拟队列2. 模拟队列思路（1）问题分析并优化&#x

目录

  • 一、线性结构和非线性结构
    • 线性结构
    • 非线性结构
  • 二、稀疏 sparsearray数组
    • 1. 基本介绍
    • 2. 稀疏数组的处理方法
    • 3. 二维数组转稀疏数组的思路
    • 4. 稀硫数组转原始的二维数组的思路
    • 代码——稀疏数组
  • 三、队列
    • 1. 代码——模拟队列
    • 2. 模拟队列思路
      • （1）问题分析并优化
      • （2）使用数组模拟环形队列的思路分析
      • 代码——环形队列
  • 四、链表
    • 1. 链表介绍
    • 2. 单链表的创建示意图
      • 1) 无顺序添加(创建)
      • 2) 需要按照编号的顺序添加
    • 3. 代码——不考虑编号顺序的链表
    • 4. 代码——考虑编号顺序的链表
    • 5. 代码——单链表节点的修改
    • 6. 代码——单链表节点的删除和小结
    • 汇总代码
    • 7. 总结
    • 8. 单链表面试题

数据结构与算法java？

一、线性结构和非线性结构

数据结构包括:线性结构和非线性结构。

线性结构

  1. 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系
  2. 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的
  3. 链式存储的线性表称为链表,链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
  4. 线性结构常见的有：数组、队列、链表和栈

尚硅谷idea讲解笔记。顺序存储——数组
链式存储——链表

非线性结构

非线性结构包括：二维数组，多维数组，广义表，树结构，图结构

二、稀疏 sparsearray数组

五子棋：存盘退出、续上盘

1. 基本介绍

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

2. 稀疏数组的处理方法

  1. 记录数组一共有几行几列，有多少个不同的值
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

稀疏数组

3. 二维数组转稀疏数组的思路

  • 遍历原始的二维数组，得到有效数据的个数sum
  • 根据sum就可以创建稀硫数组 sparseArr int[sum+1][3]
  • 将二维数组的有效数据数据存入到稀疏数组

4. 稀硫数组转原始的二维数组的思路

  • 先读取稀硫数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chesser2 = int[11][11]
  • 在读取稀硫数组后几行的数据，并赋给原始的二维数组即可。

代码——稀疏数组

package com.blue;public class SparseArray {public static void main(String[] args) {// 创建一个原始的二维数组 11*11// 0: 表示没有棋子，1：表示黑子   2：表蓝子int chessArr[][] = new int[11][11];chessArr[1][2] = 1;chessArr[2][3] = 2;chessArr[4][5] = 2;// ===========输出原始的二维数组=====================System.out.println("输出原始的二维数组");for (int[] row:chessArr){for (int data:row){System.out.printf("%d\t", data);}System.out.println();}// =====================将二维数组转稀疏数组=================// 1.先遍历二维数组得到非 0数据的个数int sum = 0;for (int i = 0; i < 11; i++) {for (int j = 0; j < 11; j++) {if (chessArr[i][j] != 0){sum++;}}}// 2.创建对应的稀硫数组int sparseArr[][] = new int[sum + 1][3];//  给稀疏教组赋值sparseArr[0][0] = 11;sparseArr[0][1] = 11;sparseArr[0][2] = sum;// 遍历二维数组,将非0的值存放到 sparseArr 中int count = 0;for (int i = 0; i < 11; i++) {for (int j = 0; j < 11; j++) {if (chessArr[i][j] != 0){count++;sparseArr[count][0] = i;sparseArr[count][1] = j;sparseArr[count][2] = chessArr[i][j];}}}// 输出稀疏数组的形式System.out.println();System.out.println("得到稀疏数组为~~~~");for (int i = 0; i < sparseArr.length; i++) {System.out.printf("%d\t%d\t%d\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);}System.out.println();// =======================将稀疏数组--》恢复成原始的二维数组====================================//1. 先读取稀硫数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的 chessEr2=int[」1]//2. 在读取稀硫数组后几行的数据,并赋给原始的二维数组即可int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];for (int i = 1; i < sparseArr.length; i++) {chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];}//输出恢复后的二维数组System.out.println();System.out.println("恢复后的二维数组");for (int[] row:chessArr2){for (int data:row){System.out.printf("%d\t", data);}System.out.println();}}}

三、队列

  • 队列是一个有序列表，可以用数组或是链表来实现
  • 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
  • 示意图：(使用数组模拟队列示意图)
    在这里插入图片描述

数组模拟队列

  • 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。
  • 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变

1. 代码——模拟队列

package com.blue;import java.util.Scanner;public class ArrayQueueDemo {public static void main(String[] args) {// 测试一把// 创建一个队列ArrayQueue queue = new ArrayQueue(3);char key = ' ';  //接收用户输入Scanner scanner = new Scanner(System.in);boolean loop = true;// 输出一个菜单while (loop){System.out.println("s(show): 显示队列");System.out.println("e(exit):退出程序");System.out.println("a(add): 添加数据到队列");System.out.println("g(get): 从队列取出数据");System.out.println("h(head): 查看队列头的数据");key = scanner.next().charAt(0);switch (key){case 's':queue.showQueue();break;case 'a':System.out.println("输出一个数");int value = scanner.nextInt();queue.addQueue(value);break;case 'g':  // 取出数据try {int res = queue.getQueue();System.out.printf("取出的数据是‰d\n",res);}catch (Exception e){// TODO: handle exceptionSystem.out.println(e.getMessage());}break;case 'h': //查看队列头的数据try {int res = queue.headQueue();System.out.printf("队列头的数据是‰d\n",res);}catch (Exception e){// TODO: handle exceptionSystem.out.println(e.getMessage());}break;case 'e':  // 退出scanner.close();loop = false;break;default:break;}}System.out.println("程序退出");}}//================== 使用数组模拟队列-编写一个 ArrayQueue类==================================
class ArrayQueue{private int maxSize;  // 表示数组的最大容量private int front; // 队列头private int rear; //队列尾private int[] arr;  // 该数据用于存放数据,模拟队列// =======创建队列的构造器========================public ArrayQueue(int arrMaxSize){maxSize = arrMaxSize;arr = new int[maxSize];front = -1;  // 指向队列头部,分析出 front是指向队列头的前一个位置rear = -1; // 指向队列尾,指向队列尾的数据(即就是队列最后一个数据}// =====判断队列是否溝======public boolean isFull(){return rear==maxSize-1;}// =====判断队列是否为空======public boolean isEmpty(){return rear==front;}//======================添加数据到队列===================public void addQueue(int n){// 判断队列是否满if (isFull()){System.out.println("队列满,不能加入数据~");return;}rear++; //让 rear后移arr[rear] = n;}//=================获取队列的数据,出队列========================public int getQueue(){// 判断队列是否空if (isEmpty()){// 通过抛出异常throw new RuntimeException("队列空,不能取数据");}front++;  // front后移return arr[front];}// =====显示队列的所有数据=====public void showQueue(){// 遍历if (isEmpty()){System.out.println("队列空的,没有数据~~");return;}for (int i = 0; i < arr.length; i++) {System.out.printf("arr[%d]=%d\n",i,arr[i]);}}//====显示队列的头数据,注意不是取出数据===public  int headQueue(){// 判断if (isEmpty()){throw new RuntimeException("队列空的,没有数据~~");}return  arr[front + 1];}}输出：================================s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
s
队列空的,没有数据~~
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
a
输出一个数
20
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
s
arr[0]=20
arr[1]=0
arr[2]=0
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

2. 模拟队列思路

（1）问题分析并优化

  1. 数组使用一次就不能用，没有达到复用的效果
  2. 将这个数组使用算法，改进成一个环形的队列取模:%

（2）使用数组模拟环形队列的思路分析

  1. front变量的含义做一个调整: front就指向队列的第一个元素,也就是说 affront就是队列的第一个元素。—— front的初始值=0
  2. rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置因为希望空出一个空间做为约定。——rear的初始值=0
  3. 当队列满时，条件是 (rea+1)% max Size = front【满】
  4. 对队列为空的条件，rear= front 空
  5. 当我们这样分析，队列中有效的数据的个数 (rear+ maxsize - front)% maxsize

代码——环形队列

package com.blue;import java.util.Scanner;// 环形队列
public class CircleArrayQueueDemo {public static void main(String[] args) {// 测试一把System.out.println("测试数组模拟环形队列的案例~~");// 创建一个环形队列CircleArray queue = new CircleArray(4); // 说明设置4,其队列的有效数据最大是3char key = ' ';  //接收用户输入Scanner scanner = new Scanner(System.in);boolean loop = true;// 输出一个菜单while (loop){System.out.println("s(show): 显示队列");System.out.println("e(exit):退出程序");System.out.println("a(add): 添加数据到队列");System.out.println("g(get): 从队列取出数据");System.out.println("h(head): 查看队列头的数据");key = scanner.next().charAt(0);switch (key){case 's':queue.showQueue();break;case 'a':System.out.println("输出一个数");int value = scanner.nextInt();queue.addQueue(value);break;case 'g':  // 取出数据try {int res = queue.getQueue();System.out.printf("取出的数据是%d\n",res);}catch (Exception e){// TODO: handle exceptionSystem.out.println(e.getMessage());}break;case 'h': //查看队列头的数据try {int res = queue.headQueue();System.out.printf("队列头的数据是%d\n",res);}catch (Exception e){// TODO: handle exceptionSystem.out.println(e.getMessage());}break;case 'e':  // 退出scanner.close();loop = false;break;default:break;}}System.out.println("程序退出");}}class CircleArray{private int maxSize;  // 表示数组的最大容量// front变量的含义做一个调整: front就指向队列的第一个元素,也就是说 affront就是队列的第一个元素。—— front的初始值=0private int front; // 队列头// rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置因为希望空出一个空间做为约定。——rear的初始值=0private int rear; //队列尾private int[] arr;  // 该数据用于存放数据,模拟队列public CircleArray(int arrMaxSize){maxSize = arrMaxSize;arr = new int[maxSize];front = 0;rear = 0;}// =====判断队列是否溝======public boolean isFull(){return (rear + 1) % maxSize == front;}// =====判断队列是否为空======public boolean isEmpty(){return rear==front;}//=====添加数据到队列=============public void addQueue(int n){// 判断队列是否满if (isFull()){System.out.println("队列满,不能加入数据~");return;}//直接将数据加入arr[rear] = n;// 将rear后移,这里必须考虑取模rear = (rear + 1)% maxSize;}//=======获取队列的数据,出队列============public int getQueue(){// 判断队列是否空if (isEmpty()){// 通过抛出异常throw new RuntimeException("队列空,不能取数据");}// front后移/*这里需要分析出 front是指向队列的第一个元素1。先把 front对应的值保留到一个临时变量2.将 front后移3.将临时保存的变量返回*/int value = arr[front];front = (front + 1) % maxSize;return value;}// =======显示队列的所有数据========public void showQueue(){// 遍历if (isEmpty()){System.out.println("队列空的,没有数据~~");return;}// 思路:从 front开始遍历,遍历多少个元素// 动脑筋for (int i = front; i < front + size(); i++) {System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);}}// =========求出当前队列有效数据的个数=======public int size(){return (rear + maxSize - front) % maxSize;}//====显示队列的头数据,注意不是取出数据======public int headQueue(){// 判断if (isEmpty()){throw new RuntimeException("队列空的,没有数据~~");}return  arr[front];}}

====================输出为=========================
测试数组模拟环形队列的案例~~
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
a
输出一个数
1
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
a
输出一个数
2
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
a
输出一个数
3
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
s
arr[0]=1
arr[1]=2
arr[2]=3
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
h
队列头的数据是1
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据g
取出的数据是1
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
g
取出的数据是2
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
g
取出的数据是3
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
g
队列空,不能取数据
s(show): 显示队列
e(exit):退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

四、链表

1. 链表介绍

  • 链表是有序的列表，但是它在内存中是存储如下
    在这里插入图片描述

小结：

  1. 链表是以节点的方式来存储，是链式存储
  2. 每个节点包含data域，next域：指向下一个节点
  3. 如图：发现链表的各个节点不定是连续存放
  4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
  • 单链表(带头结点)逻辑结构示意图如下：
    在这里插入图片描述

2. 单链表的创建示意图

显示单向链表的分析

在这里插入图片描述

1) 无顺序添加(创建)

  1. 先创建一个head头节点，作用就是表示单链表的头
  2. 后面我们每添加一个节点，就直接加入到链表的最后

在这里插入图片描述

遍历:

  • 通过一个辅助变量，帮助遍历整个链表

2) 需要按照编号的顺序添加

  1. 首先找到新添加的节点的位置,是通过辅助变量(指针），通过遍历来搞定
  2. 新的节点.next = temp. next
  3. 将 temp.next = 新的节点
    在这里插入图片描述

3. 代码——不考虑编号顺序的链表

package com.blue.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(hero4);singleLinkedList.add(hero2);singleLinkedList.add(hero3);singleLinkedList.add(hero4);// 显示一把singleLinkedList.list();}}// ========================定义 SingleLinkedList 管理我们的英雄===============================
class SingleLinkedList{// 先初始化一个头节点,头节点不要动private HeroNode head  = new HeroNode(0,"","");//添加节点到单向链表/*思路,当不考虑编号顺序时1.找到当前链表的最后节点2.将最后这个节点的next指向新的节点*/public void add(HeroNode heroNode){// 因为head节点不能动,因此我们需要一个辅助遍历 tempHeroNode temp = head;// 遍历链表, 找到最后while (true){// 找到链表的最后if (temp.next==null){break;}// 如果没有找到最后,将将temp后移temp = temp.next;}// 当退出 whi1e循环时, temp就指向了链表的最后// 将最后这个节点的 next 指向新的节点temp.next = heroNode;}//显示链表[遍历]public void list(){// 判断链表是否为空if (head.next == null){System.out.println("链表为空");return;}// 因为头节点,不能动,因此我们需要一个辅助变量来遍历HeroNode temp = head.next;while (true){// 判断是否到链表最后if (temp == null){break;}// 输出节点的信息System.out.println(temp);// 将temp后移,一定小心temp = temp.next;}}}// =============================定义 HeroNode,每个 HeroNode对象就是一个节点=========================================
class HeroNode{public int no;  //public String name;public String nickname;public HeroNode next;  // 指向下一个节点// 构造器public HeroNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}// 为了显示方法,我们重新 tostring@Overridepublic String toString() {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='豹子头'}Process finished with exit code 0

4. 代码——考虑编号顺序的链表

package com.blue.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.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);// 显示一把singleLinkedList.list();}}// ========================定义 SingleLinkedList 管理我们的英雄===============================
class SingleLinkedList{// 先初始化一个头节点,头节点不要动private HeroNode head  = new HeroNode(0,"","");//+++++++++++++++添加节点到单向链表+++++++++++++++++++++++++++// 第二种方式在添加英雄时,根据排名将英雄插入到指定位置——// (如果有这个排名,则添加失败,并给出提示)public void addByOrder(HeroNode heroNode){// 因为头节点不能动, 因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置// 因为单链表, 因为我们找的 temp是位于添加位置的前一个节点, 否则插入不了HeroNode temp = head;boolean flag = false;  //标志添加的编号是否存在,默认为falsewhile (true){if (temp.next == null){ // 说明temp已经在链表的最后break; //}if (temp.next.no > heroNode.no){ //位置找到,就在temp的后面插入break;}else if (temp.next.no == heroNode.no){ //说明希望添加的 heroNode的编号已然存在flag = true; //说明编号存在break;}temp = temp.next; //后移,遍历当前链表}//判断 f1ag的值if (flag){ //不能添加,说明编号存在
//            System.out.printf("准备插入的英雄编号%d 已经存在了，不能加入\n",heroNode.no);System.out.println("准备插入的英雄编号"+heroNode.no+"已经存在了");}else {//插入到链表中heroNode.next = temp.next;temp.next = heroNode;}}//+++++++++++++++++++显示链表[遍历]+++++++++++++++++++++++++public void list(){// 判断链表是否为空if (head.next == null){System.out.println("链表为空");return;}// 因为头节点,不能动,因此我们需要一个辅助变量来遍历HeroNode temp = head.next;while (true){// 判断是否到链表最后if (temp == null){break;}// 输出节点的信息System.out.println(temp);// 将temp后移,一定小心temp = temp.next;}}}// ========================定义 HeroNode,每个 HeroNode对象就是一个节点=========================================
class HeroNode{public int no;  //public String name;public String nickname;public HeroNode next;  // 指向下一个节点// +++++++++++++++构造器 ++++++++++++++++++++++++public HeroNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}// ++++++++++为了显示方法,我们重新 tostring++++++++++++@Overridepublic String toString() {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='豹子头'}Process finished with exit code 0

5. 代码——单链表节点的修改

package com.blue.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.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);// 显示一把singleLinkedList.list();//测试修改节点的代码HeroNode newHeroNode = new HeroNode(2,"小卢","玉麒麟");singleLinkedList.update(newHeroNode);System.out.println("修改后的链表情况~~");// 显示一把singleLinkedList.list();}}// ========================定义 SingleLinkedList 管理我们的英雄===============================
class SingleLinkedList{// 先初始化一个头节点,头节点不要动private HeroNode head  = new HeroNode(0,"","");//+++++++++++++++添加节点到单向链表+++++++++++++++++++++++++++// 第二种方式在添加英雄时,根据排名将英雄插入到指定位置——// (如果有这个排名,则添加失败,并给出提示)public void addByOrder(HeroNode heroNode){// 因为头节点不能动, 因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置// 因为单链表, 因为我们找的 temp是位于添加位置的前一个节点, 否则插入不了HeroNode temp = head;boolean flag = false;  //标志添加的编号是否存在,默认为falsewhile (true){if (temp.next == null){ // 说明temp已经在链表的最后break; //}if (temp.next.no > heroNode.no){ //位置找到,就在temp的后面插入break;}else if (temp.next.no == heroNode.no){ //说明希望添加的 heroNode的编号已然存在flag = true; //说明编号存在break;}temp = temp.next; //后移,遍历当前链表}//判断 f1ag的值if (flag){ //不能添加,说明编号存在
//            System.out.printf("准备插入的英雄编号%d 已经存在了，不能加入\n",heroNode.no);System.out.println("准备插入的英雄编号"+heroNode.no+"已经存在了");}else {//插入到链表中,temp的后面heroNode.next = temp.next;temp.next = heroNode;}}//修改节点的信息,根据 no编号来修改,即 no编号不能改//说明//1.根据 newHeroNode 的 no来修改即可public void update(HeroNode newHeroNode){//if (head.next == null){System.out.println("链表为空~");return;}//找到需要修改的节点,根据no编号// 定义一个辅助变量HeroNode temp = head.next;boolean flag = false; //表示是否找到该节点while (true){if (temp == null) {break; //已经遍历完链表}if (temp.no == newHeroNode.no){//flag = true;break;}temp = temp.next;}//根据f1ag判断是否找到要修改的节点if (flag){temp.name = newHeroNode.name; // 名字temp.nickname = newHeroNode.nickname; //昵称}else {//没有找到System.out.println("没有找到编号"+newHeroNode.no+"的节点,不能修改");}}//+++++++++++++++++++显示链表[遍历]+++++++++++++++++++++++++public void list(){// 判断链表是否为空if (head.next == null){System.out.println("链表为空");return;}// 因为头节点,不能动,因此我们需要一个辅助变量来遍历HeroNode temp = head.next;while (true){// 判断是否到链表最后if (temp == null){break;}// 输出节点的信息System.out.println(temp);// 将temp后移,一定小心temp = temp.next;}}}// ========================定义 HeroNode,每个 HeroNode对象就是一个节点=========================================
class HeroNode{public int no;  //public String name;public String nickname;public HeroNode next;  // 指向下一个节点// +++++++++++++++构造器 ++++++++++++++++++++++++public HeroNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}// ++++++++++为了显示方法,我们重新 tostring++++++++++++@Overridepublic String toString() {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='豹子头'}
修改后的链表情况~~
HeroNode{no=1, name='宋江', nickname='及时雨'}
HeroNode{no=2, name='小卢', nickname='玉麒麟'}
HeroNode{no=3, name='吴用', nickname='智多星'}
HeroNode{no=4, name='林冲', nickname='豹子头'}Process finished with exit code 0

6. 代码——单链表节点的删除和小结

从单链表中删除一个节点的思路：

  1. 我们先找到需要删除的这个节点的前一个节点 temp
  2. temp.next=temp.next.next
  3. 被删除的节点,将不会有其它引用指向，会被垃圾回收机制回收
    //+++++++++++删除节点++++++++++++/*思路1. head不能动,因此我们需要一个 temp辅助节点找到待删除节点的前一个节点2. 说明我们在比较时,是temp,next,no和需要删除的节点的no比较*/public void del(int no){HeroNode temp = head;boolean flag = false;//标志是否找到待删除节点的while (true){if (temp.next == null){//已经到链表的最后break;}if (temp.next.no == no){// 找到的待删除节点的前一个节点 tempflag = true;break;}temp = temp.next;  //temp后移,遍历}//判断f1agif (flag){//可以删除temp.next = temp.next.next;}else {System.out.println("要删除的"+no+"节点不存在");}}

汇总代码

package com.blue.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(hero4);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);// 加入按照编号的顺序singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);// 显示一把singleLinkedList.list();//测试修改节点的代码HeroNode newHeroNode = new HeroNode(2,"小卢","玉麒麟");singleLinkedList.update(newHeroNode);System.out.println("修改后的链表情况~~");// 显示一把singleLinkedList.list();//删除节点singleLinkedList.del(1);System.out.println("删除后的链表情况~~");singleLinkedList.list();}}// ========================定义 SingleLinkedList 管理我们的英雄===============================
class SingleLinkedList{// 先初始化一个头节点,头节点不要动private HeroNode head  = new HeroNode(0,"","");//+++++++++++++++添加节点到单向链表+++++++++++++++++++++++++++/*思路,当不考虑编号顺序时1.找到当前链表的最后节点2.将最后这个节点的 next指向新的节点*/public void add(HeroNode heroNode){// 因为 head节点不能动,因此我们需要一个辅助遍历 tempHeroNode temp = head;// 遍历链表, 找到最后while (true){// 找到链表的最后if (temp.next==null){break;}// 如果没有找到最后,将将 temp后移temp = temp.next;}// 当退出 whi1e循环时, temp就指向了链表的最后// 将最后这个节点的 next 指向新的节点temp.next = heroNode;}// 第二种方式在添加英雄时,根据排名将英雄插入到指定位置——// (如果有这个排名,则添加失败,并给出提示)public void addByOrder(HeroNode heroNode){// 因为头节点不能动, 因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置// 因为单链表, 因为我们找的 temp是位于添加位置的前一个节点, 否则插入不了HeroNode temp = head;boolean flag = false;  //标志添加的编号是否存在,默认为falsewhile (true){if (temp.next == null){ // 说明temp已经在链表的最后break; //}if (temp.next.no > heroNode.no){ //位置找到,就在temp的后面插入break;}else if (temp.next.no == heroNode.no){ //说明希望添加的 heroNode的编号已然存在flag = true; //说明编号存在break;}temp = temp.next; //后移,遍历当前链表}//判断 f1ag的值if (flag){ //不能添加,说明编号存在
//            System.out.printf("准备插入的英雄编号%d 已经存在了，不能加入\n",heroNode.no);System.out.println("准备插入的英雄编号"+heroNode.no+"已经存在了");}else {//插入到链表中,temp的后面heroNode.next = temp.next;temp.next = heroNode;}}//+++++++++++++修改节点的信息,根据 no编号来修改,即 no编号不能改++++++++/*说明1.根据 newHeroNode 的 no来修改即可*/public void update(HeroNode newHeroNode){//if (head.next == null){System.out.println("链表为空~");return;}//找到需要修改的节点,根据no编号// 定义一个辅助变量HeroNode temp = head.next;boolean flag = false; //表示是否找到该节点while (true){if (temp == null) {break; //已经遍历完链表}if (temp.no == newHeroNode.no){//flag = true;break;}temp = temp.next;}//根据f1ag判断是否找到要修改的节点if (flag){temp.name = newHeroNode.name; // 名字temp.nickname = newHeroNode.nickname; //昵称}else {//没有找到System.out.println("没有找到编号"+newHeroNode.no+"的节点,不能修改");}}//+++++++++++删除节点++++++++++++/*思路1. head不能动,因此我们需要一个 temp辅助节点找到待删除节点的前一个节点2. 说明我们在比较时,是temp,next,no和需要删除的节点的no比较*/public void del(int no){HeroNode temp = head;boolean flag = false;//标志是否找到待删除节点的while (true){if (temp.next == null){//已经到链表的最后break;}if (temp.next.no == no){// 找到的待删除节点的前一个节点 tempflag = true;break;}temp = temp.next;  //temp后移,遍历}//判断f1agif (flag){//可以删除temp.next = temp.next.next;}else {System.out.println("要删除的"+no+"节点不存在");}}//+++++++++++++++++++显示链表[遍历]+++++++++++++++++++++++++public void list(){// 判断链表是否为空if (head.next == null){System.out.println("链表为空");return;}// 因为头节点,不能动,因此我们需要一个辅助变量来遍历HeroNode temp = head.next;while (true){// 判断是否到链表最后if (temp == null){break;}// 输出节点的信息System.out.println(temp);// 将temp后移,一定小心temp = temp.next;}}}// ========================定义 HeroNode,每个 HeroNode对象就是一个节点=========================================
class HeroNode{public int no;  //public String name;public String nickname;public HeroNode next;  // 指向下一个节点// +++++++++++++++构造器 ++++++++++++++++++++++++public HeroNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}// ++++++++++为了显示方法,我们重新 tostring++++++++++++@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}
}

7. 总结

  1. 链表是以节点的方式来存储是链式存储
  2. 每个节点包含data域、next域：指向下一个节点
  3. 链表的各个节点不一定是连续存储
  4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

8. 单链表面试题

版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接：https://808629.com/98639.html

上一篇：IPv6网络服务器，利用VSCode实现远程连接服务器并实时同步保存文件
下一篇：实现在线查看PDF文件
标签：数据结构与算法java尚硅谷idea讲解笔记尚硅谷mysql笔记算法和数据结构的关系java算法数据结构数据结构排序数据结构必背算法
数据结构与算法java

发表评论:

最新文章
阅读排行
猜你喜欢
热门标签

本站为非赢利网站，部分文章来源或改编自互联网及其他公众平台，主要目的在于分享信息，版权归原作者所有，内容仅供读者参考，如有侵权请联系我们删除！

Copyright © 2022 86后生记录生活 Inc. 保留所有权利。

底部版权信息