Java 实现带头结点的单链表

一、思路说明头结点Head不存储有效数据仅作为链表入口统一空链表、非空链表操作逻辑无需特殊处理首节点插入 / 删除。节点类存储数据 下一个节点引用。链表核心操作增、删、查、改、遍历、清空、获取长度、判空。完整代码java运行/** * 单链表节点 */ class NodeT { // 存储数据 T data; // 指向下一个节点 NodeT next; public Node(T data) { this.data data; this.next null; } } /** * 带头结点的单链表 * param T 泛型支持任意引用类型存储 */ public class HeadSingleLinkedListT { // 头结点无实际数据永久存在 private final NodeT head; // 构造方法初始化头结点 public HeadSingleLinkedList() { head new Node(null); } /** * 判断链表是否为空只有头结点 */ public boolean isEmpty() { return head.next null; } /** * 获取链表有效节点长度 */ public int size() { int count 0; NodeT temp head.next; while (temp ! null) { count; temp temp.next; } return count; } /** * 尾部追加节点 */ public void addLast(T data) { NodeT newNode new Node(data); NodeT temp head; // 遍历到最后一个节点 while (temp.next ! null) { temp temp.next; } temp.next newNode; } /** * 头部插入头结点后第一个位置 */ public void addFirst(T data) { NodeT newNode new Node(data); // 新节点指向原第一个有效节点 newNode.next head.next; // 头结点指向新节点 head.next newNode; } /** * 指定下标插入节点下标从0开始 * param index 插入位置 * param data 插入数据 */ public void addByIndex(int index, T data) { if (index 0 || index size()) { throw new IndexOutOfBoundsException(下标越界); } NodeT newNode new Node(data); NodeT temp head; // 找到插入位置前一个节点 for (int i 0; i index; i) { temp temp.next; } newNode.next temp.next; temp.next newNode; } /** * 根据下标删除节点 */ public void removeByIndex(int index) { if (isEmpty()) { throw new RuntimeException(链表为空无法删除); } if (index 0 || index size()) { throw new IndexOutOfBoundsException(下标越界); } NodeT temp head; // 找到待删节点前一个节点 for (int i 0; i index; i) { temp temp.next; } // 跳过待删除节点 temp.next temp.next.next; } /** * 根据数据删除第一个匹配节点 */ public void removeByData(T data) { if (isEmpty()) { throw new RuntimeException(链表为空); } NodeT temp head; while (temp.next ! null) { if (temp.next.data.equals(data)) { temp.next temp.next.next; return; } temp temp.next; } System.out.println(未找到该元素); } /** * 根据下标修改节点数据 */ public void update(int index, T newData) { if (isEmpty()) { throw new RuntimeException(链表为空); } if (index 0 || index size()) { throw new IndexOutOfBoundsException(下标越界); } NodeT temp head.next; for (int i 0; i index; i) { temp temp.next; } temp.data newData; } /** * 根据下标查询节点数据 */ public T get(int index) { if (isEmpty()) { throw new RuntimeException(链表为空); } if (index 0 || index size()) { throw new IndexOutOfBoundsException(下标越界); } NodeT temp head.next; for (int i 0; i index; i) { temp temp.next; } return temp.data; } /** * 遍历打印所有链表元素 */ public void show() { if (isEmpty()) { System.out.println(链表为空); return; } NodeT temp head.next; StringBuilder sb new StringBuilder([); while (temp ! null) { sb.append(temp.data); if (temp.next ! null) { sb.append(, ); } temp temp.next; } sb.append(]); System.out.println(sb); } /** * 清空所有有效节点保留头结点 */ public void clear() { head.next null; } // 测试主方法 public static void main(String[] args) { HeadSingleLinkedListInteger list new HeadSingleLinkedList(); // 尾部添加 list.addLast(10); list.addLast(20); list.addLast(30); System.out.print(尾部添加后); list.show(); // 头部添加 list.addFirst(5); System.out.print(头部添加5后); list.show(); // 指定下标插入 list.addByIndex(2, 15); System.out.print(下标2插入15后); list.show(); // 查询 System.out.println(下标3元素 list.get(3)); // 修改 list.update(1, 8); System.out.print(下标1修改为8后); list.show(); // 删除下标元素 list.removeByIndex(0); System.out.print(删除下标0后); list.show(); // 删除指定数据 list.removeByData(30); System.out.print(删除30后); list.show(); System.out.println(链表长度 list.size()); System.out.println(是否为空 list.isEmpty()); // 清空链表 list.clear(); System.out.print(清空后); list.show(); } }二、代码核心要点1. 头结点特性java运行private final NodeT head; public HeadSingleLinkedList() { head new Node(null); }链表实例创建时一定会存在头结点head.next null代表空链表所有操作都从head开始遍历不需要单独判断链表为空时插入首节点的特殊逻辑。2. 节点结构单向链表只有data和next无法向前回溯所有增删操作必须遍历找到前驱节点。3. 操作对比有无头结点区别无头结点插入第一个元素、删除第一个元素要单独判断代码冗余有头结点统一逻辑所有节点操作规则一致工程开发常用。三、运行输出结果plaintext尾部添加后[10, 20, 30] 头部添加5后[5, 10, 20, 30] 下标2插入15后[5, 10, 15, 20, 30] 下标3元素20 下标1修改为8后[5, 8, 15, 20, 30] 删除下标0后[8, 15, 20, 30] 删除30后[8, 15, 20] 链表长度3 是否为空false 清空后链表为空