一、概述
链表是有序的列表，其存储结构如下：
单链表示意图
- 链表是以节点的方式来存储，是链式存储
- 每个节点包含data域，next域：指向下一个节点
- 链表的各个节点并不一定是连续存储
- 链表分带头节点的链表和不带头节点的链表，根据实际情况来定
二、代码实现
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
