首页 专区 Skill 文章 专题 AI工具 学习 编程手册

PHP MySQL jquery HTML CSS
首页 > Java > Java基础

java实现单链表(Linked List)相关

千敏同学_1837

千敏同学_1837

2021-03-01

3639人浏览

转载

免费学习推荐：java基础教程

文章目录

  • 一、单链表介绍
  • 二、单链表的实现
    • 1.单链表的创建(添加)
      • 1.1尾添加
      • 1.2按排名添加
    • 2.单链表节点的修改
    • 3.单链表节点的删除
    • 4.单链表的完整实现
  • 三、单链表面试题

一、单链表介绍

单链表是一个有序列表，以节点的方式链式存储信息，但节点不一定连续，每一个节点包括data域和next域。

  • data域：用来存放数据。
  • next域：指向下一个节点。

在这里插入图片描述

链表分为带头节点的链表和不带头节点的链表。

  • 单链表(带头节点)
    在这里插入图片描述
  • 单链表(不带头节点)
    在这里插入图片描述

二、单链表的实现

需求：使用带head头的单向链表实现–水浒英雄排行榜管理。
1)完成对英雄的增删改查
2)第一种方法在添加英雄时，直接添加到链表的尾部。
3)第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果已有这个排名，则添加失败，并给出提示)

1.单链表的创建(添加)

1.1尾添加

尾添加的思路

①先创建一个head头节点，作用就是表示单链表的头。
②然后每添加一个节点，就直接加入到链表的最后。

尾添加即：不考虑编号顺序，找到当前链表的最后节点，将最后这个节点的next指向新的节点。
在这里插入图片描述
代码实现

	// 添加方式1:尾添加
	public void add(HeroNode heroNode) {
		// 因为head头不能动,因此需要一个辅助变量(指针)temp
		HeroNode temp = head;
		while (true) {
			// 如果遍历到链表的最后
			if (temp.next == null) {
				break;
			}
			// temp指针后移
			temp = temp.next;
		}
		// 当退出循环时,temp指向链表的最后
		temp.next = heroNode;
	}

1.2按排名添加

按排名添加的思路
①先通过辅助变量(temp指针)找到新添加的节点的位置。
②新节点.next=temp.next;
③temp.next=新的节点；

Java注释规范Skills
Java注释规范Skills

当用户要求为 Java 代码添加注释、修改注释、审查注释、整理注释格式，或要求按照代码注释规范处理 Java 文件时，使用本技能。本技能用于统一生成和维护 Java 类注释模板、按 Git 对比 release 判断版本号、补充每行代码上方中文块注释、调整注释空行规则，并保持 Java 文件 UTF-8 无 BOM 编码。典型触发场景包括：补充类注释、更新 @version、检查 @author 来源、整理行尾注释、把注释放到代码上一行、检查注释是否符合规范、构建前检查 Java 注释风格。

下载

在这里插入图片描述

代码实现

	// 添加方式2:根据排名添加
	public void addByOrder(HeroNode heroNode) {
		HeroNode temp = head;// 借助辅助指针
		boolean flag = false;// 添加的编号是否存在
		while (true) {
			if (temp.next == null) {// 遍历到结尾
				break;
			}
			if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入
				break;
			} else if (temp.next.no == heroNode.no) {// 该编号已存在
				flag = true;
				break;
			}
			temp = temp.next;// 后移,遍历当前链表
		}
		if (flag) {
			// 不能添加
			System.out.printf("准备插入的英雄的编号%d已经存在，不能加入\n", heroNode.no);
		} else {
			// 插入到temp的后面
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

2.单链表节点的修改

修改的思路
①通过遍历先找到该节点。
②temp.name =newHeroNode.name;，temp.nickname=newHeroNode.nickname;

代码实现

	// 修改节点信息,根据节点的no属性修改其他信息
	public void update(HeroNode newHeroNode) {
		// 空链表无法修改节点信息
		if (head.next == null) {
			System.out.println("链表为空~");
			return;
		}
		// 根据no排名找到需要修改的节点
		HeroNode temp = head.next;
		boolean flag = false;// flag表示是否找到需要修改的节点
		while (true) {
			if (temp == null) {
				// 遍历到结尾
				break;
			}
			if (temp.no == newHeroNode.no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;// 后移
		}
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {
			System.out.printf("没有找到编号为%d的节点，不能修改\n", newHeroNode.no);
		}
	}

3.单链表节点的删除

删除的思路

①找到需要删除的节点的前一个节点。
②temp.next=temp.next.next
③被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收。
在这里插入图片描述
代码实现

	public void delete(int no) {
		HeroNode 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;
		} else {
			System.out.printf("要删除的%d节点不存在\n", no);
		}
	}

4.单链表的完整实现

package com.gql.linkedlist;/**
 * 单链表
 * 
 * @guoqianliang
 *
 */public class SingleLinkedListDemo {
	public static void main(String[] args) {
		// 创建节点
		HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
		HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
		HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
		HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
		// 创建单向链表
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		// 加入
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero2);

		singleLinkedList.list();

		// 测试修改节点
		HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~");
		singleLinkedList.update(newHeroNode);
		System.out.println("修改后的链表情况:");
		singleLinkedList.list();

		// 删除一个节点
		singleLinkedList.delete(1);
		singleLinkedList.delete(2);
		singleLinkedList.delete(3);
		singleLinkedList.delete(4);
		System.out.println("删除后的链表情况:");
		singleLinkedList.list();

	}}//定义SingleLinkedList,管理英雄class SingleLinkedList {
	// 初始化头结点,不存放具体数据
	private HeroNode head = new HeroNode(0, "", "");

	// 添加方式1:尾添加
	// 思路:
	// 1.找到当前链表的最后节点
	// 2.将这个最后的节点的next指向新的节点
	public void add(HeroNode heroNode) {
		// 因为head头不能动,因此需要一个辅助变量(指针)temp
		HeroNode temp = head;
		while (true) {
			// 如果遍历到链表的最后
			if (temp.next == null) {
				break;
			}
			// temp指针后移
			temp = temp.next;
		}
		// 当退出循环时,temp指向链表的最后
		temp.next = heroNode;
	}

	// 添加方式2:根据排名添加
	public void addByOrder(HeroNode heroNode) {
		HeroNode temp = head;// 借助辅助指针
		boolean flag = false;// 添加的编号是否存在
		while (true) {
			if (temp.next == null) {// 遍历到结尾
				break;
			}
			if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入
				break;
			} else if (temp.next.no == heroNode.no) {// 该编号已存在
				flag = true;
				break;
			}
			temp = temp.next;// 后移,遍历当前链表
		}
		if (flag) {
			// 不能添加
			System.out.printf("准备插入的英雄的编号%d已经存在，不能加入\n", heroNode.no);
		} else {
			// 插入到temp的后面
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

	// 修改节点信息,根据节点的no属性修改其他信息
	public void update(HeroNode newHeroNode) {
		// 空链表无法修改节点信息
		if (head.next == null) {
			System.out.println("链表为空~");
			return;
		}
		// 根据no排名找到需要修改的节点
		HeroNode temp = head.next;
		boolean flag = false;// flag表示是否找到需要修改的节点
		while (true) {
			if (temp == null) {
				// 遍历到结尾
				break;
			}
			if (temp.no == newHeroNode.no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;// 后移
		}
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {
			System.out.printf("没有找到编号为%d的节点，不能修改\n", newHeroNode.no);
		}
	}

	// 删除节点
	// 思路:
	// 1.找到需要删除节点的前一个节点
	// 2.temp.next=temp.next.next
	// 3.被删除的节点将会被垃圾回收机制回收
	public void delete(int no) {
		HeroNode 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;
		} else {
			System.out.printf("要删除的%d节点不存在\n", no);
		}

	}

	// 显示链表[遍历]
	public void list() {
		// 空链表直接返回
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		// 仍然使用辅助变量(指针),进行循环
		HeroNode temp = head.next;
		while (true) {
			if (temp == null) {
				break;
			}
			System.out.println(temp);
			// 将temp后移
			temp = temp.next;
		}

	}}//定义HeroNode,每一个HeroNode就是一个节点class HeroNode {
	public int no;// 排名
	public String name;
	public String nickname;// 昵称
	public HeroNode next;// 指向下一个节点

	// 构造器
	public HeroNode() {
		super();
	}

	public HeroNode(int no, String name, String nickname) {
		super();
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	// 重写toString
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}}

运行结果
在这里插入图片描述

三、单链表面试题

在这里插入图片描述
上面四个面试题，答案都放在下面的代码中

package com.gql.LinkedList;import java.util.Stack;/**
 * 模拟单链表
 * 
 * @author Hudie
 * @Email:guoqianliang@foxmail.com
 * @date 2020年7月16日下午6:47:42
 */public class SingleLinkedListDemo {
	public static void main(String[] args) {
		// 创建节点
		HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
		HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
		HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
		HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
		// 创建单向链表
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		// 加入
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero2);

		singleLinkedList.list();

		// 测试修改节点
		HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~");
		singleLinkedList.update(newHeroNode);
		System.out.println("修改后的链表情况:");
		singleLinkedList.list();

		// 删除一个节点
		singleLinkedList.delete(4);
		System.out.println("删除后的链表情况:");
		singleLinkedList.list();
		
		//练习4:反向打印单链表
		System.out.println("反向打印单链表:");
		reversePrint(singleLinkedList.getHead());
		//练习3:反转单链表
		reversalList(singleLinkedList.getHead());
		System.out.println("反转过后的单链表为:");
		singleLinkedList.list();
		
		// 练习1:获取单链表节点个数
		System.out.println("单链表的有效个数为:");
		System.out.println(getLength(singleLinkedList.getHead()));
		
		int index = 2;
		//练习2:获取单链表倒数第index给节点
		System.out.println("倒数第"+ index +"个节点为:");
		System.out.println(getLastKNode(singleLinkedList.getHead(),index));
	}

	/**
	 * @Description: 获取单链表节点个数 思路: while循环 + 遍历指针
	 */
	public static int getLength(HeroNode head) {
		if (head.next == null) {
			return 0;
		}
		int length = 0;
		// 辅助指针
		HeroNode p = head.next;
		while (p != null) {
			length++;
			p = p.next;
		}
		return length;
	}

	/**
	 * @Description: 
	 * 查找单链表中倒数第index个节点 index:表示倒数第index给节点 
	 * 思路:
	 * 1.首先获取链表的长度length,可直接调用getLength
	 * 2.然后从链表第一个开始遍历,遍历(length-index)个 
	 * 3.找不到返回null
	 */
	public static HeroNode getLastKNode(HeroNode head, int index) {
		if (head.next == null) {
			return null;
		}
		int length = getLength(head);
		if (index  length) {
			return null;
		}
		HeroNode p = head.next;
		for(int i = 0;i  stack = new Stack<heronode>();
		HeroNode p = head.next;
		while(p != null){
			stack.push(p);
			p = p.next;
		}
		//将栈中的节点进行打印
		while(stack.size() > 0){
			System.out.println(stack.pop());
		}
	}}// 定义SingleLinkedList,管理英雄,即链表的增删改查class SingleLinkedList {
	// 初始化头结点,不存放具体数据
	private HeroNode head = new HeroNode(0, "", "");

	// 添加方式1:尾添加
	// 思路:
	// 1.找到当前链表的最后节点
	// 2.将这个最后的节点的next指向新的节点
	public void add(HeroNode heroNode) {
		// 因为head头不能动,因此需要一个辅助变量(指针)temp
		HeroNode temp = head;
		while (true) {
			// 如果遍历到链表的最后
			if (temp.next == null) {
				break;
			}
			// temp指针后移
			temp = temp.next;
		}
		// 当退出循环时,temp指向链表的最后
		temp.next = heroNode;
	}

	public HeroNode getHead() {
		return head;
	}

	// 添加方式2:根据排名添加
	public void addByOrder(HeroNode heroNode) {
		HeroNode temp = head;// 借助辅助指针
		boolean flag = false;// 添加的编号是否存在
		while (true) {
			if (temp.next == null) {// 遍历到结尾
				break;
			}
			if (temp.next.no > heroNode.no) {// 位置找到,就在temp的后面插入
				break;
			} else if (temp.next.no == heroNode.no) {// 该编号已存在
				flag = true;
				break;
			}
			temp = temp.next;// 后移,遍历当前链表
		}
		if (flag) {
			// 不能添加
			System.out.printf("准备插入的英雄的编号%d已经存在，不能加入\n", heroNode.no);
		} else {
			// 插入到temp的后面
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

	// 修改节点信息,根据节点的no属性修改其他信息
	public void update(HeroNode newHeroNode) {
		// 空链表无法修改节点信息
		if (head.next == null) {
			System.out.println("链表为空~");
			return;
		}
		// 根据no排名找到需要修改的节点
		HeroNode temp = head.next;
		boolean flag = false;// flag表示是否找到需要修改的节点
		while (true) {
			if (temp == null) {
				// 遍历到结尾
				break;
			}
			if (temp.no == newHeroNode.no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;// 后移
		}
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {
			System.out.printf("没有找到编号为%d的节点，不能修改\n", newHeroNode.no);
		}
	}

	// 删除节点
	// 思路:
	// 1.找到需要删除节点的前一个节点
	// 2.temp.next=temp.next.next
	// 3.被删除的节点将会被垃圾回收机制回收
	public void delete(int no) {
		HeroNode 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;
		} else {
			System.out.printf("要删除的%d节点不存在\n", no);
		}

	}

	// 显示链表[遍历]
	public void list() {
		// 空链表直接返回
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		// 仍然使用辅助变量(指针),进行循环
		HeroNode temp = head.next;
		while (true) {
			if (temp == null) {
				break;
			}
			System.out.println(temp);
			// 将temp后移
			temp = temp.next;
		}

	}}// 定义HeroNode,每一个HeroNode就是一个节点class HeroNode {
	public int no;// 排名
	public String name;
	public String nickname;// 昵称
	public HeroNode next;// 指向下一个节点

	// 构造器
	public HeroNode() {
		super();
	}

	public HeroNode(int no, String name, String nickname) {
		super();
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	// 重写toString
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}}</heronode>

相关学习推荐：java基础

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南

相关文章

Java 中指令重排序怎么通过内存屏障禁止乱序

Java 中线程中断抛出异常怎么满足 happens-before 约束

Java 中并发编程三大特性怎么结合内存模型掌握

Java 异步流处理中 CompletableFuture 怎么实现高效并发

Java 中怎么遍历指定目录下的所有文件
java速学教程(入门到精通)
java速学教程(入门到精通)

java怎么学习？java怎么入门？java在哪学？java怎么学才快？不用担心，这里为大家提供了java速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

java

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：java怎么定义数组

下一篇：Java讲解ThreadPool线程池

作者最新文章

java中indexof方法有哪些

Java并发编程之介绍线程安全基础

Java介绍通过反射获取类的信息

java怎么定义数组

java实现单链表(Linked List)相关

Java讲解ThreadPool线程池

Java零基础详解多线程

Java基础之TreeSet与Java自定义类型的排序

常用的Java代码段有哪些

Java常用的五种设计模式是什么

热门AI工具

更多
Laper

Laper

Hot 豆包大模型

豆包大模型

 讯飞绘文

讯飞绘文

Hot AionClaw

AionClaw

Hot 火山引擎

火山引擎

Hot 超级麦吉

超级麦吉

Hot 立刻MV

立刻MV

Hot DeepSeek

DeepSeek

相关专题

更多
Vite 项目如何打包和部署
Vite 项目如何打包和部署

Vite项目打包部署专题汇集生产构建、产物预览、输出目录、资源路径、Nginx与GitHub Pages部署及常见白屏和路由404问题的已审核文章，帮助读者完成上线流程。

2026.10.28

40

16

Vite 如何搭配 Vue.js
Vite 如何搭配 Vue.js

Vite搭配Vue.js专题汇集创建Vue 3项目、配置开发环境、路径别名、Vue插件、代理、多环境构建与调试的已审核文章，帮助读者完成从初始化到日常开发的配置。

2026.10.28

20

15

Vite 项目目录怎么看
Vite 项目目录怎么看

Vite项目目录专题汇集入口文件、src源码、public静态资源、路径别名、项目根目录和构建输出目录相关的已审核文章，帮助读者理解各文件夹的用途与引用方式。

2026.10.28

40

10

Gradle插件开发入门教程
Gradle插件开发入门教程

本专题介绍Gradle插件开发的基本流程，涵盖插件类编写、自定义任务注册、扩展参数设计和插件应用方法，帮助你理解插件如何组织构建逻辑，减少多个项目之间的重复配置。

2026.10.22

120

11

Gradle Wrapper配置教程
Gradle Wrapper配置教程

本专题介绍Gradle Wrapper的基本作用，涵盖文件组成、生成方法、版本配置和任务调用，帮助你理解项目如何使用指定的Gradle版本，减少不同开发环境带来的构建差异。

2026.10.22

80

10

Golangci-lint检查器使用教程
Golangci-lint检查器使用教程

本专题整理Golangci-lint常用Linters的用途与配置方法，覆盖错误处理、无效代码、安全、复杂度、命名和依赖检查，帮助项目合理选规则。

2026.10.22

80

15

Gradle怎么构建Java项目
Gradle怎么构建Java项目

本专题介绍Gradle Java项目构建方法，涵盖Java插件配置、依赖声明、源码编译、测试执行和打包检查，帮助你理解各阶段的任务关系，逐步完成项目构建。

2026.10.22

40

10

PHP时间戳漏洞修复教程
PHP时间戳漏洞修复教程

本专题汇总PHP常见时间戳漏洞，包括2038年溢出、时区漂移、时间戳伪造、重放攻击、时间盲注与日志审计失效等，并给出升级64位环境、使用 DateTimeImmutable、统一UTC、严格超时校验、预处理绑定、hash_equals 比对等修复方案，帮助开发者快速排查和加固时间相关代码。

2026.10.22

80

25

Golangci-lint配置文件与规则设置
Golangci-lint配置文件与规则设置

本专题聚焦Golangci-lint YAML配置文件，讲清运行参数、规则启停、目录排除、问题过滤及严重级别设置，便于团队统一检查标准。

2026.10.22

40

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

相关下载

更多
MDPHP(麦迪php框架系统)1.1
PHP 多国语言框架2.0
ujframe简单快速PHP开发框架1.0
php轻量型框架1.0
MyQEE开源PHP多项目及模块化开发框架3.0 RC2
php开源学习型框架CMVC1.2.0
PHP框架Kohana3.3.1

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Oracle 官方：JDK 26 Tool Specifications
Oracle 官方：JDK 26 Tool Specifications

共0课时 | 0人学习

dev.java 官方：Learn Java
dev.java 官方：Learn Java

共0课时 | 0人学习

Java JDBC数据库连接官方教程
Java JDBC数据库连接官方教程

共0课时 | 0人学习

最新文章

更多
java开发技巧总结
java开发必备知识
java开发基础总结
java开发基础教程
java开发基础知识点
java开发基础面试题
零基础小白学java要多久
零基础三个月学java
从基础培养java语言
java script零基础书籍