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=新的节点;

JavaScript 测试模式
JavaScript 测试模式

使用 Jest、Vitest 和 Testing Library 实施全面的测试策略,包括单元测试、集成测试和端到端测试,涵盖模拟、测试夹具和测试驱动开发。在编

下载

在这里插入图片描述

代码实现

	// 添加方式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速学教程(入门到精通)

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

下载

相关标签:

java

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

相关专题

更多
GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

20

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

60

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

60

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

20

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

60

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

40

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

180

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

140

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

160

15

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
dev.java 官方:Learn Java
dev.java 官方:Learn Java

共0课时 | 0人学习

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

共0课时 | 0人学习