待解决的问题
- 单向环形链表
- 单链表的反转
-
数据结构与算法概述
什么是数据结构？
数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据
数据结构分类
逻辑结构
逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系进行分类。
集合结构：集合结构中的数据元素除了属于同一个集合外，他们之间没有其他任何的关系。
- 线性结构：线性结构中的数据元素之间存在一对一的关系。
- 树型结构：树型结构中的数据元素之间存在一对多的层次关系。
- 图型结构：图形结构的数据元素是多对多的关系。
物理结构/存储结构
逻辑结构在计算机中真正的表示方式（又称为映像）称为物理结构，也可以叫做存储结构。
- 顺序存储结构：把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的。例如数组就是顺序存储结构。
- 链式存储结构：把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此在链式存储结构中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。
什么是算法？
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法解决问题的策略机制。
算法分析
算法的时间复杂度分析
- 事后分析估算法：在计算机程序编写后，利用计算机计时器对不同算法编写的程序运行时间进行比较，从而确定算法效率的高低。这种方式有很大的缺陷，写了半天发现这个算法不好，非常浪费时间，而且不同的测试环境的差别导致测试的结果差异也很大。
- 事前分析估算法：在计算机程序编写前，依据统计方法对算法进行估算。
一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素：
- 算法采用的策略和方案
- 编译产生的代码质量
- 问题的输入规模
- 机器执行指令的速度
抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。如果算法固定，那么该算法的执行时间就只和问题的输入规模有关系了。
算法的时间复杂度分析规则
- 算法函数中的常数可以忽略（2n^3+3n+1）
- 算法函数中最高次幂的常数因子可以忽略（2n^3+3n+1）
算法函数中最高次幂越小，算法效率越高。（2n^3+3n+1）
大O记法
前提：执行次数=执行时间
⭐规则：用 常数1 取代运行时间中的所有加法常数。
- 在第一步的基础上，只保留高阶项。
如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数。
常见的大O阶
线性阶 O(n)
一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长。
- 平方阶 O(n2)
一般嵌套循环属于这种时间复杂度。
- 立方阶 O(n3)
一般三层嵌套循环属于这种时间复杂度。
- 对数阶 O(logn)
对数阶，由于随着输入规模n的增大，不管底数为多少，他们的增长趋势是一样的，所以我们会忽略底数。
- 常数阶 O(1)
一般不涉及循环操作的都是常数阶，因为它不会随着n的增长而增加操作次数。
总结：
复杂度从低→高：O(1)
最坏情况
除非特别指定，我们提到的运行时间都指的是最坏情况下的运行时间。
例：有一个存储了n个随机数字的数组，请从中查找出指定的数字。
最好情况：查找的第一个数字就是期望的数字，那么算法的时间复杂度为O(1)。
最坏情况：查找的最后一个数字，才是期望的数字，那么算法的时间复杂度为O(n)。
平均情况：任何数字查找的平均成本是O(n/2)。
算法的空间复杂度分析（了解）
在早期，算法在运行过程中对内存的占用情况也是一个经常需要考虑的问题。我们可以用算法的空间复杂度来描述算法对内存的占用。
- 基本数据类型的内存占用情况
- 计算机访问内存的方式都是一次一个字节。
- 一个引用需要8个字节来表示。
- Date d1 = new Date(),则d1这个变量需要占用8个字节来表示
- 创建一个对象，例如new Date(),除了对象内部存储的数据占用内存，该对象的本身也有内存开销，每个对象占用16个字节，用来保存对象的头信息。
- 在内存的使用中，如果不够8个字节，则会被自动填充为8字节。
java中数组被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销，4字节用于保存长度以及4个填充字节)再加上保存值所需的内存)。
数组
基本介绍
数组对应的英文是array， 是有限个相同类型的变量所组成的有序集合， 数组中的每一个变量被称为元素。 数组是最为简单、 最为常用的数据结构。
数组的每一个元素也有着自己的下标， 下标从0开始， 一直到数组长度-1。
数组的基本操作
插入操作
数组的实际元素数量有可能小于数组的长度 。
因此，数组的插入操作存在3中情况：
- 时间复杂度为O(1)，直接将元素放入数组尾部的空闲位置即可。
中间插入
由于数组的每一个元素都有其固定下标， 所以不得不首先把插入位置及后面的元素向后移动， 腾出地方， 再把要插入的元素放到对应的数组位置上。
代码： ```java package ch00_array;
/**
数组的中间插入操作 */ public class ArrayIns { private int[] array; private int size;
public ArrayIns(int capacity) {
//初始化数组大小this.array = new int[capacity];/*数组中元素的个数不是length，length是长度，比如这个数组的length就是10！*/size = 0;
}
/**
- 数组插入元素 *
- @param element 插入的元素
@param index 插入位置的下标 */ public void insert(int element, int index) { //判断访问下标index是否越界 if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("数组下标越界！");
} / 从后向前循环，将元素逐个向右移动一位 size=index，尾部插入 size>index，中间或头部插入 / for (int i = size; i >= index; i—) {
array[i + 1] = array[i];
} //将插入的元素放入腾出的空位置中 array[index] = element; //元素+1 size++; }
/**
数组的遍历 */ public void output() { for (int i = 0; i < size; i++) {
System.out.println(array[i]);
} }
public static void main(String[] args) { ArrayIns arrayIns = new ArrayIns(10); arrayIns.insert(3, 0); arrayIns.insert(4, 1); arrayIns.insert(5, 2); arrayIns.insert(6, 3);
arrayIns.insert(6, 1); arrayIns.output(); }
}
<a name="y4AU7"></a>#### 超范围插入<br />如图所示，当有一个长度为6的数组，已经装满了元素，此时想插入一个新元素。这就涉及到了超范围插入。<br /> **解决方案：**<br />创建一个新数组， 长度是旧数组的2倍， 再把旧数组中的元素统统复制过去， 这样就实现了数组的扩容。<br /><br />**代码：**```javapackage ch00_array;/*** 数组的中间插入操作*/public class ArrayIns {private int[] array;private int size;public ArrayIns(int capacity) {//初始化数组大小this.array = new int[capacity];/*数组中元素的个数不是length，length是长度，比如这个数组的length就是10！*/size = 0;}/*** 数组插入元素** @param element 插入的元素* @param index 插入位置的下标*/public void insert(int element, int index) {//判断访问下标index是否越界if (index < 0 || index > size) {throw new IndexOutOfBoundsException("数组下标越界！");}//判断数组元素个数是否达到容量上限，若达到则扩容if (size >= array.length) {resize();}/*从后向前循环，将元素逐个向右移动一位size=index，尾部插入size>index，中间或头部插入*/for (int i = size-1; i >= index; i--) {array[i + 1] = array[i];}//将插入的元素放入腾出的空位置中array[index] = element;//元素+1size++;}/*** 数组的扩容* arraycopy(Object src, int srcPos, Object dest, int destPos,int length);* src：要复制的数组(源数组)* srcPos：复制源数组的起始位置* dest：目标数组* destPos：目标数组的下标位置* length：要复制的长度*/private void resize() {int[] newArray = new int[array.length * 2];System.arraycopy(array, 0, newArray, 0, array.length);array = newArray;}/*** 数组的遍历*/public void output() {for (int i = 0; i < size; i++) {System.out.println(array[i]);}System.out.println("数组长度"+array.length);}public static void main(String[] args) {ArrayIns arrayIns = new ArrayIns(4);arrayIns.insert(3, 0);arrayIns.insert(4, 1);arrayIns.insert(5, 2);arrayIns.insert(6, 3);//超范围插入arrayIns.insert(6, 1);arrayIns.output();}}
删除操作
数组的删除操作和插入操作的过程相反， 如果删除的元素位于数组中间， 其后的元素都需要向前挪动1位由于不涉及扩容问题， 所以删除操作的代码实现比插入操作要简单。
代码：
/*** 数组删除元素操作** @param index* @return*/public int delete(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("超出数组实际元素范围！");}int deleteElement = array[index];//从前向后循环，将元素逐个向左移动一位for (int i = index; i < size - 1; i++) {array[i] = array[i + 1];}size--;return deleteElement;}
栈
基本介绍
栈是限制插入和删除只能在一个位置上进行的线性表。
- 允许插入和删除的一端称为末端，叫做栈顶（top）。
- 不允许插入和删除的另一端叫做栈底（bottom）。
- push（压栈），相当于表的插入操作（向栈顶插入一个元素）。
- pop（弹栈），相当于表的删除操作（删除栈顶的一个元素）。
- 栈是一种 后进先出（LIFO）的数据结构。
实现栈的方式
由于栈是一个表，因此任何实现表的方法都可以用来实现栈。主要有两种方式，链表实现和数组实现。链表实现栈
可以使用单链表来实现栈。通过在表顶端插入一个元素来实现 PUSH，通过删除表顶端元素来实现 POP。使用链表方式实现的栈又叫动态栈。动态栈有链表的部分特性，即元素与元素之间在物理存储上可以不连续，但是功能有些受限制，动态栈只能在栈顶处进行插入和删除操作，不能在栈尾或栈中间进行插入和删除操作。数组实现栈
栈也可以用数组来实现。使用数组方式实现的栈叫静态栈。栈的快速入门
使用数组来模拟栈的使用
```java package ch01_stack;
/**
使用数组模拟栈 */ public class ArrayStack { //栈的大小 private int maxStack; //数组模拟栈 private int[] stack; //表示栈顶，默认值为-1（空栈）。 private int top = -1;
//初始化栈的大小 public ArrayStack(int maxStack) {
this.maxStack = maxStack;this.stack = new int[this.maxStack];
}
/**
- 判断栈是否已满 *
- @return true-满
false-未满 */ public boolean isFull() { return this.top == maxStack - 1; }
/**
- 判断栈是否为空栈 *
- @return true-空栈
false-非空 */ public boolean isEmpty() { return this.top == -1; }
/**
- 入栈
- 先移动栈顶指针，后赋值。
@param value-入栈值 */ public void push(int value) { //判断是否满栈 if (isFull()) {
throw new RuntimeException("此栈已满！");
} //若没满，栈顶指针上移 top++; //赋值 stack[top] = value; }
/**
- 弹栈
- 先赋值，后移动栈顶指针。
@return */ public int pop() { //判断是否为空栈 if (isEmpty()) {
throw new RuntimeException("此栈为空栈，无数据。");
} //赋值 int value = stack[top]; //指针下移 top—;
return value; }
/**
- 查看栈中全部数据
*/
public void list(){
if (isEmpty()){
} for (int i = 0; i < stack.length; i++) {throw new RuntimeException("此栈为空栈，无数据。");
} } /**System.out.println("stack["+i+"]="+stack[i]+"\n");
- 获取栈中元素存在的个数
- 其实这个不太需要，我使用字符串的长度不就可以了么？ */ public int length(){ return this.top++; } }
<a name="HOElP"></a>### 判断回文数**回文**：一个单词、短语或数字，从前往后写和从后往前写都是一样的。例如，dad，1001。<br />**思路**：使用栈，可以轻松判断一个字符串是否是回文。1. 我们将拿到的字符串的每个字符按从左至右的顺序压入栈。1. 当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串。**代码：**```javapackage ch01_stack.huiwenshu;import ch01_stack.ArrayStack;public class Test {public static void main(String[] args) {boolean b = detection("hello");System.out.println(b);boolean b1 = detection("1001");System.out.println(b1);}/*** 判断是否为回文数*/public static boolean detection(String words) {ArrayStack arrayStack = new ArrayStack(10);//字符串长度int length = words.length();//将字符串压栈for (int i = 0; i < length; i++) {arrayStack.push(words.charAt(i));}//将字符弹栈String newVal = "";for (int i = 0; i < length; i++) {if (!arrayStack.isEmpty()) {char val = (char) arrayStack.pop();newVal = newVal + val;}}if (words.equals(newVal)){return true;}return false;}}
栈实现计算器
思路：
前备知识点总结：
- int→char可以自动类型转换
- charAt(int index)：返回索引处字符。
- subString(int beginIndex, int endIndex)：截取字符串，左闭右开。
代码：
数组模拟栈：
package ch01_stack.calculator;/*** 使用数组模拟栈*/public class ArrayStack {//栈的大小private int maxStack;//数组模拟栈private int[] stack;//表示栈顶，默认值为-1（空栈）。private int top = -1;//初始化栈的大小public ArrayStack(int maxStack) {this.maxStack = maxStack;//初始化数组容量this.stack = new int[this.maxStack];}/*** 判断栈是否已满** @return true-满* false-未满*/public boolean isFull() {return this.top == maxStack - 1;}/*** 判断栈是否为空栈** @return true-空栈* false-非空*/public boolean isEmpty() {return this.top == -1;}/*** 入栈* 先移动栈顶指针，后赋值。** @param value-入栈值*/public void push(int value) {//判断是否满栈if (isFull()) {throw new RuntimeException("此栈已满！");}//若没满，栈顶指针上移top++;//赋值stack[top] = value;}/*** 弹栈* 先赋值，后移动栈顶指针。** @return*/public int pop() {//判断是否为空栈if (isEmpty()) {throw new RuntimeException("此栈为空栈，无数据。");}//赋值int value = stack[top];//指针下移top--;return value;}/*** 查看栈中全部数据*/public void list() {if (isEmpty()) {throw new RuntimeException("此栈为空栈，无数据。");}for (int i = 0; i < stack.length; i++) {System.out.println("stack[" + i + "]=" + stack[i] + "\n");}}/*** 获取栈中元素存在的个数* 其实这个不太需要，我使用字符串的长度不就可以了么？*/public int length() {return this.top++;}/*** 查看栈顶元素** @return-栈顶元素*/public int peak() {return stack[top];}/*** 判断字符是否是运算符** @param v：字符* @return：true-是运算符，false-不是运算符*/public boolean isOper(char v) {return v == '+' || v == '-' || v == '*' || v == '/';}/*** 运算符优先级** @param oper——运算符* @return——数字越大优先级越高*/public int priority(char oper) {//乘除if (oper == '*' || oper == '/') {return 1;}//加减else if (oper == '+' || oper == '-') {return 0;}//其他else {return -1;}}/*** 计算功能** @param num1：值1* @param num2：值2* @param oper：运算符* @return：计算结果*/public int calculate(int num1, int num2, int oper) {int result = 0;switch (oper) {case '+':result = num1 + num2;break;case '-':result =num2-num1;break;case '*':result=num1*num2;break;case '/':result=num2/num1;break;default:break;}return result;}}
main方法：
package ch01_stack.calculator;public class Test {public static void main(String[] args) {String str = "3*2+10";//数字栈ArrayStack numStack = new ArrayStack(10);//运算符栈ArrayStack symbolStack = new ArrayStack(10);//获取字符串长度int length = str.length();int temp1 = 0;int temp2 = 0;int symbolChar = 0;int result = 0;String values = "";for (int i = 0; i < length; i++) {//获取字符串中的每一个字符char c = str.charAt(i);//判断该字符是否是一个运算符，是if (symbolStack.isOper(c)) {/*判断运算符栈是否为空栈true-非空false-空*/if (!symbolStack.isEmpty()) {//比较当前运算符和栈中运算符的优先级/*当前运算符优先级<=栈中运算符优先级1.取出数字栈中的两个数字2.取出运算符栈中的运算符3.进行运算，求出结果4.将结果再次放入数字栈中5.将当前运算符放入运算符栈中*/if (symbolStack.priority(c) <= symbolStack.priority((char) symbolStack.peak())) {//1.取出数字栈中的两个数字temp1 = numStack.pop();temp2 = numStack.pop();//2.取出运算符栈中的运算符symbolChar = symbolStack.pop();//3.进行运算result = numStack.calculate(temp1, temp2, symbolChar);//4.将结果再次放入数字栈中numStack.push(result);//5.将当前运算符放入运算符栈中symbolStack.push(c);}//当前运算符优先级 > 栈中运算符优先级else {//直接放入运算符栈中symbolStack.push(c);}}//运算符栈为空else {//直接放入运算符栈中symbolStack.push(c);}}/*该字符不是运算符，则是数字。*/else {//若是多位数字（33，44），则进行字符串拼接values += c;//若当前数字字符是最后一个字符，则直接放入数字栈中if (i == length - 1) {numStack.push(Integer.parseInt(values));}//若当前数字字符不是最后一个字符else {//截取下一位字符char data = str.substring(i + 1, i + 2).charAt(0);//判断该字符是否为运算符，若为运算符直接将数字压栈，并清空values。if (symbolStack.isOper(data)) {numStack.push(Integer.parseInt(values));values = "";}}}}//取出栈中数据进行计算while (true) {//若运算符栈为空，则跳出循环。if (symbolStack.isEmpty()) {break;}temp1 = numStack.pop();temp2 = numStack.pop();symbolChar = symbolStack.pop();result = numStack.calculate(temp1, temp2, symbolChar);//将运算结果压栈numStack.push(result);}//取出最终结果int res = numStack.pop();System.out.println("结果是：" + res);}}
链表
基本介绍
链表（Linked List）是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。
物理结构：
逻辑结构：
特点：
- 链表是以结点形式存储的，是链式存储。
- 每个结点都包含data区域（数据元素）和next区域（下一个结点的存储位置）。
- 各个结点并不是连续存储的
- 链表分为带头结点链表和无头结点链表。
链表的第一个结点被称为头结点，最后一个结点称为尾结点，尾结点的next指针指向空。
链表的快速入门
单链表的基本操作
根据带有头部的单链表，实现商品增删改查，并且也可以针对商品的编号进行排序，完成排行榜。
难点：temp==null 与 temp.next==null的区别？
temp.next==null 比 temp==null 早一步少了一次循环。
代码：
GoodsNode
package ch02_linked;/*** 商品结点*/public class GoodsNode {//商品idpublic int id;//商品名称public String name;//商品价格public double price;//指针，指向下一个结点public GoodsNode next;public GoodsNode(int id, String name, double price) {this.id = id;this.name = name;this.price = price;}@Overridepublic String toString() {return "GoodsNode{" +"id=" + id +", name='" + name + '\'' +", price=" + price +'}';}}
DLLinkedList
package ch02_linked;/*** 结点的增删改查*/public class DLLinkedList {//头结点private GoodsNode node = new GoodsNode(0, "", 0.0);/*** 向链表中添加结点（尾端）** @param goodsNode*/public void add(GoodsNode goodsNode) {//将头结点赋值给临时变量GoodsNode temp = node;while (true) {//如果下一个结点为空，直接跳出循环if (temp.next == null) {break;}//如果下一个结点不为空，继续赋值temp = temp.next;}//将新增结点添加进去temp.next = goodsNode;}/*** 按照商品标号id进行添加结点，从小到大的顺序进行添加** @param goodsNode*/public void addByOrder(GoodsNode goodsNode) {GoodsNode temp = node;boolean flag = false;/*跳出循环的3个条件：1.下一个结点为空2.当下一个结点的id值大于插入结点的id值时.3.当下一个结点的id值等于插入结点的id值时。*/while (true) {if (temp.next == null) {break;}if (temp.next.id > goodsNode.id) {break;} else if (temp.next.id == goodsNode.id) {flag = true;break;}temp = temp.next;}if (flag) {System.out.println("该商品id已存在，不能添加重复元素。");} else {//连接后面goodsNode.next = temp.next;//连接前面temp.next = goodsNode;}}/*** 修改结点** @param goodsNode*/public void updateNode(GoodsNode goodsNode) {//判断是否为空链表if (node.next == null) {System.out.println("链表为空！");return;}//将头结点赋值给临时变量GoodsNode temp = node;//用于区分跳出循环的两个条件boolean flag = false;/***跳出循环的2个条件：* 1.在整个列表中未找到对应的结点* 2.找到了对应的结点*/while (true) {/*temp与temp.next的区别？temp.next==null会比temp==null少循环一次。*/if (temp == null) {break;}if (temp.id == goodsNode.id) {flag = true;break;}temp = temp.next;}if (flag) {temp.name = goodsNode.name;temp.price = goodsNode.price;} else {System.out.println("在整个列表中未找到对应的结点！");}}/*** 根据商品id删除结点** @param id:商品id*/public void delNode(int id) {//判断是否为空链表if (node.next == null) {System.out.println("链表为空！");return;}GoodsNode temp = node;boolean flag = false;/***跳出循环的2个条件：* 1.在整个列表中未找到对应的结点* 2.找到了对应的结点*/while (true) {if (temp.next == null) {break;}if (temp.next.id == id) {flag = true;break;}temp = temp.next;}if (flag) {//找到了对应结点，直接指向对应结点的下一个结点，等于删除。temp.next = temp.next.next;} else {System.out.println("在整个列表中未找到对应的结点！");}}/*** 查看链表中的每一个结点元素*/public void list() {if (node.next == null) {System.out.println("链表为空！");return;}GoodsNode temp = node.next;while (true) {if (temp == null) {break;}System.out.println(temp);temp = temp.next;}}/*** 面试题：计算单链表中结点个数（不包括头结点）** @return-结点个数*/public int getLength() {if (node.next == null) {System.out.println("空链表");return 0;}GoodsNode temp = node.next;int length = 0;while (temp != null) {length++;temp = temp.next;}return length;}}
LinkedTest
package ch02_linked;public class LinkedTest {public static void main(String[] args) {GoodsNode g1 = new GoodsNode(1,"a",99.0);GoodsNode g2 = new GoodsNode(2,"b",89.0);GoodsNode g3 = new GoodsNode(3,"c",79.0);DLLinkedList linkedList = new DLLinkedList();/* linkedList.add(g2);linkedList.add(g1);linkedList.add(g3);linkedList.list();*/linkedList.addByOrder(g2);linkedList.addByOrder(g1);linkedList.addByOrder(g3);System.out.println("------------");linkedList.list();linkedList.updateNode(new GoodsNode(3,"james",76.0));System.out.println("--------------------");linkedList.list();linkedList.delNode(3);System.out.println("--------------------");linkedList.list();int length = linkedList.getLength();System.out.println(length);}}
常见面试题
给定一个单链表，实现反转链表。
单向链表只知道自己的直接后继。
![VLA68`TE]}MV8U926S%QY_7.png](/uploads/projects/mu1225@ldh5xh/12d9e50321dbc236d2454839fb40d42a.png)
双向链表的基本操作
根据带有头部的双向链表，实现图书的增删改查，并且也可以针对图书的编号进行排序，完成排行榜。
注：删除功能有bug
BookNode
package ch02_linked.dual;public class BookNode {public int id;public String name;public double price;public BookNode pre;public BookNode next;public BookNode(int id, String name, double price) {this.id = id;this.name = name;this.price = price;}@Overridepublic String toString() {return "BookNode{" +"id=" + id +", name='" + name + '\'' +", price=" + price +'}';}}
DualLinkedList
package ch02_linked.dual;import ch02_linked.single.GoodsNode;import com.sun.imageio.plugins.wbmp.WBMPImageReader;/*** 双向链表结点的增删改查*/public class DualLinkedList {//创建头结点private BookNode node = new BookNode(0, "", 0.0);/*** 向双向链表的末尾添加结点** @param newNode*/public void addLast(BookNode newNode) {//获取头结点BookNode temp = node;//寻找双向链表的末尾结点while (true) {if (temp.next == null) {break;}temp = temp.next;}/*此时的temp就代表着链表的末尾结点temp的next指向新结点新结点的pre指向temp完成结点的添加*/temp.next = newNode;newNode.pre = temp;}/*** 根据图书标号id进行添加结点，按照从小到大的顺序进行添加** @param newNode*/public void addByOrder(BookNode newNode) {BookNode temp = node;/*** 跳出循环的3个条件：* 1.当添加的结点为第一个结点时* 1.下一个结点为空* 2.当下一个结点的id值大于插入结点的id值时.* 3.当下一个结点的id值等于插入结点的id值时。*/while (true) {//头部插入if (temp.next == null && temp.pre == null) {temp.next = newNode;newNode.pre = null;break;}//尾部插入if (temp.next == null && temp.pre != null) {temp.next = newNode;}//中间插入if (temp.id < newNode.id && temp.next.id > newNode.id) {// booksNode的后继指向temp的后一个"节点"newNode.next = temp.next;// temp的后一个"节点"的前驱指向booksNodetemp.next.pre = newNode;// temp的后继指向"节点"booksNodetemp.next = newNode;// booksNode的前期指向"节点"tempnewNode.pre = temp;break;}if (temp.next.id == newNode.id) {System.out.println("该书籍已经有了" + temp.next.id);break;}temp = temp.next;}}/*** 修改结点内容** @param newNode*/public void updateNode(BookNode newNode) {//判断空链表if (node.next == null) {System.out.println("空链表..");return;}BookNode temp = node.next;boolean flag = false;/*** 跳出循环的条件：* 1.整个链表中未找到对应结点* 2.找到了对应结点*/while (true) {if (temp.id == newNode.id) {flag = true;break;}if (temp.next == null) {break;}temp = temp.next;}if (flag) {temp.name = newNode.name;temp.price = newNode.price;} else {System.out.println("未找到对应结点！");}}/*** 根据id编号删除对象结点** @param*/public void delNode(BookNode bookNode) {if (node.next == null) {System.out.println("空链表..");return;}BookNode temp = node;/*** 跳出循环的条件：* 1.在整个链表中未找到对应结点* 2.找到了对应结点*/while (true) {if (temp.next == null) {System.out.println("未找到对应的结点！");break;}if (temp.next.id == bookNode.id) {System.out.println("恭喜成功删除" + temp.next + "结点！");if (temp.next.next == null) {temp.next = null;break;}temp.next.next.pre = temp;temp.next = temp.next.next;break;}temp = temp.next;}}/*** 遍历链表*/public void list() {if (node.next == null) {System.out.println("空链表！");return;}BookNode temp = node.next;while (true) {if (temp == null) {break;}System.out.println(temp);temp = temp.next;}}}
DualLinkedListTest
package ch02_linked;import ch02_linked.dual.BookNode;import ch02_linked.dual.DualLinkedList;public class DualLinkedListTest {public static void main(String[] args) {BookNode b1 = new BookNode(1,"james",66.00);BookNode b2 = new BookNode(2,"kobe",66.00);BookNode b3 = new BookNode(3,"davis",66.00);BookNode b4 = new BookNode(4,"paul",66.00);DualLinkedList dualLinkedList = new DualLinkedList();//测试添加dualLinkedList.addLast(b1);dualLinkedList.addLast(b3);dualLinkedList.addByOrder(b2);dualLinkedList.addByOrder(b4);dualLinkedList.list();System.out.println("-----------------");/*测试删除有bug：只能删除第一个结点，后面的结点的删除都多少有点bug*/dualLinkedList.delNode(1);dualLinkedList.list();System.out.println("--------------");//测试修改dualLinkedList.updateNode(new BookNode(3,"myt",66.00));dualLinkedList.list();}}
单向环形链表（不理解）
基本介绍
如果把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表，通俗讲就是把尾节点的下一跳指向头结点。
约瑟夫问题（约瑟夫环）
解决思路（思路）
- 做环形链表
- 解决约瑟夫问题
代码：
若有收获，就点个赞吧
0 人点赞
