链表
1 链表
- 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。
2 单链表
- 商品结点类
package com.acti.linkedList;
/**
* author hongyeci
* date 20220722
* version 1.0
* remark 单链表--商品类
*/
public class GoodsNode {
private int goodsId;
private String goodsName;
private double goodsPrice;
private GoodsNode next;
public GoodsNode() {
}
public GoodsNode(int goodsId, String goodsName, double goodsPrice) {
this.goodsId = goodsId;
this.goodsName = goodsName;
this.goodsPrice = goodsPrice;
}
public int getGoodsId() {
return goodsId;
}
public void setGoodsId(int goodsId) {
this.goodsId = goodsId;
}
public String getGoodsName() {
return goodsName;
}
public void setGoodsName(String goodsName) {
this.goodsName = goodsName;
}
public double getGoodsPrice() {
return goodsPrice;
}
public void setGoodsPrice(double goodsPrice) {
this.goodsPrice = goodsPrice;
}
public GoodsNode getNext() {
return next;
}
public void setNext(GoodsNode next) {
this.next = next;
}
@Override
public String toString() {
return "GoodsNode{" +
"goodsId=" + goodsId +
", goodsName='" + goodsName + '\'' +
", goodsPrice=" + goodsPrice +
", next=" + next +
'}';
}
}
- 带有头结点的单链表
package com.acti.linkedList;
/**
* author hongyeci
* date 20220722
* version 1.0
* remark 带有头结点的单链表
*/
public class SingleLinkedList {
private GoodsNode node = new GoodsNode(0,"头结点",0.0);
/**
* 增加结点-添加到末尾结点
* @param goodsNode 商品结点
*/
public void addNode(GoodsNode goodsNode){
GoodsNode temp = node;
while(true){
if (temp.getNext() == null){
break;
}
temp=temp.getNext();
}
temp.setNext(goodsNode);
}
/**
* 指定位置插入值
* 按照商品id值顺序插入到链表中
* @param goodsNode
*/
public void insertNode(GoodsNode goodsNode){
GoodsNode temp = node;
boolean flag = false;
while(true){
if (temp.getNext() == null){
break;
}
if (temp.getNext().getGoodsId()>goodsNode.getGoodsId()){
break;
}else if (temp.getNext().getGoodsId() == goodsNode.getGoodsId()){
flag = true;
break;
}
temp=temp.getNext();
}
if (flag){
throw new RuntimeException("不能插入重复的商品...");
}else {
goodsNode.setNext(temp.getNext());
temp.setNext(goodsNode);
}
}
/**
* 修改指定结点data域信息
* @param goodsNode
*/
public void updateNode(GoodsNode goodsNode){
GoodsNode temp = node;
if (temp.getNext() == null){
throw new RuntimeException("该链表为空链表，不能进行修改操作...");
}
boolean flag = false;
while (true){
//1 直到最后一个结点
if (temp.getNext()==null){
break;
}
//2 找到指定结点
if (temp.getNext().getGoodsId()==goodsNode.getGoodsId()){
flag = true;
break;
}
temp = temp.getNext();
}
if (flag){
//修改指定结点data域数据
temp.getNext().setGoodsName(goodsNode.getGoodsName());
temp.getNext().setGoodsPrice(goodsNode.getGoodsPrice());
}else {
throw new RuntimeException("未找到指定结点...");
}
}
/**
* 删除指定结点
* 根据结点ID删除指定结点
* @param goodsId
*/
public void deleteNode(int goodsId){
//判断链表是否为空
if (node.getNext() == null){
throw new RuntimeException("该链表为空链表，不能进行删除操作...");
}
GoodsNode temp = node; //头结点
boolean flag = false; //是否做删除操作标识
//遍历链表结点 获取指定结点
while (true){
//遍历至最后一个结点 退出遍历
if (temp.getNext()==null){
break;
}
//找到指定结点
if (temp.getNext().getGoodsId()==goodsId){
flag = true;
break;
}
temp = temp.getNext();
}
if (flag){
//删除操作
temp.setNext(temp.getNext().getNext());
}else {
throw new RuntimeException("未找到指定删除结点...");
}
}
/**
* 获取当前单链表的结点个数
* @return
*/
public int lengthNode(){
int length = 0;
GoodsNode temp = node.getNext();
while (temp!=null){
length++;
temp = temp.getNext();
}
return length;
}
/**
* 查看链表元素
*/
public void listNode(){
if (node.getNext()==null){
System.out.println("空链表...");
}else {
GoodsNode temp = node;
while (true){
if (temp.getNext()==null){
break;
}
temp = temp.getNext();
System.out.println(temp);
}
}
}
}
3 双链表
- 图书结点类
package com.acti.linkedList;
/**
* author hongyeci
* date 20220725
* version 1.0
* remark 双链表--图书类
*/
public class BooksNode {
private int id;
private String name;
private double price;
private BooksNode pre; //双链表前驱结点
private BooksNode next; //双链表后继结点
public BooksNode() {
}
public BooksNode(int id, String name, double price) {
this.id = id;
this.name = name;
this.price = price;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public double getPrice() {
return price;
}
public void setPrice(double price) {
this.price = price;
}
public BooksNode getPre() {
return pre;
}
public void setPre(BooksNode pre) {
this.pre = pre;
}
public BooksNode getNext() {
return next;
}
public void setNext(BooksNode next) {
this.next = next;
}
@Override
public String toString() {
return "BooksNode{" +
"id=" + id +
", name='" + name + '\'' +
", price=" + price +
'}';
}
}
- 带有头结点的双链表
package com.acti.linkedList;
/**
* author hongyeci
* date 20220725
* version 1.0
* remark 带有头结点的双链表
*/
public class DoubleLinkedList {
private BooksNode head = new BooksNode(0,"头结点",0.0);
/**
* 增加结点-添加到末尾结点
* @param booksNode 图书结点
*/
public void addNode(BooksNode booksNode){
BooksNode temp = head;
while(true){
if (temp.getNext() == null){
break;
}
temp=temp.getNext();
}
temp.setNext(booksNode);
booksNode.setPre(temp);
}
/**
* 指定位置插入值
* 按照商品id值顺序插入到链表中
* @param booksNode
*/
public void insertNode(BooksNode booksNode){
BooksNode temp = head;
boolean flag = false;
while(true){
if (temp.getNext() == null){
break;
}
if (temp.getNext().getId()>booksNode.getId()){
break;
}else if (temp.getId() == booksNode.getId()){
flag = true;
break;
}
temp=temp.getNext();
}
if (flag){
throw new RuntimeException("不能插入重复的商品...");
}else {
if (temp.getNext()==null){
temp.setNext(booksNode);
booksNode.setPre(temp);
}else {
//1、当前结点的后继结点后继节点前驱指向新结点
temp.getNext().setPre(booksNode);
//2、新结点后继结点指向当前结点后继结点
booksNode.setNext(temp.getNext());
//3、新结点前驱结点指向当前结点
booksNode.setPre(temp);
//4、当前结点后继结点指向新结点
temp.setNext(booksNode);
}
}
}
/**
* 修改指定结点data域信息
* @param booksNode
*/
public void updateNode(BooksNode booksNode){
BooksNode temp = head;
if (temp.getNext() == null){
throw new RuntimeException("该双向链表为空链表，不能进行修改操作...");
}
boolean flag = false;
while (true){
//1 直到最后一个结点
if (temp.getNext()==null){
break;
}
//2 找到指定结点
if (temp.getId()==booksNode.getId()){
flag = true;
break;
}
temp = temp.getNext();
}
if (flag){
//修改指定结点data域数据
temp.setName(booksNode.getName());
temp.setPrice(booksNode.getPrice());
}else {
throw new RuntimeException("未找到指定结点...");
}
}
/**
* 删除指定结点
* 根据结点ID删除指定结点
* @param id
*/
public void deleteNode(int id){
BooksNode temp = head; //头结点
//判断链表是否为空
if (temp.getNext() == null){
throw new RuntimeException("该链表为空链表，不能进行删除操作...");
}
boolean flag = false; //是否做删除操作标识
//遍历链表结点 获取指定结点
while (true){
//遍历至最后一个结点 退出遍历
if (temp.getNext()==null){
break;
}
//找到指定结点
if (temp.getId()==id){
flag = true;
break;
}
temp = temp.getNext();
}
if (flag){
//1、当前结点前驱结点的后继指向当前结点的后继结点
temp.getPre().setNext(temp.getNext());
//2、当前结点的后继结点前驱指向当前结点的前驱结点
if (temp.getNext()!=null){
temp.getNext().setPre(temp.getPre());
}
}else {
throw new RuntimeException("未找到指定删除结点...");
}
}
/**
* 获取当前单链表的结点个数
* @return
*/
public int lengthNode(){
int length = 0;
BooksNode temp = head.getNext();
while (temp!=null){
length++;
temp = temp.getNext();
}
return length;
}
/**
* 查看链表元素
*/
public void listNode(){
if (head.getNext()==null){
System.out.println("空链表...");
}else {
BooksNode temp = head;
while (true){
if (temp.getNext()==null){
break;
}
temp = temp.getNext();
System.out.println(temp);
}
}
}
}
4 单向环形链表-约瑟夫环
- 设编号为1,2,...,n的n个人围坐成一圈，约定编号为k(1=<k<=n)的人开始从1报数，数到m的人出列，他的下一位又从1开始报数，数到m的人出列，依此类推，直到所有人都出列为止，由此产生一个出队编号的序列。
- 节点类
package com.structure.linkedList;
/**
* author hongyeci
* date 20220829
* version 1.0
* remark 单向环形链表--结点类
*/
public class BoyNode {
//结点编号
private int boyNo;
//指向下一个结点
private BoyNode next;
public BoyNode(int boyNo) {
this.boyNo = boyNo;
}
public int getBoyNo() {
return boyNo;
}
public void setBoyNo(int boyNo) {
this.boyNo = boyNo;
}
public BoyNode getNext() {
return next;
}
public void setNext(BoyNode next) {
this.next = next;
}
}
- 单向循环链表-约瑟夫环
package com.structure.linkedList;
/**
* author hongyeci
* date 20220830
* version 1.0
* remark 单向环形链表--约瑟夫环
*/
public class CircleSingleLinkedList {
private BoyNode firstNode = new BoyNode(-1);
/**
* 定义单向环形链表
* @param nums 结点个数
*/
public void initCircleSingleLinkedList(int nums){
if (nums<1){
System.out.println("结点个数不能小于1");
return;
}
//定义辅助结点，新进的结点赋给辅助结点
BoyNode temp = null;
for (int i=1;i<=nums;i++){
BoyNode newBoy = new BoyNode(i);
if (i == 1){
//首结点时
firstNode = newBoy;
firstNode.setNext(firstNode);
temp = firstNode;
}else {
temp.setNext(newBoy);
newBoy.setNext(firstNode);
temp=newBoy;
}
}
}
/**
* 遍历输出循环链表--链表结点的编号
*/
public void showCircleList(){
if (firstNode == null){
System.out.println("该链表为空..");
return;
}
BoyNode node = firstNode;
while (true){
System.out.printf("当前结点编号为：%d\n",node.getBoyNo());
//遍历到最后一个结点时，退出
if (node.getNext()==firstNode){
break;
}
node = node.getNext();
}
}
/**
* 约瑟夫环问题：
* 设编号为1,2,...,n的n个人围坐成一圈，约定编号为k(1=<k<=n)的人开始从1报数，数到m的人出列，
* 他的下一位又从1开始报数，数到m的人出列，依此类推，直到所有人都出列为止，由此产生一个出队编号的序列。
* @param startNo 开始结点
* @param count 间隔结点数
* @param nums 单向循环链表中结点个数
*/
public void handle(int startNo,int count,int nums){
if(startNo>nums || startNo<1 || firstNode==null){
System.out.println("参数错误..");
return;
}
//定义辅助结点，指向最后一个结点
BoyNode lastNode = firstNode;
while (true){
if (lastNode.getNext() == firstNode){
//找到最后结点时退出
break;
}
lastNode = lastNode.getNext();
}
//确定编号为startNo的结点移动次数startNo-1 找到firstNode、lastNode
for(int i=0;i<startNo-1;i++){
firstNode = firstNode.getNext();
lastNode = lastNode.getNext();
}
//开始数数，数到count的结点出列
while (true){
if (lastNode == firstNode){
//单项循环链表中只剩一个结点时 出列
System.out.printf("最后一个结点%d出列\n",firstNode.getBoyNo());
break;
}
//数数
// firstNode.setBoyNo(firstNode.getBoyNo()+(count-1));
// lastNode.setBoyNo(lastNode.getBoyNo()+(count-1));
for (int i=0;i<count-1;i++){
firstNode = firstNode.getNext();
lastNode = lastNode.getNext();
}
//出列
System.out.printf("结点%d出列\n",firstNode.getBoyNo());
//构成循环链表
firstNode = firstNode.getNext();
lastNode.setNext(firstNode);
}
}
}