当前位置： 首页 > news >正文

Java实现一个带头节点的单链表

news 2025/7/18 3:29:08
什么是单链表？

单链表是一种基础的数据结构，其中每个节点都包含两部分：

  1. 数据域：存储节点数据。
  2. 指针域：存储指向下一个节点的引用。
为什么使用头节点？

头节点的存在简化了操作逻辑：

  • 统一操作逻辑：即使链表为空，头节点也存在，从而避免特殊情况的判断。

  • 简化插入和删除：无需特殊处理第一个节点的操作。

  • 没有头节点的add：你必须对是头节点插入进行处理，把当前的node给头节点，这样才不是null，后续才能进行正常查找最后一个的node节点然后进行指向。详情查看下面代码演示过程。

package com.algorithm.dev.linked;import lombok.AllArgsConstructor;
import lombok.Data;/*** @author xiazhihao* @ClassName: NoHeadSingleLinkedList* @ClassNameExplain:* @Description: xiazhihao* @date 2024/12/13 */
public class NoHeadSingleLinkedList {/*** 起始位置 没有设置头节点 现在它为null*/private Node head;/*** 添加数据* @param data 待添加的数据*/public void add(Object data){Node newNode = new Node(data, null);//没有头节点需要判断 因为必须告知起始的地址//【】if (null == head){//【node|next】->head = newNode;}//有新的话必须 往后面找//【1|next】—> 【1|next】 -> null//假设你不判断null == head 那么没有头节点插入就会空指针else {//当前处理的node节点 后面为了找到最后一个会不断遍历更新Node currentNode = newNode;while ( null != currentNode.next){//没找到一直更新当前遍历的情况currentNode = currentNode.next;}//找到了就证明找到了结尾 直接更改指向就链上了currentNode.next = newNode;}}@Data@AllArgsConstructorclass Node{/*** 数据域*/private Object data;/*** 下一个指针*/private Node next;}}
  • 有头节点的add：不管是不是头节点都可以直接按一套逻辑查找，直接找最后的node，因为头节点给了入口进行查找，不会出现null的情况。
/*** @author xiazhihao* @ClassName: SingleLinkedList* @ClassNameExplain:* @Description: 有头节点的标志单链表* @date 2024/12/13 */
@ToString
public class SingleLinkedList {/*** 头节点*/private Node head = new Node("我是头节点，不要动我，我是多余的，我为方便新增或者删除少做逻辑判断",null);/*** 新增链表数据 尾插o(n)* @param data 数据*/public void add(Object data){Node newNode = new Node(data,null);//用于后续编辑找到最后一个节点 代表当前遍历的位置Node currentNode = head;while (null != currentNode.next){currentNode = currentNode.next;}//【currentNode|next】 -> 【newNode|next】 -> null//找到了最后的节点currentNode.next = newNode;}
}

链表实现及方法解析

链表结构

初始状态下链表只有一个头节点：

【head|next】-> null
1. 新增节点：尾插法

代码实现：

/*** 新增链表数据 尾插o(n)* @param data 数据*/
public void add(Object data){Node newNode = new Node(data,null);// 用于后续编辑找到最后一个节点，代表当前遍历的位置Node currentNode = head;while (null != currentNode.next){currentNode = currentNode.next;}//【currentNode|next】 -> 【newNode|next】 -> null// 找到了最后的节点currentNode.next = newNode;
}

操作示意图：

  1. 插入 “1” 后：
    【head|next】-> 【1|next】-> null
  2. 插入 “2” 后：
    【head|next】-> 【1|next】-> 【2|next】-> null
2. 新增节点：头插法

代码实现：

/*** 头插法 o(1)* @param data*/
public void afterAdd(Object data){Node newNode = new Node(data,null);// 【1|next】-> nullnewNode.next = head;head = newNode;// 【newNode|next】->【1|next】-> null
}

操作示意图：

  1. 插入 “2” 后：

    【head|next】-> 【2|next】-> null

  2. 插入 “3” 后：

    【head|next】-> 【3|next】-> 【2|next】-> null
3. 查找节点

代码实现：

/*** 查找出指定节点*/
public Node find(Object data){// 头节点不需要查找Node currentNode = head.next;if (null != currentNode){// 一直往下找while (null != currentNode.next){if (currentNode.data.equals(data)){return currentNode;}// 继续往下滚currentNode = currentNode.next;}return null;}// 啥都没有return null;
}

操作示意图：
查找 “2” 的节点：

【head|next】-> 【1|next】-> 【2|next】-> null↑查找
4. 删除节点：按数据删除

代码实现：

/*** 删除节点* @param data 待删除的节点* @return true 删除成功 false 删除失败*/
public boolean remove(Object data){if (isEmpty()){return false;}Node currentNode = head;while (null != currentNode.next){// 找当前系节点的下一个数据是符合删除的if (currentNode.next.data.equals(data)){// 找到了currentNode.next = currentNode.next.next;// 后续会自动释放2return true;}// 继续往下滚currentNode = currentNode.next;}return false;
}
5. 删除节点：按索引删除

代码实现：

/*** 删除指定坐标node* @param index 坐标* @return true 删除成功 false 删除失败*/
public boolean remove(int index){// 前驱节点Node preNode = head;// 遍历到指定位置的前驱节点for (int i = 0; i < index; i++) {if (preNode.next == null) {return false; // 索引超出范围}preNode = preNode.next;}// 删除了前驱next的节点if (preNode.next != null) {preNode.next = preNode.next.next; // 前驱节点指向后继节点return true;}return false;
}
6. 获取节点：按索引获取

代码实现：

/*** 获取node节点* @param index 坐标从0开始* @return*/
public Node get(int index){Node currentNode = head;for (int i = 0; i <= index; i++) {if (null == currentNode.next){return null; // 超界}currentNode = currentNode.next;}return currentNode;
}

测试代码与运行结果

测试代码：

public static void main(String[] args) {SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.add("1");singleLinkedList.add("2");singleLinkedList.add("3");// 删除索引3的节点boolean remove = singleLinkedList.remove(3);System.out.println(remove); // 输出 false// 输出链表System.out.println(singleLinkedList);
}

运行结果：

false
SingleLinkedList(head=Node(data=我是头节点，不要动我，我是多余的，我为方便新增或者删除少做逻辑判断, next=Node(data=1, next=Node(data=2, next=Node(data=3, next=null)))))

完整代码

以下是完整代码：

package com.algorithm.dev.linked;import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.ToString;import java.util.LinkedList;/*** @author xiazhihao* @ClassName: SingleLinkedList* @ClassNameExplain:* @Description: 有头节点的标志单链表* @date 2024/12/13*/
@ToString
public class SingleLinkedList {/*** 头节点*/private Node head = new Node("我是头节点，不要动我，我是多余的，我为方便新增或者删除少做逻辑判断",null);/*** 新增链表数据 尾插o(n)* @param data 数据*/public void add(Object data){Node newNode = new Node(data,null);//用于后续编辑找到最后一个节点 代表当前遍历的位置Node currentNode = head;while (null != currentNode.next){currentNode = currentNode.next;}//【currentNode|next】 -> 【newNode|next】 -> null//找到了最后的节点currentNode.next = newNode;}/*** 头插法 o(1)* @param data*/public void afterAdd(Object data){Node newNode = new Node(data,null);//【1|next】-> nullnewNode.next = head;head = newNode;//【newNode|next】->【1|next】-> null}/*** 查找出指定节点*/public Node find(Object data){//头节点不需要查找Node currentNode = head.next;if (null != currentNode){//一直往下找while ( null != currentNode.next){if (currentNode.data.equals(data)){return currentNode;}//继续往下滚currentNode = currentNode.next;}return null;}//啥都没有return null;}/****/public boolean isEmpty(){return head.next == null;}/*** 删除节点* @param data 待删除的节点* @return true 删除成功 false 删除失败*/public boolean remove(Object data){if (isEmpty()){return false;}Node currentNode = head;//【1|next】->【2|next】->【3|next】->//【1|next】->【3|next】->//while ( null != currentNode.next){//找当当前系节点的下一个数据是符合删除的代表需要上面所属的操作 1链入3if (currentNode.next.data.equals(data)){//找到了currentNode.next = currentNode.next.next;//后续会自动释放2return true;}//继续往下滚currentNode = currentNode.next;}return false;}/*** 删除指定坐标node* @param index 坐标* @return true 删除成功 false 删除失败*/public boolean remove(int index){//前驱节点Node preNode = head;// 遍历到指定位置的前驱节点for (int i = 0; i < index; i++) {if (preNode.next == null) {return false; // 索引超出范围}preNode = preNode.next;}//删除了前驱next的节点 自动释放 如果不是最后一个if (preNode.next != null) {preNode.next = preNode.next.next; // 前驱节点指向后继节点return true;}return false;}/*** 获取node节点* @param index 坐标从0开始* @return*/public Node get(int index){Node currentNode = head;for (int i = 0; i <= index; i++) {//下一个坐标没有 还在遍历肯定是超界了if ( null == currentNode.next){return null;}currentNode = currentNode.next;}return currentNode;}@AllArgsConstructor@Dataclass Node{/*** 数据*/private Object data;/*** next指针*/private Node next;}public static void main(String[] args) {SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.add("1");singleLinkedList.add("2");singleLinkedList.add("3");boolean remove = singleLinkedList.remove(3);System.out.println(remove);System.out.println(singleLinkedList);}}
http://www.lryc.cn/news/504757.html

相关文章：

  • 【图像配准】方法总结
  • LabVIEW汽车综合参数测量
  • 三相异步电动机没有气压怎么办？
  • 软件工程书籍推荐
  • 验证集和测试集的区别
  • OpenIPC开源FPV之Adaptive-Link天空端代码解析
  • Next.js流量教程：核心 Web Vitals的改善
  • 百度智能云千帆AppBuilder升级，百度AI搜索组件上线，RAG支持无限容量向量存储！
  • 构建树莓派温湿度监测系统：从硬件到软件的完整指南
  • 12.11数据结构-图
  • BERT模型入门（2）BERT的工作原理
  • python3 中的成员运算符
  • 【测试面试篇1】测试开发与开发|selenium实现自动化测试|设计测试用例|常见的测试方法|开发不认可提测试的bug该怎么办
  • 人大金仓数据linux安装注意事项
  • 【Maven】多模块项目的构建
  • 大模型学习笔记------SAM模型详解与思考
  • crictl和ctr与docker的命令的对比
  • SQLite建表语句示例（含所有数据类型、索引、自增主键、唯一索引）
  • 探秘Redis哨兵模式：原理、运行与风险全解析
  • .NET平台使用C#设置Excel单元格数值格式
  • 零基础学安全--wireshark简介
  • [Flutter] : Clipboard
  • ArcGIS MultiPatch数据转换Obj数据
  • 《开源数据：开启信息共享与创新的宝藏之门》
  • 如何评估基于TRIZ理论生成的方案的可行性和有效性？
  • sh-寡肽-78——头发护理多肽原料，改善头发外观
  • metagpt 多智能体系统
  • 下采样在点云处理中的关键作用——以PointNet++为例【初学者无门槛理解版！】
  • pytorch ---- torch.linalg.norm()函数
  • 系列1:基于Centos-8.6部署Kubernetes (1.24-1.30)