单链表简单实现

曾经终败给现在 2023-03-01 13:44 124阅读 0赞

# 一、概述 #

链表是有序的列表，其存储结构如下：

![单链表示意图][format_png]

1.  链表是以节点的方式来存储，是链式存储
2.  每个节点包含data域，next域：指向下一个节点
3.  链表的各个节点并不一定是连续存储
4.  链表分带头节点的链表和不带头节点的链表，根据实际情况来定  
    ![format_png 1][]

# 二、代码实现 #

## 1. 创建节点类 ##

存储节点信息和指向下一个节点。

//学生链表节点
        public class StudentNode { 
            private int stuId;
            private String name;
            private int age;
            private StudentNode next;
    
            public StudentNode(int stuId, String name, int age) { 
                this.stuId = stuId;
                this.name = name;
                this.age = age;
            }
    
    
    
            @Override
            public String toString() { 
                return "StudentNode{" +
                        "stuId=" + stuId +
                        ", name='" + name + '\'' +
                        ", age=" + age +
                        '}';
            }
    
            //判断是否存在下一个节点
            public boolean hasNext(){ 
                return this.next != null;
            }
        }

## 2. 创建单向链表类 ##

public class SingleLinkList { 
        //头节点，不存放任何实用数据，不能动，用于遍历
        private StudentNode head;
    
        //构造器，初始化头节点
        public SingleLinkList() { 
            this.head = new StudentNode(0,"",0);
        }
    
        //创建学生节点
        public StudentNode getStudentNodeInstance(int stuId, String name, int age){ 
            return this.new StudentNode(stuId,name,age);
        }
    
        //追加到链表末尾
        public void add(StudentNode studentNode){ 
            //创建临时变量作为遍历指针
            StudentNode temp = head;
            //遍历链表，获取最后节点
            while (temp.hasNext()){ 
                temp = temp.next;
            }
            temp.next = studentNode;
        }
    
        //按照学号id顺序进行添加
        public void addByStuIdOrder(StudentNode studentNode){ 
            //创建临时变量作为遍历指针
            StudentNode temp = head;
            //判断该序号的学生节点是否存在
            boolean flag = false;
            //遍历链表，获取最后节点
            while (temp.hasNext()){ 
                if(temp.next.stuId > studentNode.stuId){ 
                    break;
                }else if(temp.next.stuId == studentNode.stuId){ 
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if(flag){ 
                System.out.printf("该学号%d的学生已存在，不可添加\n",studentNode.stuId);
            }
            studentNode.next = temp.next;
            temp.next = studentNode;
        }
    
        //通过学号来查询节点，并对节点内容做修改
        public void update(StudentNode studentNode){ 
            //如果链表为空，提示需要修改的节点不存在
            if(head.next == null){ 
                System.out.printf("该学号%d的学生不存在，无法修改\n",studentNode.stuId);
            }
    
            //判断该序号的学生节点是否存在
            boolean flag = false;
            //创建临时变量作为遍历指针
            StudentNode temp = head;
            while (temp.hasNext()){ 
                if(temp.stuId == studentNode.stuId){ 
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
    
            //如果存在则修改节点内容
            if(flag){ 
                temp.name = studentNode.name;
                temp.age = studentNode.age;
            }else { 
                System.out.printf("该学号%d的学生不存在，无法修改\n",studentNode.stuId);
            }
        }
    
        //删除
        public void del(int stuId){ 
            //如果链表为空，提示需要删除的节点不存在
            if(head.next == null){ 
                System.out.printf("该学号%d的学生不存在，无法删除\n",stuId);
            }
            //判断该序号的学生节点是否存在
            boolean flag = false;
            //创建临时变量作为遍历指针
            StudentNode temp = head;
            while (temp.hasNext()){ 
                if(temp.next.stuId == stuId){ 
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
    
            //如果存在则修改节点内容
            if(flag){ 
                //temp指向的下一个节点为待删除节点，因此将temp的next指向待删除节点的next节点
                temp.next = temp.next.next;
            }else { 
                System.out.printf("该学号%d的学生不存在，无法删除\n",stuId);
            }
        }
        
        //获取指定学号的学生信息
        public StudentNode get(int stuId){ 
            //如果链表为空，直接返回null
            if(head.next == null){ 
                return null;
            }
    
            //判断该序号的学生节点是否存在
            boolean flag = false;
            //创建临时变量作为遍历指针
            StudentNode temp = head;
            while (temp.hasNext()){ 
                if(temp.stuId == stuId){ 
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
    
            //如果存在则修改节点内容
            if(flag){ 
                return temp;
            }else { 
                return null;
            }
        }
    
        //遍历输出
        public void list(){ 
            //创建临时变量作为遍历指针
            StudentNode temp = head;
            while (temp.hasNext()){ 
                temp = temp.next;
                System.out.println(temp);
            }
        }
    
        //学生链表节点(对应上面节点类)
        public class StudentNode { 
            ...
        }
    }

# 三、结果演示 #

## 1. 测试类 ##

public static void main(String[] args) { 
            SingleLinkList singleLinkList = new SingleLinkList();
            SingleLinkList.StudentNode stu1 = singleLinkList.getStudentNodeInstance(1, "lxm", 26);
            SingleLinkList.StudentNode stu2 = singleLinkList.getStudentNodeInstance(2, "lh", 25);
            SingleLinkList.StudentNode stu3 = singleLinkList.getStudentNodeInstance(3, "sr", 26);
            SingleLinkList.StudentNode stu4 = singleLinkList.getStudentNodeInstance(4, "jl", 25);
            /*singleLinkList.add(stu1); singleLinkList.add(stu2); singleLinkList.add(stu4); singleLinkList.add(stu3);*/
            System.out.println("新增后内容：");
            singleLinkList.addByStuIdOrder(stu1);
            singleLinkList.addByStuIdOrder(stu2);
            singleLinkList.addByStuIdOrder(stu4);
            singleLinkList.addByStuIdOrder(stu3);
            singleLinkList.list();
    
            System.out.println("修改后内容：");
            singleLinkList.update(singleLinkList.getStudentNodeInstance(1,"poi",36));
            singleLinkList.list();
    
            System.out.println("删除后内容：");
            singleLinkList.del(1);
            singleLinkList.del(4);
            singleLinkList.del(5);
            singleLinkList.list();
            
            System.out.println("get方法结果测试：");
            System.out.println(singleLinkList.get(2));
        }

## 2. 测试结果 ##

新增后内容：
    StudentNode{ stuId=1, name='lxm', age=26}
    StudentNode{ stuId=2, name='lh', age=25}
    StudentNode{ stuId=3, name='sr', age=26}
    StudentNode{ stuId=4, name='jl', age=25}
    修改后内容：
    StudentNode{ stuId=1, name='poi', age=36}
    StudentNode{ stuId=2, name='lh', age=25}
    StudentNode{ stuId=3, name='sr', age=26}
    StudentNode{ stuId=4, name='jl', age=25}
    删除后内容：
    该学号5的学生不存在，无法删除
    StudentNode{ stuId=2, name='lh', age=25}
    StudentNode{ stuId=3, name='sr', age=26}
    get方法结果测试：
    StudentNode{ stuId=2, name='lh', age=25}
    
    Process finished with exit code 0

[format_png]: /images/20230208/fcd2ec3914914c95aa5f4bd7130b30aa.png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS83ZDJlN2U0MWI1N2Q5ODQwM2Y0OGJkNTNkYTBiMzIwNS94bWxub3RlL0I0Mzk0OTc2MzNFRDRGQkQ5MjE3MUMxMEM2OUY3RUUxLzE3NjEw?x-oss-process=image/format,png