链表介绍
单向链表
代码实现
package com.xz.linkedlist;
import java.util.Stack;
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(hero2);
// singlelinkedList.add(hero3);
// singlelinkedList.add(hero4);
//按照编号加入
singlelinkedList.addByOrder(hero1);
singlelinkedList.addByOrder(hero4);
singlelinkedList.addByOrder(hero3);
singlelinkedList.addByOrder(hero2);
//显示
singlelinkedList.list();
//修改
Heronode xiaoLu = new HeroNode(2, "小卢", "玉麒麟~~");
singlelinkedList.update(xiaoLu);
//再次显示
System.out.println("=================");
singlelinkedList.list();
//删除
singlelinkedList.delete(2);
singlelinkedList.delete(3);
// singlelinkedList.delete(4);
System.out.println("================");
singlelinkedList.list();
System.out.println(getLength(singlelinkedList.getHead()));
// Heronode lastIndexNode = getLastIndexNode(singlelinkedList.getHead(), 2);
// System.out.println(lastIndexNode);
// System.out.println("======================");
// reverseList(singlelinkedList.getHead());
// singlelinkedList.list();
System.out.println("===================");
reversePrint(singlelinkedList.getHead());
}
//可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
public static void reversePrint(Heronode head) {
Heronode temp = head.next;
if (head.next == null) {
return;
}
Stack stack = new Stack<>();
while (temp != null) {
stack.push(temp);
temp = temp.next;
}
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
//将单链表反转
public static void reverseList(Heronode head) {
//如果当前链表为空，或者只有一个节点，无需反转，直接返回
if(head.next == null || head.next.next == null) {
return ;
}
//定义一个辅助的指针(变量)，帮助我们遍历原来的链表
Heronode cur = head.next;
Heronode next = null;// 指向当前节点[cur]的下一个节点
Heronode reverseHead = new HeroNode(0, "", "");
//遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
//动脑筋
while(cur != null) {
next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
reverseHead.next = cur; //将cur 连接到新的链表上
cur = next;//让cur后移
}
//将head.next 指向 reverseHead.next , 实现单链表的反转
head.next = reverseHead.next;
}
//编写一个方法：返回有效节点的个数
public static int getLength(Heronode head) {
int length = 0;
Heronode temp = head.next;
if (head.next == null) {//空链表
return 0;
}
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
//编写一个方法，返回倒数第K(index)个节点
public static Heronode getLastIndexNode(Heronode head, int index) {
if (head.next == null) {
System.out.println("链表为空！");
return null;//空链表
}
int length = getLength(head);
Heronode temp = head.next;
if (index <= 0 || index > length) {
System.out.println("输入不规范");
return null;
}
for (int i = 0; i < length - index; i++) {
temp = temp.next;
}
return temp;
}
}
//定义SinglelinkedList 管理我们的英雄
class SinglelinkedList {
//先初始化一个头节点，头节点不能动，不存放具体的数据
private Heronode head = new HeroNode(0, "", "");
public Heronode getHead() {
return head;
}
//添加节点到单向链表
//思路，当不考虑编号顺序时
//1. 找到当前链表的最后节点
//2. 将最后这个节点的next指向新的节点
public void add(Heronode heroNode) {
//因为head节点不能动，因此我们需要一个辅助变量temp
Heronode temp = head;
//遍历链接
while (true) {
//找到链表最后
if (temp.next == null) {
break;
}
//如果没有找到最后，就将temp后移
temp = temp.next;
}
//当退出while循环时，temp就指向了链表的最后
//将最后这个节点的next指向新的节点
temp.next = heroNode;
}
//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
//(如果有这个排名，则添加失败,并给出提示)
public void addByOrder(Heronode heroNode) {
//我们需要一个辅助变量（指针）来帮助我们找到添加的位置
//temp需要找到 位于添加位置的前一个节点
Heronode temp = head;
boolean flag = false;
while (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;
}
//判断flag的值
if (flag) {
System.out.println("准备插入的英雄编号" + heroNode.no + "已经存在，不能再插入了！");
} else {
//插入到链表中,temp的后面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
//根据节点的信息no，来修改内容
public void update(Heronode heroNode) {
//判断链表是否为空
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 == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
//判断flag是否找到修改的节点
if (flag) {
temp.name = heroNode.name;
temp.nickName = heroNode.nickName;
} else {
System.out.println("没有找到编号为" + heroNode.no + "的节点，无法修改！");
}
}
//删除节点
public void delete(int no) {
Heronode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (temp.next.no == no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
} else {
System.out.println("没有找到编号为" + no + "的节点，不能删除！");
}
}
//显示链表[遍历]
public void list() {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//因为头节点不能动，这里我们依然需要一个辅助变量temp
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方法
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + ''' +
", nickName='" + nickName + ''' +
'}';
}
}
双向链表
代码实现
package com.xz.linkedlist;
public class DoublelinkedListDemo {
public static void main(String[] args) {
//测试
System.out.println("双向链表的测试：");
//创建节点
HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
//创建双向链表
DoublelinkedList doublelinkedList = new DoublelinkedList();
doublelinkedList.add(hero1);
doublelinkedList.add(hero2);
doublelinkedList.add(hero3);
doublelinkedList.add(hero4);
doublelinkedList.list();
System.out.println("=======================");
doublelinkedList.del(3);
doublelinkedList.list();
System.out.println("=======================");
doublelinkedList.update(new HeroNode2(2,"小卢","玉麒麟~~"));
doublelinkedList.list();
}
}
class DoublelinkedList {
private HeroNode2 head = new HeroNode2(0, "", "");
public HeroNode2 getHead() {
return head;
}
//添加一个节点到双向链表的最后
public void add(HeroNode2 heroNode2) {
//因为head节点不能动，因此我们需要一个辅助变量temp
HeroNode2 temp = head;
//遍历链接
while (true) {
//找到链表最后
if (temp.next == null) {
break;
}
//如果没有找到最后，就将temp后移
temp = temp.next;
}
//当退出while循环时，temp就指向了链表的最后
//将最后这个节点的next指向新的节点
temp.next = heroNode2;
heroNode2.pre = temp;
}
// 从双向链表中删除一个节点,
// 说明
// 1 对于双向链表，我们可以直接找到要删除的这个节点
// 2 找到后，自我删除即可
public void del(int no) {
// 判断当前链表是否为空
if (head.next == null) {// 空链表
System.out.println("链表为空，无法删除");
return;
}
HeroNode2 temp = head.next; // 辅助变量(指针)
boolean flag = false; // 标志是否找到待删除节点的
while (true) {
if (temp == null) { // 已经到链表的最后
break;
}
if (temp.no == no) {
// 找到的待删除节点的前一个节点temp
flag = true;
break;
}
temp = temp.next; // temp后移，遍历
}
// 判断flag
if (flag) { // 找到
// 可以删除
// temp.next = temp.next.next;[单向链表]
temp.pre.next = temp.next;
// 这里我们的代码有问题?
// 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
if (temp.next != null) {
temp.next.pre = temp.pre;
}
} else {
System.out.printf("要删除的 %d 节点不存在n", no);
}
}
public void update(HeroNode2 heroNode2) {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//找到需要修改的节点（根据no编号）
HeroNode2 temp = head.next;
boolean flag = false;//表示是否找到该节点
while (true) {
if (temp == null) {
break;
}
if (temp.no == heroNode2.no) {
flag = true;
break;
}
temp = temp.next;
}
//判断flag是否找到修改的节点
if (flag) {
temp.name = heroNode2.name;
temp.nickName = heroNode2.nickName;
} else {
System.out.println("没有找到编号为" + heroNode2.no + "的节点，无法修改！");
}
}
//显示链表[遍历]
public void list() {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//因为头节点不能动，这里我们依然需要一个辅助变量temp
HeroNode2 temp = head.next;
while (true) {
//判断是否到链表最后
if (temp == null) {
break;
}
System.out.println(temp);
//将temp后移
temp = temp.next;
}
}
}
//定义HeroNode2,每一个HeroNode2对象是一个节点
class HeroNode2 {
public int no;
public String name;
public String nickName;
public HeroNode2 next;//指向下一个节点
public HeroNode2 pre;//指向上一个节点
//构造器
public HeroNode2(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
//为了显示方便，我们重写toString方法
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + ''' +
", nickName='" + nickName + ''' +
'}';
}
}
单项环形链表
代码实现约瑟夫环
package com.xz.linkedlist;
public class Josepfu {
public static void main(String[] args) {
//测试
CircleSinglelinkedList circleSinglelinkedList = new CircleSinglelinkedList();
circleSinglelinkedList.addBoy(5);
circleSinglelinkedList.showBoy();
System.out.println("===============");
circleSinglelinkedList.countBoy(1, 2, 5);
}
}
//创建一个环形单向链表
class CircleSinglelinkedList {
private Boy first = null;
//添加小孩节点，构建一个环形链表
public void addBoy(int nums) {
if (nums < 1) {
System.out.println("输入格式错误（ < 1 ）");
return;
}
Boy curBoy = null;
for (int i = 1; i <= nums; i++) {
//根据编号创建小孩节点
Boy boy = new Boy(i);
if (i == 1) {
first = boy;
first.setNext(first);
curBoy = first;//让curBoy指向第一个小孩
} else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
//遍历环形链表
public void showBoy() {
//判断当前链表是否为空
if (first == null) {
System.out.println("当前没有小孩！");
return;
}
Boy curBoy = first;
while (true) {
System.out.println("小孩的编号：" + curBoy.getNo());
if (curBoy.getNext() == first) {
break;
}
curBoy = curBoy.getNext();
}
}
public void countBoy(int startNo, int countNum, int nums) {
if (first == null || startNo > nums || startNo < 1 || countNum < 1 || nums < 1) {
System.out.println("输入格式错误！");
return;
}
Boy helper = first;
while (true) {
if (helper.getNext() == first) {
break;
}
helper = helper.getNext();
}
for (int i = 0; i < startNo - 1; i++) {
helper = helper.getNext();
first = first.getNext();
}
while (true) {
if (first == helper) {
break;
}
for (int i = 0; i < countNum - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
System.out.println("出圈的小孩编号：" + first.getNo());
first = first.getNext();
helper.setNext(first);
}
System.out.println("最后留下来的小孩的编号为：" + helper.getNo());
}
}
//创建一个Boy类,表示一个节点
class Boy {
private int no;
private Boy next;
public Boy(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
