链表¶
一、单链表¶
1、单链表概述¶
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含data域， next 域：指向下一个节点.
- 链表的各个节点不一定是连续存储
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确
2、面试题¶
1）有效节点个数¶
/**
* 有效节点个数（遍历+计数）
*/
public int usedNode() {
int ans = 0;
heroNode temp = head;
while (temp.next != null) {
ans++;
temp = temp.next;
}
return ans;
}
2）倒数第K个节点数据¶
/**
* 反向输出第k个节点
*/
public void oppoShow(int k) {
int all = usedNode();
heroNode temp = head.next;
if (all < k) {
System.out.printf("没有第%d个节点\n", k);
return;
}
int i = 1;
while (temp != null) {
if (i == (all - k + 1)) {
System.out.println(temp.toString());
break;
}
temp = temp.next;
i++;
}
}
3）反向遍历——迭代¶
/**
* 反向遍历
*/
public void oppoShow() {
if (head.next == null) {
System.out.println("链表为空");
return;
}
int all = usedNode();
for (int i = all; i >= 0; i--) {
int j = 1;
heroNode temp = head.next;
while (temp != null) {
if (j == i) {
System.out.println(temp.toString());
break;
}
j++;
temp = temp.next;
}
}
}
4）反向遍历——栈¶
class nodeStact {
int maxSize;
heroNode[] hn;
int top;
/**
* 栈的构造器
*
* @param maxSize 栈的大小
*/
nodeStact(int maxSize) {
this.maxSize = maxSize;
hn = new heroNode[maxSize];
top = -1;
}
/**
* 判空
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 判满
*/
public boolean isFull() {
return top == maxSize - 1;
}
/**
* 弹出
*/
public heroNode pop() {
if (isEmpty()) {
System.out.println("栈空");
return null;
}
return hn[top--];
}
/**
* 压栈
*/
public void push(heroNode _hn) {
if (isFull()) {
System.out.println("栈满");
} else {
hn[++top] = _hn;
}
}
}
/**
* 反向遍历——通过栈实现
*/
public void showByStack() {
if(head.next == null) {
System.out.println("链表为空");
return;
}
nodeStact ns = new nodeStact(usedNode());
heroNode temp = head.next;
while(temp != null) {
ns.push(temp);
temp = temp.next;
}
while(!ns.isEmpty()) {
System.out.println(ns.pop().toString());
}
}
5）合并单链表¶
/**
* 与demo合并
*/
public void mesh() {
singleLinkedList demo = new singleLinkedList();
demo.add(new heroNode(-1, "小明", "王哥"));
demo.add(new heroNode(0, "芭芭拉", "芭芭拉冲鸭"));
heroNode temp = demo.head.next;
while(temp != null) {
addByNo(new heroNode(temp.getNo(), temp.getName(), temp.getNickName()));
temp = temp.next;
}
}
3、代码实现¶
package work.rexhao.linkedlist;
import java.util.Scanner;
public class singleLinkedListDemo {
public static void main(String[] args) {
singleLinkedList sll = new singleLinkedList();
boolean loop = true;
while (loop) {
System.out.println("--------");
System.out.println("1.在尾部添加");
System.out.println("2.按编号添加");
System.out.println("3.遍历单链表");
System.out.println("4.修改节点");
System.out.println("5.删除节点");
System.out.println("6.有效节点个数");
System.out.println("7.反向输出");
System.out.println("8.反向遍历");
System.out.println("0.退出");
System.out.println("--------");
Scanner sc = new Scanner(System.in);
int key = sc.nextInt();
if (key == 1) {
System.out.println("请输入英雄编号：");
int no = sc.nextInt();
System.out.println("请输入英雄姓名：");
Scanner sc1 = new Scanner(System.in);
String name = sc1.nextLine();
System.out.println("请输入英雄昵称：");
Scanner sc2 = new Scanner(System.in);
String nickName = sc2.nextLine();
sll.add(new heroNode(no, name, nickName));
System.out.println("添加成功！");
} else if (key == 2) {
System.out.println("请输入英雄编号：");
int no = sc.nextInt();
System.out.println("请输入英雄姓名：");
Scanner sc1 = new Scanner(System.in);
String name = sc1.nextLine();
System.out.println("请输入英雄昵称：");
Scanner sc2 = new Scanner(System.in);
String nickName = sc2.nextLine();
sll.addByNo(new heroNode(no, name, nickName));
System.out.println("添加成功！");
} else if (key == 3) {
try {
sll.show();
} catch (Exception e) {
System.out.println(e.getMessage());
}
} else if (key == 4) {
System.out.println("请输入英雄编号：");
int no = sc.nextInt();
System.out.println("请输入英雄新的姓名：");
Scanner sc1 = new Scanner(System.in);
String name = sc1.nextLine();
System.out.println("请输入英雄新的昵称：");
Scanner sc2 = new Scanner(System.in);
String nickName = sc2.nextLine();
sll.change(no, name, nickName);
} else if (key == 5) {
System.out.println("请输入英雄编号：");
int no = sc.nextInt();
sll.delete(no);
} else if (key == 6) {
System.out.println("有效节点个数：" + sll.usedNode());
} else if (key == 7) {
int k = sc.nextInt();
sll.oppoShow(k);
} else if (key == 8) {
System.out.println("通过反向遍历实现：");
sll.oppoShow();
System.out.println("通过栈实现：");
sll.showByStack();
} else if (key == 9) {
System.out.println("与demo链表合并");
sll.mesh();
} else if (key == 0) {
loop = false;
} else {
System.out.println("输入有误！");
}
}
}
}
/**
* 管理英雄
*/
class singleLinkedList {
/**
* 定义一个头结点
*/
private heroNode head = new heroNode(0, "", "");
/**
* 添加节点的方法(尾插法) 将最后的next域指向新的node
*/
public void add(heroNode hn) {
// 需要一个辅助变量
heroNode temp = head;
// 遍历单链表
while (temp.next != null) {
temp = temp.next;
}
// 退出循环时，temp指向最后
temp.next = hn;
}
/**
* 按照编号大小添加
*
* @param hn
*/
public void addByNo(heroNode hn) {
/**
* 空链表：直接放后面
*/
if (head.next == null) {
head.next = hn;
return;
}
heroNode temp = head.next;
/**
* 如果只有一个节点，且大于hn
*/
if (hn.getNo() < temp.getNo()) {
head.next = hn;
hn.next = temp;
return;
}
while (true) {
/**
* 如果no相等：报错
*/
if (hn.getNo() == temp.getNo()) {
throw new RuntimeException("编号重复！");
}
if (temp.next != null) {
if (hn.getNo() == temp.next.getNo()) {
throw new RuntimeException("编号重复！");
}
}
/**
* 找到：大于前一个节点且（小于后一个节点或者后一个节点为null）的节点
*/
if (hn.getNo() > temp.getNo() && (temp.next == null || hn.getNo() < temp.next.getNo())) {
hn.next = temp.next;
temp.next = hn;
break;
}
if (temp.next != null) {
temp = temp.next;
} else {
break;
}
}
}
/**
* 遍历
*/
public void show() {
// 判空
if (head.next == null) {
throw new RuntimeException("链表为空");
}
// 遍历
heroNode temp = head.next;
while (temp != null) {
System.out.println(temp.toString());
temp = temp.next;
}
}
/**
* 修改节点
*/
public void change(int no, String name, String nickName) {
// 判空
if (head.next == null) {
System.out.println("链表为空");
return;
}
// 遍历：找no节点
heroNode temp = head.next;
while (temp != null) {
if (temp.getNo() == no) {
temp.setName(name);
temp.setNickName(nickName);
System.out.println("修改成功！");
return;
}
temp = temp.next;
}
System.out.printf("未找到编号为%d的节点\n", no);
return;
}
/**
* 删除节点
*/
public void delete(int no) {
// 判空
if (head.next == null) {
System.out.println("链表为空");
return;
}
// 遍历找节点
heroNode temp = head;
while (temp.next != null) {
if (temp.next.getNo() == no) {
temp.next = temp.next.next;
System.out.println("删除成功");
return;
}
temp = temp.next;
}
System.out.printf("未找到编号为%d的节点\n", no);
return;
}
/**
* 有效节点个数（遍历+计数）
*/
public int usedNode() {
int ans = 0;
heroNode temp = head;
while (temp.next != null) {
ans++;
temp = temp.next;
}
return ans;
}
/**
* 反向输出第k个节点
*/
public void oppoShow(int k) {
int all = usedNode();
heroNode temp = head.next;
if (all < k) {
System.out.printf("没有第%d个节点\n", k);
return;
}
int i = 1;
while (temp != null) {
if (i == (all - k + 1)) {
System.out.println(temp.toString());
break;
}
temp = temp.next;
i++;
}
return;
}
/**
* 反向遍历——翻转单链表
*/
public void oppoShow() {
if (head.next == null) {
System.out.println("链表为空");
return;
}
int all = usedNode();
for (int i = all; i >= 0; i--) {
int j = 1;
heroNode temp = head.next;
while (temp != null) {
if (j == i) {
System.out.println(temp.toString());
break;
}
j++;
temp = temp.next;
}
}
}
/**
* 反向遍历——通过栈实现
*/
public void showByStack() {
if (head.next == null) {
System.out.println("链表为空");
return;
}
nodeStact ns = new nodeStact(usedNode());
heroNode temp = head.next;
while (temp != null) {
ns.push(temp);
temp = temp.next;
}
while (!ns.isEmpty()) {
System.out.println(ns.pop().toString());
}
}
/**
* 与demo合并
*/
public void mesh() {
singleLinkedList demo = new singleLinkedList();
demo.add(new heroNode(-1, "小明", "王哥"));
demo.add(new heroNode(0, "芭芭拉", "芭芭拉冲鸭"));
heroNode temp = demo.head.next;
while(temp != null) {
addByNo(new heroNode(temp.getNo(), temp.getName(), temp.getNickName()));
temp = temp.next;
}
}
}
/**
* 定义heroNode节点
*/
class heroNode {
private int no;
private String name;
private String nickName;
public heroNode next;
/**
* 构造器
*
* @param no 编号
* @param name 姓名
* @param nickName 昵称
*/
heroNode(int no, String name, String nickName) {
this.name = name;
this.no = no;
this.nickName = nickName;
}
/**
* 重写toString
*/
@Override
public String toString() {
return "[no=" + no + ", name=" + name + ", nickName=" + nickName + ", next=" + next + "]";
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getNickName() {
return nickName;
}
public void setNickName(String nickName) {
this.nickName = nickName;
}
}
class nodeStact {
int maxSize;
heroNode[] hn;
int top;
/**
* 栈的构造器
*
* @param maxSize 栈的大小
*/
nodeStact(int maxSize) {
this.maxSize = maxSize;
hn = new heroNode[maxSize];
top = -1;
}
/**
* 判空
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 判满
*/
public boolean isFull() {
return top == maxSize - 1;
}
/**
* 弹出
*/
public heroNode pop() {
if (isEmpty()) {
System.out.println("栈空");
return null;
}
return hn[top--];
}
/**
* 压栈
*/
public void push(heroNode _hn) {
if (isFull()) {
System.out.println("栈满");
} else {
hn[++top] = _hn;
}
}
}
二、双向链表¶
1、双向链表概述¶
- 遍历方法和单链表一样，不仅可以向前，也可以向后查找
- 添加（默认添加到双向链表的最后)
- 先找到双向链表的最后这个节点
- temp.next = newHeroNode
- newHeroNode.pre=temp;
- 修改：思路和原来的单向链表一样
- 删除
- 双向链表可以实现自我删除某个节点
- 直接找到要州除的这个节点，比如 temp
- temp.pre.next =temp.next
- temp.next. pre = temp.pre;
2、代码实现¶
package work.rexhao.linkedlist;
import java.util.Scanner;
public class doubleLinkedListDemo {
public static void main(String[] args) {
doubleLinkedList dll = new doubleLinkedList();
boolean loop = true;
while (loop) {
System.out.println("--------");
System.out.println("1.在尾部添加");
System.out.println("2.按编号添加");
System.out.println("3.遍历双向链表");
System.out.println("4.修改节点");
System.out.println("5.删除节点");
System.out.println("6.有效节点个数");
System.out.println("0.退出");
System.out.println("--------");
Scanner sc = new Scanner(System.in);
int key = sc.nextInt();
if (key == 1) {
System.out.println("请输入学生编号：");
int no = sc.nextInt();
System.out.println("请输入学生姓名：");
Scanner sc1 = new Scanner(System.in);
String name = sc1.nextLine();
dll.add(new stuNode(no, name));
System.out.println("添加成功！");
} else if (key == 2) {
System.out.println("请输入学生编号：");
int no = sc.nextInt();
System.out.println("请输入学生姓名：");
Scanner sc1 = new Scanner(System.in);
String name = sc1.nextLine();
dll.addByNo(new stuNode(no, name));
System.out.println("添加成功！");
} else if (key == 3) {
dll.show();
} else if (key == 4) {
System.out.println("请输入学生编号：");
int no = sc.nextInt();
System.out.println("请输入学生新的姓名：");
Scanner sc1 = new Scanner(System.in);
String name = sc1.nextLine();
dll.change(new stuNode(no, name));
} else if (key == 5) {
System.out.println("请输入学生编号：");
int no = sc.nextInt();
dll.delete(no);
} else if (key == 6) {
System.out.println("有效节点个数：" + dll.usedNode());
} else if (key == 0) {
loop = false;
} else {
System.out.println("输入有误！");
}
}
}
}
/**
* 双向链表
*/
class doubleLinkedList {
private stuNode head = new stuNode(0, "wmh");
/**
* 有效节点数
*/
public int usedNode() {
int ans = 0;
stuNode temp = head.next;
while (temp != null) {
ans++;
temp = temp.next;
}
return ans;
}
/**
* 插入
*/
public void add(stuNode sn) {
if (head.next == null) {
head.next = sn;
sn.pre = head;
return;
}
stuNode temp = head.next;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = sn;
sn.pre = temp;
}
/**
* 遍历
*/
public void show() {
if (head.next == null) {
System.out.println("单链表为空");
return;
}
stuNode temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
/**
* 修改
*/
public void change(stuNode sn) {
if (head.next == null) {
System.out.println("单链表为空");
return;
}
stuNode temp = head.next;
while (temp != null) {
if (temp.getNo() == sn.getNo()) {
temp.setName(sn.getName());
temp.setNo(sn.getNo());
return;
}
temp = temp.next;
}
System.out.printf("未找到no=%d的节点\n", sn.getNo());
}
/**
* 自我删除
*/
public void delete(int no) {
if (head.next == null) {
System.out.println("链表为空");
return;
}
stuNode temp = head.next;
while (temp != null) {
if (temp.getNo() == no) {
/*
* 找到了
*/
temp.pre.next = temp.next;
if (temp.next != null) {
temp.next.pre = temp.pre;
}
return;
}
temp = temp.next;
}
System.out.printf("未找到no=%d的节点\n", no);
}
/**
* 按照编号添加
*/
public void addByNo(stuNode sn) {
/*
* 判空
*/
if (head.next == null) {
head.next = sn;
sn.pre = head;
return;
}
/*
* 判同
*/
stuNode temp = head.next;
while (temp != null) {
if (temp.getNo() == sn.getNo()) {
System.out.println("编号相同");
return;
}
temp = temp.next;
}
/*
* 找位置添加——第一个位置
*/
if (sn.getNo() < head.next.getNo()) {
sn.next = head.next;
head.next = sn;
sn.pre = head;
sn.next.pre = sn;
return;
}
/*
* 找位置添加——不是第一个位置
*/
temp = head.next;
while (temp != null) {
if (temp.next == null) {
temp.next = sn;
sn.pre = temp;
return;
}
if (temp.getNo() < sn.getNo() && temp.next.getNo() > sn.getNo()) {
sn.next = temp.next;
temp.next = sn;
sn.pre = head;
sn.next.pre = sn;
return;
}
temp = temp.next;
}
}
}
/**
* 定义stuNode节点
*/
class stuNode {
private int no;
private String name;
public stuNode next;
public stuNode pre;
/**
* 构造器
*
* @param no 编号
* @param name 姓名
*/
stuNode(int no, String name) {
this.name = name;
this.no = no;
}
public int getNo() {
return no;
}
/**
* 重写toString
*/
@Override
public String toString() {
return "[no=" + no + ", name=" + name + "]";
// 使用双向链表，不能打印next和pre
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
三、单项循环链表与Josepfu问题¶
1、约瑟夫环概述¶
设编号为1,2,⋯n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
2、解决思想¶
用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有口个结点的单循环链表，然后由k结点起从1 开始计数，计到 m 时，对应结点从链表中州除，然后再从被删除结点的下一个结点又从1 开始计数，到最后一个结点从链表中删除算法结束。
3、代码实现¶
package work.rexhao.linkedlist;
import java.util.Scanner;
public class JosepfuDemo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("总人数:");
int n = sc.nextInt();
System.out.print("报号数:");
int k = sc.nextInt();
Josepfu(n, k);
}
/**
* Josepfu问题
*
* @param n 人数
* @param k 报号数
*/
public static void Josepfu(int n, int k) {
circleSingleLinkedList csll = new circleSingleLinkedList();
for(int i = 1; i <= n; i++) {
csll.add(new Node(i));
}
Node temp = csll.head;
int j = 1;
while(csll.usedNode() != 1) {
if(j == k) {
csll.delete(temp.getNum());
j = 1;
temp = temp.next;
continue;
}
j++;
temp = temp.next;
}
csll.show();
}
}
class circleSingleLinkedList {
public Node head = null;
/**
* 添加节点
*/
public void add(Node n) {
/*
* 空链表，直接放后面
*/
if (head == null) {
head = n;
n.next = head;
return;
}
/*
* 非空，遍历加在后面
*/
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = n;
n.next = head;
}
/**
* 遍历
*/
public void show() {
Node temp = head;
boolean loop = true;
while (loop) {
System.out.println(temp);
temp = temp.next;
if (temp == head) {
loop = false;
}
}
}
/**
* 有效元素
*/
public int usedNode() {
if (head == null) {
return 0;
}
if (head.next == head) {
return 1;
}
Node temp = head;
int ans = 1;
while (temp.next != head) {
temp = temp.next;
ans++;
}
return ans;
}
/**
* 删除节点
*/
public void delete(int num) {
/*
* 判空
*/
if (head == null) {
System.out.println("链表为空");
return;
}
/*
* 删除head节点
*/
if (head.getNum() == num) {
if (head.next == head) {
/*
* 只有一个head
*/
head = null;
} else {
/*
* 还有其他节点
*/
// 1.改最后的next
Node temp = head;
while (true) {
if (temp.next == head) {
temp.next = head.next;
break;
}
temp = temp.next;
}
// 2.改head
head = head.next;
}
return;
}
/*
* 删除其他的节点
*/
Node temp = head.next;
while (true) {
if (temp.next.getNum() == num) {
temp.next = temp.next.next;
return;
}
temp = temp.next;
}
}
}
class Node {
private int num;
public Node next;
Node(int num, Node next) {
this.num = num;
this.next = next;
}
Node(int num) {
this.num = num;
this.next = null;
}
@Override
public String toString() {
return "Node[num=" + num + "]";
}
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
}