文章目录
节点类
链表类（主要）
测试类
小结
节点类
可以根据需要，对节点属性进行修改。注意重写toString()方法，以便后续的输出操作。
//节点类 class Node { public int id; public String name; public Node next; public Node(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "Node{" + "id=" + id + ", name='" + name + '\'' + '}'; } }
链表类（主要）
所实现的增删改查，反转，逆序等功能基本能适用。实现思路在代码中注释。
//链表类（管理节点） class LinkedList { //头节点 Node head = new Node(0,null); //链表有效数据个数（链表长度）（头节点不计） public int size(){ Node temp = head; int size = 0; while (true){ if (temp.next == null){ break; } size++; temp = temp.next; } return size; } //展示链表 public void list(){ if (head.next == null){ System.out.println("链表为空！"); return; } Node temp = head.next; while (true){ if (temp == null){ break; } System.out.println(temp); temp = temp.next; } } //增(根据id从小到大) public void add(Node newNode){ Node temp = head; while (true){ //用来找到链表尾 if (temp.next == null) { break; } if (temp.id == newNode.id){ System.out.println("要添加的节点的id已经存在，添加失败！"); return; } if (temp.next.id > newNode.id){ break; } temp = temp.next; } Node node = newNode; newNode.next = temp.next; temp.next = node; } //删(根据id匹配删除) public void remove(int id){ if (head.next == null){ System.out.println("链表为空!"); return; } Node temp = head; boolean flag = false; //用来标记是否找到对应id的节点 while (true){ if (temp.next == null){ break; } if (temp.next.id == id){ //找到要删除节点的前一个节点 flag =true; break; } temp = temp.next; } if (flag){ temp.next = temp.next.next; }else { System.out.println("没有找到要删除的节点，删除失败!"); } } //改（根据id匹配要修改的节点） public void update(int id,String name){ if (head.next == null){ System.out.println("链表为空！"); return; } Node temp = head; boolean flag = false; //用来标记是否找到对应id的节点 while (true){ if (temp.next == null){ break; } if (temp.id == id){ flag = true; break; } temp = temp.next; } if (flag){ temp.name = name; }else { System.out.println("没有找到要修改的节点，修改失败！"); } } //查（根据id匹配） public Node show(int id){ if (head.next == null){ System.out.println("链表为空！"); return null; } Node temp = head.next; boolean flag = false; while (true){ if (temp == null){ break; } if (temp.id == id){ flag = true; break; } temp = temp.next; } if (flag){ return temp; }else { System.out.println("没有找到要查找的节点，查找失败！"); return null; } } //查找倒数第n个节点 public Node lastShow(int n){ Node temp = head.next; int size = this.size(); if (size < n || n <= 0){ System.out.println("查找的节点不存在！"); return null; } for (int i = 0; i < size - n; i++) { temp = temp.next; } return temp; } //链表反转 public void reverse(){ if (head.next == null || head.next.next == null){ return; } Node reverseHead = new Node(0,null); Node cur = head.next; //记录当前遍历到的节点 Node next = null; //记录当前遍历到的节点的下一个节点 while (true){ if (cur == null){ //确保遍历到最后一个 break; } next = cur.next; //保存下一个节点，避免断链 //使得反转头节点指向遍历到的当前节点，而让遍历到的当前节点指向反转头节点的下一个节点 // 确保遍历到的当前节点始终位于反转头节点的下一个 cur.next = reverseHead.next; reverseHead.next = cur; //遍历 cur = next; } head.next = reverseHead.next; //最后让原头节点指向反转头节点的下一个节点，即可实现原链表的反转 } //逆序打印 //方法一：先反转 //方法二：使用栈结构 public void reversePrint(){ if (head.next == null){ System.out.println("链表为空！"); return; } Stack<Node> nodes = new Stack<>(); Node temp = head.next; while (true){ if (temp == null){ break; } nodes.push(temp); temp = temp.next; } while (nodes.size() > 0){ System.out.println(nodes.pop()); } } }
测试类
import java.util.Stack; /** * @Author: Yeman * @Date: 2021-10-14-12:55 * @Description: */ //测试类 public class SingleLinkedListTest { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); Node node1 = new Node(1, "阿兰"); Node node2 = new Node(2, "洛国富"); Node node3 = new Node(3, "艾克森"); //可以不按照id顺序添加 linkedList.add(node1); linkedList.add(node3); linkedList.add(node2); linkedList.list(); System.out.println(linkedList.size()); //链表长度 // System.out.println(linkedList.lastShow(2)); //倒数查找 // linkedList.update(2,"张玉宁"); //改 // // linkedList.remove(3); //删 // // System.out.println(linkedList.show(2)); //查 // linkedList.reverse(); //链表反转 linkedList.reversePrint(); //逆序打印 } }
小结
单链表的节点由具体数据域和指针域两部分组成，而带有头节点的单链表的头节点不存储具体数据，其指针域则指向链表的第一个有效节点，即非头节点的第一个节点。
当对单链表进行增删改查，逆序等操作时，要定义一个Node类型的辅助变量来遍历链表，而头节点注意要保持不动。
进行反转操作时，最后需要使得头节点指向反转后的链表的第一个节点，这是唯一一处使得头节点变动的地方。
