学习链表必备的1w个技巧Java版本

链表（Java版本）

关于作者

• 作者介绍

🍓 博客主页：作者主页
🍓 简介：JAVA领域优质创作者🥇、一名初入职场小白🎓、曾在校期间参加各种省赛、国赛，斩获一系列荣誉🏆
🍓 关注我：关注我学习资料、文档下载统统都有，每日定时更新文章，励志做一名JAVA资深程序猿👨‍💻

简介

链表是有序的列表，但是它在内存中是存储如下

​ 1.链表是以节点的方式来存储，是链式存储

​ 2.每个节点包含 data 域， next 域：指向下一个节点.

​ 3.发现链表的各个节点不一定是连续存储

​ 4.链表分为带头节点的链表和没有头节点的链表，根据实际的需求来确定

单链表（带头节点）

实例

使用带 head 头的单向链表实现—学生信息管理完成对学生信息的增删改查操作

思路

添加

直接添加到链表的尾部

在添加信息时，根据编号将学生信息插入到指定位置(如果存在这个编号，则添加失败，并给出提示

思路的分析示意图:

修改

修改节点的信息, 根据 no 编号来修改，即 no 编号不能改.

删除

代码

package com.cz.LinkedList;
 
import java.util.Stack;
 
/**
 * @ProjectName: Data_structure
 * @Package: com.cz.LinkedList
 * @ClassName: SingleLinkedListDemo
 * @Author: 张晟睿
 * @Date: 2022/2/24 10:32
 * @Version: 1.0
 */
public class SingleLinkedListDemo {
    public static void main(String []args){
        NodeList list = new NodeList(0,"zrq",20,"软工1班");
        NodeList list1 = new NodeList(1,"zrq1",21,"软工2班");
//        NodeList list2 = new NodeList(2,"zrq2",22,"软工3班");
//        NodeList list3 = new NodeList(3,"zrq3",23,"软工4班");
        NodeList list4 = new NodeList(2,"zrq4",24,"软工5班");
        NodeList list5 = new NodeList(5,"sss",21,"软工1班");
 
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList1.add(list);
        singleLinkedList1.add(list1);
//        singleLinkedList1.addByOrder(list2);
//        singleLinkedList1.addByOrder(list3);
 
        singleLinkedList2.add(list4);
        singleLinkedList2.add(list5);
        singleLinkedList2.list();
        System.out.println("+++++");
        System.out.println(list4.next);
        System.out.println("+++++");
 
//        singleLinkedList.reversalNode(singleLinkedList.getHead());
//
//        singleLinkedList.list();
//        singleLinkedList.reversePrint(singleLinkedList.getHead());
//        singleLinkedList.add(list4);
 
//        singleLinkedList.delete(list4.sno);
//
//        singleLinkedList.update(list5);
//
//        singleLinkedList.list();
//
//        System.out.println("链表的有效数据个数为："+ singleLinkedList.size());
//
//        //测试查找单链表中倒数第k个节点
//        NodeList lastIndexNode = singleLinkedList.findLastIndexNode(singleLinkedList.getHead(), 4);
//        System.out.println(lastIndexNode);
 
//        singleLinkedList.reversalNode(singleLinkedList.getHead());
 
        singleLinkedList1.mergeNode(singleLinkedList1.getHead(), singleLinkedList2.getHead());
    }
}
//管理Node节点
class SingleLinkedList{
    //初始化头节点
    private NodeList head = new NodeList(0,"",0,"");
 
    public void setHead(NodeList head) {
        this.head = head;
    }
 
    public NodeList getHead() {
        return head;
    }
 
    //统计有效的节点个数
    public int size(){
        //链表为空 则返回长度0
        if (head.next == null) return 0;
        //定义一个辅助来记录当前的节点
        NodeList temp = head.next;
        int count = 0;//统计节点个数
        while(temp != null){
            count++;
            temp = temp.next;
        }
        return count;
    }
    //向节点中添加数据
    //思路，当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的 next 指向 新的节
    public void add(NodeList nodeList){
        NodeList temp = head;
        while(true){
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        //退出循环时，链表指向最后
        temp.next = nodeList;
    }
 
 
 
 
    //向节点中添加数据并排序
    //思路，当考虑编号顺序时
    //1. 找到当前链表与当前链表的后一个节点的sno编号进行比较
    //2. 将最后这个节点的 next 指向 新的节
    public void addByOrder(NodeList nodeList){
        boolean flag = false;//判断是否已经存在该排名
        NodeList temp = head;
        while(true) {
            //判断是否到达链表尾部
            if (temp.next == null) {
                break;
            }
            //判断插入的节点与后一个节点的sno的大小
            if (temp.next.sno > nodeList.sno) {
                break;//此时找到插入的位置在temp的后面
            } else if (temp.next.sno == nodeList.sno) {
                flag = true; //说明编号存在
                break;
            }
            temp = temp.next;
        }
            if (flag) {
                System.out.println("该编号已存在，请重新输入");
            } else {
                nodeList.next = temp.next;
                temp.next = nodeList;
            }
    }
    //显示节点中的所有对象
    public void list(){
        //判断节点是否为空
        if(head.next == null){
            return;
        }
        NodeList temp = head.next;
        while(true){
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
 
 
    //修改节点的信息, 根据 no 编号来修改，即 no 编号不能改.
    //1. 根据 newHeroNode 的 no 来修改即可
    //2. 说明我们在比较时，需要查找当前节点是否存在 如果存在才能进行修改
    public void update(NodeList nodeList){
        //标记是否找到该节点
        int flag = 0;
        //头节点不能动
        if (head.next == null) return ;//链表是否为空
        NodeList temp = head.next;
        while(true) {
            if (temp == null)//判断是否到达链表尾部
            {
                break;
            }
            if (nodeList.sno == temp.sno) {
                //找到该节点
                flag = 1;
                break;
            }
            temp = temp.next;
        }
            if (flag == 1){
                temp.setSno(nodeList.sno);
                temp.setName(nodeList.name);
                temp.setAge(nodeList.age);
                temp.setGrade(nodeList.grade);
            }else
                System.out.printf("要修改的 %d 节点不存在，无发修改n", nodeList.sno);
    }
 
//    删除节点
//    思路
//    1. head 不能动，因此我们需要一个 temp 辅助节点找到待删除节点的前一个节点
//    2. 说明我们在比较时，是 temp.next.sno 和 需要删除的节点的 sno 比较
    public void delete(int sno){
        //用来标记是否找到该节点 0是为找到  1为找到
        int flag = 0;
        //头节点不能动
        NodeList temp = head;
        //判断节点是否为空
        if(head.next == null){
            return;
        }
        while(true){
            //判断节点是否到达末尾
            if (temp.next == null){
                break;
            }
            //删除的链表号是否被找到
            if (temp.next.sno == sno) {
                flag = 1;break;
            }
            temp = temp.next;//当前节点指向后一个节点
        }
        //找到该节点后  判断该节点的尾指针指向下一个节点
        if (flag == 1){
            temp.next = temp.next.next;
        }else
            System.out.printf("要删除的 %d 节点不存在n", sno);
    }
 
}
 
//定义Node 每个Node都是一个对象
class NodeList{
    public int sno;
    public String name;
    public int age;
    public String grade;
    public NodeList next;
 
    public NodeList(int sno, String name, int age, String grade) {
        this.sno = sno;
        this.name = name;
        this.age = age;
        this.grade = grade;
    }
 
    public void setSno(int sno) {
        this.sno = sno;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public void setAge(int age) {
        this.age = age;
    }
 
    public void setGrade(String grade) {
        this.grade = grade;
    }
 
    public void setNext(NodeList next) {
        this.next = next;
    }
 
    @Override
    public String toString() {
        return "Student{" +
                "sno=" + sno +
                ", name='" + name + ''' +
                ", age=" + age +
                ", grade='" + grade + ''' +
                '}';
    }
}
 

单链表常见的几种类型的问题

​ 1.求单链表中有效节点的个数

//统计有效的节点个数
    public int size(){
        //链表为空 则返回长度0
        if (head.next == null) return 0;
        //定义一个辅助来记录当前的节点
        NodeList temp = head.next;
        int count = 0;//统计节点个数
        while(temp != null){
            count++;
            temp = temp.next;
        }
        return count;
    }

​ 2.查找单 链表中的倒数第k个结点

//查找单链表中倒数第k个节点
    //思路
    //先把链表全部遍历一遍得到链表的长度，从链表的第一个节点开始，查找length - k 就可以得到该节点的数据
    //例如 length=3 k=1  我们所需要循环2次就可以找到该节点
 
    /**
     *
     * @param head  链表的头节点
     * @param index 倒数第k个节点
     * @return 倒数第k个节点的链表内容
     */
    public NodeList findLastIndexNode(NodeList head, int index){
        //判断链表是否为空
        if(head.next == null) return null;
        NodeList temp = head.next;
        for (int i = 0; i < size() - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

​ 3.单链表的反转

//链表反转
    public void reversalNode(NodeList head){
        if (head.next == null || head.next.next == null){
            System.out.println("链表为空！");return ;
        }
        NodeList cur = head.next;//用cur来记录当前的node节点
        NodeList next = null;//用来记录cur的下一个节点
        NodeList reversalHead = new NodeList(0,"",0,"");//用来记录reversal节点
        while(cur != null){
            next = cur.next;
            cur.next = reversalHead.next;//将 cur 的下一个节点指向新的链表的最前端
            reversalHead.next = cur; //将 cur 连接到新的链表上
            cur = next;//让 cur 后移
        }
        //将 head.next 指向 reverseHead.next , 实现单链表的反转
        head.next = reversalHead.next;
    }

​ 这里可能有两行代码很难理解

cur.next = reversalHead.next;//将 cur 的下一个节点指向新的链表的最前端
reversalHead.next = cur; //将 cur 连接到新的链表上

​ 4.从尾到头打印单链表 [要求方式1:反向遍历。方式2: Stack栈]

//从尾到头打印单链表 【百度，要求方式 1：反向遍历 。 方式 2：Stack 栈
    public void reversePrint(NodeList head){
        //判断链表是否为空
        if (head.next == null) return ;
        //创建要给一个栈，将各个节点压入栈
        Stack stack = new Stack();
        NodeList cur = head.next;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        while(stack.size()>0){
            System.out.println(stack.pop());
        }
    }

​ 5.合并两个有序的单链表，合并之后的链表依然有序

public void mergeNode(NodeList head1, NodeList head2){
        //定义一个心链表
        NodeList newnode = new NodeList(0,"",0,"");
        //定义新链表的表头
        NodeList temp = newnode;
        //判断链表的个数如果链表为空返回另一链表内容
        if(head1.next == null) newnode = head2;
        if(head2.next == null) newnode = head1;
        NodeList cur1 = head1.next;
        NodeList cur2 = head2.next;
 
        //判断链表的sno大小 ，将链表的下一个节点指向所需要的指向的节点
        while(cur1 != null && cur2 != null){
            if(cur1.sno > cur2.sno){
                newnode.next = cur2;
                cur2 = cur2.next;
            }else{
                newnode.next = cur1;
                cur1 = cur1.next;
            }
            newnode = newnode.next;
        }
        //判断完成后，如果该cur1节点为空 将剩余的cur2链表的内容通过newnode指向cur2
        if (cur1 == null) newnode.next = cur2;
        if (cur2 == null) newnode.next = cur1;
        while(temp.next!=null){
            temp = temp.next;
            System.out.println(temp);
        }
    }

双向链表（带头结点）

管理单向链表的缺点分析

• 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
• 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点总是找到 temp,temp 是待删除节点的前一个节点。
• 分析了双向链表如何完成遍历，添加，修改和删除的思路。

思路

遍历

和单链表一样，只是可以向前，也可以向后查找

添加 (默认添加到双向链表的最后)

修改

和单向链表一样。

删除

(1) 因为是双向链表，因此，我们可以实现自我删除某个节点

(2) 直接找到要删除的这个节点，比如temp

(3) temp.pre.next = temp.next

(4) temp.next.pre = temp.pre;

代码

package com.cz.LinkedList;
 
/**
 * @ProjectName: Data_structure
 * @Package: com.cz.LinkedList
 * @ClassName: DoubleLinkedListDemo
 * @Author: 张晟睿
 * @Date: 2022/2/26 18:33
 * @Version: 1.0
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLinedList doubleLinedList = new DoubleLinedList();
        NodePoint nodePoint1 = new NodePoint(1,"孙悟空",19,"西游记");
        NodePoint nodePoint2 = new NodePoint(2,"唐僧",17,"西游记");
        NodePoint nodePoint3 = new NodePoint(3,"猪八戒",26,"西游记");
        NodePoint nodePoint4 = new NodePoint(4,"沙悟净",30,"西游记");
        NodePoint nodePoint5 = new NodePoint(4,"白骨精",32,"西游记");
        doubleLinedList.add(nodePoint1);
        doubleLinedList.add(nodePoint2);
        doubleLinedList.add(nodePoint3);
        doubleLinedList.add(nodePoint4);
 
        doubleLinedList.update(nodePoint5);
 
        doubleLinedList.delete(nodePoint5.sno);
        doubleLinedList.list();
    }
}
class DoubleLinedList{
    private NodePoint head = new NodePoint(0,"",0,"");
 
    // 遍历双向链表的方法
    public void list(){
        if (head.next == null) {
            System.out.println("链表为空");
            return ;
        }
        NodePoint temp = head.next;
        while(temp != null){
            System.out.println(temp);
            temp = temp.next;
 
        }
    }
    // 添加一个节点到双向链表的最后.
    public void add(NodePoint node){
        NodePoint temp = head;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = node;
        node.pre = temp;
    }
    // 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样
    public void update(NodePoint updatenode){
        boolean flag = false;
        NodePoint temp = head.next;
        while(true){
            if(temp == null) break;
            if (temp.sno == updatenode.sno){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag == true){
            temp.name = updatenode.name;
            temp.age = updatenode.age;
            temp.grade = updatenode.grade;
        }else
            System.out.printf("要修改的 %d 节点不存在，无发修改n", updatenode.sno);
    }
    // 从双向链表中删除一个节点, // 说明
    // 1 对于双向链表，我们可以直接找到要删除的这个节点
    // 2 找到后，自我删除即可
    public void delete(int sno){
        if (head.next == null) {// 空链表
            System.out.println("链表为空，无法删除");
            return;
        }
        boolean flag = false;
        NodePoint temp = head.next;
        while (true){
            if (temp == null) return ;
            if (temp.sno == sno) {// 找到的待删除节点的前一个节点 temp
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.pre.next = temp.next;
            //判断是否为最后一个节点，如果最后一个节点不进行判断会出现nullException
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.printf("要删除的 %d 节点不存在n", sno);
        }
 
    }
}
//定义Node 每个Node都是一个对象
class NodePoint{
    public int sno;
    public String name;
    public int age;
    public String grade;
    public NodePoint pre;
    public NodePoint next;
 
    public NodePoint(int sno, String name, int age, String grade) {
        this.sno = sno;
        this.name = name;
        this.age = age;
        this.grade = grade;
    }
 
    public void setSno(int sno) {
        this.sno = sno;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public void setAge(int age) {
        this.age = age;
    }
 
    public void setGrade(String grade) {
        this.grade = grade;
    }
 
 
    @Override
    public String toString() {
        return "Student{" +
                "sno=" + sno +
                ", name='" + name + ''' +
                ", age=" + age +
                ", grade='" + grade + ''' +
                '}';
    }
}
 

约瑟夫问题

这里我们用单循环链表进行题解。

问题

Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（11->5->3

图解

代码

package com.cz.LinkedList;
 
/**
 * @ProjectName: Data_structure
 * @Package: com.cz.LinkedList
 * @ClassName: Josephu
 * @Author: 张晟睿
 * @Date: 2022/2/27 18:27
 * @Version: 1.0
 */
public class Josephu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addChild(5);
 
        circleSingleLinkedList.showChild();
 
        circleSingleLinkedList.outcircle(1,2,5);
    }
}
 
class CircleSingleLinkedList{
    //创建一个first节点 当前没有编号
    private Child first = null;
 
    public void addChild(int nums) {
        //定义一个临时变量存放头节点
        Child curChild = null;
        if (nums < 1 ){
            System.out.println("nums 的值不正确,请重新输入");
        }
        for (int i = 1; i  nums || countNum < 0 || nums < 0){
            System.out.println("输入错误，请输入合适的参数");
        }
        Child point = first;    //辅助指针  用来辅助first来进行指针的指向
        while(true){
            if (point.getNext() == first){
                break;
            }
            point = point.getNext();
        }
        //将两个指针从startNo开始进行操作
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            point = point.getNext();
        }
        while(true){
            if (first == point){    //说明该环中 只有一个孩子
                break;
            }
            for (int i = 0; i < countNum - 1; i++) {
                point = point.getNext();
                first = first.getNext();
            }
            System.out.printf("小孩%d 出圈n", first.getNo());
 
            first = first.getNext();//first 指向下一个孩子节点
            point.setNext(first);//将point的指针指向first的节点 此时first的孩子已经出圈
        }
        System.out.printf("最后留在圈中的小孩编号%d n", first.getNo());
    }
}
class Child {
    private int no;//该节点的编号
    private Child next;//指向下一个节点
 
    public Child(int no) {
        this.no = no;
    }
 
    public int getNo() {
        return no;
    }
 
    public void setNo(int no) {
        this.no = no;
    }
 
    public Child getNext() {
        return next;
    }
 
    public void setNext(Child next) {
        this.next = next;
    }
 
    @Override
    public String toString() {
        return "Child{" +
                "no=" + no +
                '}';
    }
}