1 单链表
1.1 单链表介绍
由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它 不要求在逻辑上相邻的两个元素在物理位置上也相邻。
物理结构示意图：
逻辑结构示意图：
关于单链表的一些说明：
链表是以节点的方式存储的，每个节点包含data和next域，分别表示存储的数据和指向下一个节点；
链表的各个节点不一定是连续存储的；
可以根据实际需求来构造是否带有头节点的链表。
1.2 单链表的实现思路分析
1.2.1 单链表的创建与遍历
单链表的创建：
先创建一个 head 头节点，表示单链表的头；
每添加一个节点就直接加入链表的最后；
遍历的思路：
创建一个辅助指针，用于帮助遍历整个链表；
当指针指向的节点的next域为null，说明当前节点为最后一个，遍历完成。
1.2.2 单链表节点的插入与修改
示意图如下：
首先需要通过遍历找到需要添加节点的位置，图中示意的为a1的位置；
新的节点的next指向a1.next；
将该位置，即a1.next指向新的节点。
修改操作相当于上述过程的简化，只需要找到对应的节点直接修改节点对应的属性即可，这里不再赘述。
1.2.3 单链表节点的删除
删除序号为 “2” 的节点示意图如下：
思路如下：
- 找到待删除节点的前一个节点，示例中则找到序号为1的节点；
- 让该节点的 temp.next = temp.next.next，即可；
- 由于被删除的节点没有其他的指向，则会由Java的垃圾回收机制进行回收，无需处理。
1.3 实现代码
StudentNode.java 节点类：
/** * @author 兴趣使然黄小黄 * @version 1.0 * 链表的节点类，包含学生信息和next */ public class StudentNode { public String no; //学号 public String name; //姓名 public int age; //年龄 public StudentNode next; //指向下一个节点 //构造器 public StudentNode(String no, String name, int age ){ this.no = no; this.name = name; this.age = age; } //为了显示方便 @Override public String toString() { return "StudentNode{" + "no='" + no + '\'' + ", name='" + name + '\'' + ", age=" + age + '}'; } }
StudentLinkedList.java 链表的实现类：
/** * @author 兴趣使然黄小黄 * @version 1.0 * 链表的实现类，用于管理众多StudentNode节点 */ public class StudentLinkedList { //初始化头节点 private StudentNode head = new StudentNode("", "", 0); //获取头节点 public StudentNode getHead() { return head; } //添加节点 //1.找到当前链表的最后节点 //2.将最后节点的next指向新的节点 public void add(StudentNode studentNode) { StudentNode temp = head; //遍历链表找到最后的节点 while (temp.next != null) { //没有找到，就后移 temp = temp.next; } //最后的节点的next指向新节点 temp.next = studentNode; } //遍历 显示链表 public void showList(){ //判断链表是否为空 if (head.next == null){ System.out.println("当前链表为空"); return; } //遍历 使用辅助指针 StudentNode temp = head; while (temp != null){ //更新指针 temp = temp.next; if (temp.next == null){ System.out.print(temp); break; } System.out.print(temp + "--->"); } } //插入节点 //根据学号顺序查找添加的位置, 如果存在, 则提示错误信息 public void addByOrder(StudentNode studentNode){ //寻找的temp应该为添加位置的前一个节点 StudentNode temp = head; boolean flag = false; //标识新添加的no是否已经存在 while (true){ if (temp.next == null){ //已经在链表的尾部 break; } if (Integer.parseInt(temp.next.no) > Integer.parseInt(studentNode.no)){ //位置找到 插入到temp后 break; }else if (Integer.parseInt(temp.next.no) == Integer.parseInt(studentNode.no)){ //已经存在 flag = true; break; } //移动指针 temp = temp.next; } if (flag){ System.out.println("\n准备插入的学生信息: " + studentNode.no + "，该学号已经存在，不可添加！"); }else { studentNode.next = temp.next; temp.next = studentNode; } } //根据no学号修改学生信息 public void update(StudentNode studentNode){ if (head.next == null){ System.out.println("当前链表为空, 无法修改"); return; } StudentNode temp = head.next; boolean flag = false; //表示是否找到节点 while (true){ if (temp == null){ break; } if (temp.no == studentNode.no){ flag = true; break; } temp = temp.next; } if (flag){ temp.name = studentNode.name; temp.age = studentNode.age; }else { System.out.println("没有找到"); } } //删除节点 public void delete(String no){ StudentNode temp = head; boolean flag = false; //标志是否找到 //查找到待删除节点的前一个节点进行删除操作 while (true){ if (temp.next == null){ //到达尾部 break; } if (temp.next.no == no){ //找到了 flag = true; break; } //遍历 temp = temp.next; } //删除操作 if (flag){ temp.next = temp.next.next; System.out.println("删除成功！"); }else { System.out.println("要删除的节点不存在！"); } } }
