2.代码
1.单链表
1.基本介绍
1.定义
2.逻辑结构
2.应用实例
1.需求分析
2.思路分析
3.完成添加和显示链表信息，直接添加到链表的尾部
package com.sun.linkedlist;
import java.util.Scanner;
/**
* @author 孙显圣
* @version 1.0
*/
class Test {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
//添加几条记录
Node node1 = new Node(1, "李白", "青莲剑歌");
Node node2 = new Node(2, "杜甫", "青莲剑歌");
Node node3 = new Node(3, "周瑜", "青莲剑歌");
Node node4 = new Node(4, "诸葛亮", "青莲剑歌");
singleLinkedList.add(node2);
singleLinkedList.add(node1);
singleLinkedList.add(node4);
singleLinkedList.add(node3);
boolean flag = true;
while (flag) {
System.out.println("1：显示，2：入队，3：出队，4：退出");
Scanner scanner = new Scanner(System.in);
int cmd = scanner.nextInt();
switch (cmd) {
case 1:
singleLinkedList.list();
break;
case 2:
System.out.println("请输入要添加的数据：");
System.out.println("编号：");
int no = scanner.nextInt();
System.out.println("姓名：");
String name = scanner.next();
System.out.println("技能");
String skill = scanner.next();
Node node = new Node(no, name, skill);
singleLinkedList.add(node);
System.out.println("添加成功！");
break;
case 3:
break;
case 4:
flag = false;
System.out.println("退出系统");
}
}
}
}
//用来管理节点
public class SingleLinkedList {
//头结点，指向第一个元素
private Node head = new Node();
//添加节点
public void add(Node node) {
//遍历链表直到最后，然后添加节点
//由于头结点不能动，所以需要一个辅助节点来遍历
Node temp = head;
while (true) {
//只要临时节点的下一个节点不为空，就将临时节点向后移动
if (temp.next != null) {
//节点向后移动
temp = temp.next;
continue;
}
//当临时节点的下一个节点为空，则添加一个数据，然后退出循环
temp.next = node;
break;
}
}
//遍历链表，显示信息
public void list() {
//临时节点指向头结点
Node temp = head;
while (temp.next != null) {
//显示节点信息
System.out.println(temp.next);
temp = temp.next;
}
}
}
//编写一个节点类型，每一个对象即为一个节点
class Node {
//数据域
public int no;
public String name;
public String skill;
//next域，指向下一个节点
public Node next;
public Node() {
}
public Node(int no, String name, String skill) {
this.no = no;
this.name = name;
this.skill = skill;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
", skill='" + skill + '\'' +
'}';
}
}
4.根据排名添加，如果排名重复则给出提示
//按照顺序添加节点
public void addBySequential(Node node) {
//辅助节点
Node temp = head;
//遍历节点
//只要下一个数不等于空并并且下一个数比当前数要小，则一定不是要插入的位置，所以向后移动
while (temp.next != null && temp.next.no
temp = temp.next;
}
//只要出了循环就表示，下一个数是空或者下一个数大于当前的数，可以插入
node.next = temp.next;
temp.next = node;
}
//根据id来查找到链表的那个节点
//临时节点指向头结点
Node temp = head;
//只要下一个元素不为空就进入循环
while (temp.next != null) {
//如果符合条件，就修改这个节点的值
if (temp.next.no == newNode.no) {
//修改节点的值
temp.next.name = newNode.name;
temp.next.skill = newNode.skill;
System.out.println("修改成功！修改后的节点信息为：" + temp.next);
break;
}
//只要不符合条件就一直走
temp = temp.next;
}
}
//找到指定编号的节点的前一个位置
Node temp = head;
//只要没有找到指定no的节点就往后走
while (temp.next != null) {
if (temp.next.no == no) {
//删除temp的下一个节点
temp.next = temp.next.next;
System.out.println("节点" + no + "删除成功！");
break;
}
temp = temp.next;
}
}
// 根据头结点遍历即可
// 临时节点
Node temp = head;
int length = 0; // 初始化长度为0
// 只要临时节点的下一个节点不为空，则说明有一个有效节点，所以长度++
while (temp.next != null) {
length++;
temp = temp.next;
}
return length;
}
// 得到有效节点的数量
int length = getLength(head);
if (tail length) {
throw new RuntimeException("输入有误！");
}
// 计算是正数第几个节点
int index = length - tail + 1;
// 遍历得到正数第index个节点
Node temp = head;
int temp_index = 0; // 记录是第几个节点
while (temp.next != null) {
temp_index++;
if (temp_index == index) {
return temp.next;
}
temp = temp.next;
}
return null;
}
3.面试题三
// 3.单链表反转
public void linkedListInversion(Node head) {
// 排除零个节点和一个节点的情况
if (head.next == null || head.next.next == null) {
return;
}
// 临时指针一
Node temp1 = head.next;
// 临时指针二
Node temp2 = new Node();
// 反转链表的一个临时节点
Node reverseHead = new Node();
// 使用双指针遍历单链表
while (temp1 != null) {
// 让第二个指针指向第一个指针的后面
if (temp1.next != null) {
temp2 = temp1.next;
} else {
// 如果第一个指针的下一个位置为空，则让第二个指针指向null，这样移动完一个节点之后第一个指针就会指向第二个指针也就是空，可以退出循环
temp2 = null;
}
// 将temp1指向的节点接入到reverseHead后面
temp1.next = reverseHead.next;
reverseHead.next = temp1;
// 利用第二个指针移动temp1
temp1 = temp2;
}
// 反转成功之后让head节点指向第一个节点
head.next = reverseHead.next;
}
4.面试题四
// 4，从尾到头打印单链表
public void reversePrint(Node head) {
// 只要链表没有元素就直接return
if (head.next == null) {
return;
}
// 创建一个栈
Stack stack = new Stack();
// 将各个节点依次压入栈中
Node temp = head.next;
while (temp != null) {
stack.push(temp);
temp = temp.next;
}
// 取出栈中的元素
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
2.双向链表
1.增删改查分析图解
2.代码实现
package com.sun.linkedlist;
/**
* Description: 双向链表
*
* @Author sun
* @Create 2024/3/28 20:53
* @Version 1.0
*/
// 双向链表方法的测试
class DoubleLinkedListDemoTest {
public static void main(String[] args) {
// 创建一个双向链表
DoubleLinkedListDemo doubleLinkedListDemo = new DoubleLinkedListDemo();
// 创建几个节点
Node2 node1 = new Node2(1, "李白", "青莲剑歌");
Node2 node2 = new Node2(2, "杜甫", "青莲剑歌");
Node2 node3 = new Node2(3, "周瑜", "青莲剑歌");
Node2 node4 = new Node2(4, "诸葛亮", "青莲剑歌");
// 添加节点
doubleLinkedListDemo.add(node1);
doubleLinkedListDemo.add(node2);
doubleLinkedListDemo.add(node3);
doubleLinkedListDemo.add(node4);
// 遍历
doubleLinkedListDemo.list();
// 修改节点
Node2 updateNode = new Node2(4, "4", "4");
doubleLinkedListDemo.update(updateNode);
// 删除节点
doubleLinkedListDemo.del(4);
// 遍历
doubleLinkedListDemo.list();
System.out.println("====================================");
// 把编号打乱，测试按照编号添加的方法
Node2 node5 = new Node2(5, "5", "5");
Node2 node6 = new Node2(6, "6", "6");
Node2 node7 = new Node2(7, "7", "7");
Node2 node8 = new Node2(8, "8", "8");
// 从node8逆序添加
doubleLinkedListDemo.insertByOrder(node8);
doubleLinkedListDemo.insertByOrder(node7);
doubleLinkedListDemo.insertByOrder(node6);
doubleLinkedListDemo.insertByOrder(node5);
// 遍历
doubleLinkedListDemo.list();
}
}
public class DoubleLinkedListDemo {
// 初始化双向链表
// 头结点，指向第一个元素
private Node2 head = new Node2(-1, "", "");
public Node2 getHead() {
return head;
}
// 遍历的方法与单向链表相同
public void list() {
// 判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
// 临时节点
Node2 temp = head.next;
// 只要临时节点不为空，就输出当前节点信息，然后向后移动
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
// 添加节点
public void add(Node2 node2) {
// 临时节点
Node2 temp = head;
// 首先遍历找到最后一个节点
while (temp.next != null) {
temp = temp.next;
}
// 目前temp 指向了最后一个节点
temp.next = node2;
node2.pre = temp;
}
// 修改节点，跟单向链表一致
public void update(Node2 newNode) {
// 根据id来查找到链表的那个节点
// 临时节点指向头结点
Node2 temp = head;
// 只要下一个元素不为空就进入循环
while (temp.next != null) {
// 如果符合条件，就修改这个节点的值
if (temp.next.no == newNode.no) {
// 修改节点的值
temp.next.name = newNode.name;
temp.next.skill = newNode.skill;
System.out.println("修改成功！修改后的节点信息为：" + temp.next);
break;
}
// 只要不符合条件就一直走
temp = temp.next;
}
}
// 从双向链表中删除节点，首先找到要删除的节点，然后自我删除即可
// 删除指定id的节点
public void del(int no) {
// 首先判断链表是否为空
if (head.next == null) {
System.out.println("链表为空，不能删除");
return;
}
// 临时节点指向第一个节点（这是因为第一个节点不为空才能这样）
Node2 temp = head.next;
// 只要没有找到指定no的节点就往后走
while (temp != null) {
// 判断是否是要找的节点
if (temp.no == no) {
// 执行自我删除
temp.pre.next = temp.next;
if (temp.next != null) {
// 这里如果temp指向了最后一个元素，则不执行，否则会报
temp.next.pre = temp.pre;
}
System.out.println("节点" + no + "删除成功！");
break;
}
// 后移
temp = temp.next;
}
}
// 按照编号顺序来添加
public void insertByOrder(Node2 newNode) {
// 临时节点
Node2 temp = head;
// 只要临时节点的下一个节点不为空，并且no比新节点要小，就继续走
while (temp.next != null && temp.next.no = newNode.no
// 如果下一个元素为空，则直接插入到temp的后面
if (temp.next == null) {
temp.next = newNode;
newNode.pre = temp;
return;
}
// 剩下的情况就是下一个元素不为空，则插入到temp跟下一个元素之间
// 先插后面
temp.next.pre = newNode;
newNode.next = temp.next;
// 再插前面
temp.next = newNode;
newNode.pre = temp;
}
}
// 编写一个节点类型，每一个对象即为一个节点
class Node2 {
// 数据域
public int no;
public String name;
public String skill;
// next域，指向下一个节点
public Node2 next;
public Node2 pre;
public Node2() {
}
public Node2(int no, String name, String skill) {
this.no = no;
this.name = name;
this.skill = skill;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
", skill='" + skill + '\'' +
'}';
}
}
3.单向环形链表
1.题目
2.思路分析
3.首先构建一个环形链表
1.思路分析
2.代码
package com.sun.linkedlist;
/**
* Description:
*
* @Author sun
* @Create 2024/3/29 21:39
* @Version 1.0
*/
public class Josephu {
private Boy first = null;
public static void main(String[] args) {
Josephu josephu = new Josephu();
josephu.addBoy(3);
josephu.show();
}
/**
* 根据数量添加小孩
* @param nums
*/
public void addBoy(int nums) {
// 数据校验
if (nums
