Java 数据结构与算法系列精讲之单向链表
作者：我是小白呀 发布时间：2023-07-10 08:22:12
标签：Java,单向链表,数据结构,算法
概述
从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章.
链表
链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大.
链表包括三类:
单向链表
双向链表
循环链表
单向链表
单向链表 (Single Linked List) 是链表中最简单的一种形式. 单向链表每个节点包含两个部分, 第一部分是信息, 第二部分是下一个节点. (元素 + 指针)
单向链表实现
Node 类
// Node类
private class Node {
public E e; // 元素
private SingleLinkedList.Node next; // 下一个节点
// 构造
public Node(E e) {
this.e = e;
this.next = null;
}
@Override
public String toString() {
return e.toString();
}
}
add 方法
// 添加数据
public void add(int index, E e) {
// 检查索引是否越界
if (index < 0 || index > size) {
throw new RuntimeException("Invalid Index");
}
// 获取index前一个节点
SingleLinkedList.Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// 添加数据
SingleLinkedList.Node node = new SingleLinkedList.Node(e);
node.next = prev.next;
prev.next = node;
size++;
}
remove 方法
// 删除数据
public void remove(int index) {
// 检查索引是否越界
if (index < 0 || index > size) {
throw new RuntimeException("Invalid Index");
}
// 获取index前一个节点
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// 删除数据
Node retNode = prev.next;
prev.next = retNode.next;
size --;
}
get 方法
// 通过索引获取链表数数据
public E get(int index) {
// 检查索引是否越界
if (index < 0 || index > size) {
throw new RuntimeException("Invalid Index");
}
// 获取index前一个节点
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
set 方法
// 通过索引设置链表数据
public E set(int index,E e) {
// 检查索引是否越界
if (index < 0 || index > size) {
throw new RuntimeException("Invalid Index");
}
// 获取index前一个节点
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
// 设置新值
cur.e = e;
return cur.e;
}
contain 方法
// 链表是否包含元素
public boolean contains(E e) {
Node cur = dummyHead.next;
// 遍历所有节点
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
main
// main
public static void main(String[] args) {
// 创建单向链表
SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();
// 添加数据
for (int i = 0; i < 8; i++) {
singleLinkedList.addFirst(i);
System.out.println(singleLinkedList);
}
// 是否包含元素
System.out.println(singleLinkedList.contains(0));
System.out.println(singleLinkedList.contains(10));
// set
singleLinkedList.set(0, 9);
singleLinkedList.set(1, 7);
System.out.println(singleLinkedList);
// 删除数据
for (int i = 0; i < 8; i++) {
singleLinkedList.remove(0);
System.out.println(singleLinkedList);
}
}
输出结果:
0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
5->4->3->2->1->0->NULL
6->5->4->3->2->1->0->NULL
7->6->5->4->3->2->1->0->NULL
true
false
9->7->5->4->3->2->1->0->NULL
7->5->4->3->2->1->0->NULL
5->4->3->2->1->0->NULL
4->3->2->1->0->NULL
3->2->1->0->NULL
2->1->0->NULL
1->0->NULL
0->NULL
NULL
完整代码
public class SingleLinkedList<E> {
private Node dummyHead; // 头指针
private int size; // 链表大小
// Node类
private class Node {
public E e; // 元素
private Node next; // 下一个节点
// 构造
public Node(E e) {
this.e = e;
this.next = null;
}
@Override
public String toString() {
return e.toString();
}
}
// 构造
public SingleLinkedList() {
dummyHead = new Node(null);
size = 0;
}
// 表首添加元素
public void addFirst(E e) {
add(0, e);
}
// 表尾添加元素
public void addLast(E e){
add(size, e);
}
// 添加数据
public void add(int index, E e) {
// 检查索引是否越界
if (index < 0 || index > size) {
throw new RuntimeException("Invalid Index");
}
// 获取index前一个节点
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// 添加数据
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
size ++;
}
// 删除数据
public void remove(int index) {
// 检查索引是否越界
if (index < 0 || index > size) {
throw new RuntimeException("Invalid Index");
}
// 获取index前一个节点
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// 删除数据
Node retNode = prev.next;
prev.next = retNode.next;
size --;
}
// 通过索引获取链表数数据
public E get(int index) {
// 检查索引是否越界
if (index < 0 || index > size) {
throw new RuntimeException("Invalid Index");
}
// 获取index前一个节点
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
// 通过索引设置链表数据
public E set(int index,E e) {
// 检查索引是否越界
if (index < 0 || index > size) {
throw new RuntimeException("Invalid Index");
}
// 获取index前一个节点
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
// 设置新值
cur.e = e;
return cur.e;
}
// 链表是否包含元素
public boolean contains(E e) {
Node cur = dummyHead.next;
// 遍历所有节点
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
// 获取链表大小
public int getSize() {
return size;
}
// 判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node cur = dummyHead.next;
while (cur != null) {
builder.append(cur + "->");
cur = cur.next;
}
builder.append("NULL");
return builder.toString();
}
// main
public static void main(String[] args) {
// 创建单向链表
SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();
// 添加数据
for (int i = 0; i < 8; i++) {
singleLinkedList.addFirst(i);
System.out.println(singleLinkedList);
}
// 是否包含元素
System.out.println(singleLinkedList.contains(0));
System.out.println(singleLinkedList.contains(10));
// set
singleLinkedList.set(0, 9);
singleLinkedList.set(1, 7);
System.out.println(singleLinkedList);
// 删除数据
for (int i = 0; i < 8; i++) {
singleLinkedList.remove(0);
System.out.println(singleLinkedList);
}
}
}
来源：https://iamarookie.blog.csdn.net/article/details/121885670
0
投稿猜你喜欢
算法分析一个排序算法的好坏，一般是通过下面几个关键信息来分析的，下面先介绍一下这几个关键信息，然后再将常见的排序算法的这些关键信息统计出来。- Java 匿名内部类详解匿名内部类也就是没有名字的内部类正因为没有名字，所以匿名内部类只能使用一次，它通常用来简化代码编写但使用
- 本文实例为大家分享了Android日历控件的使用方法，供大家参考，具体内容如下MainActivity.java代码:package sis
- Android Studio Intent隐式启动，发短信，拨号，打电话，访问网页等实例代码功能创建5个按钮，隐式启动、发短信、拨号按钮、电
- 本文实例讲述了Hibernate批量处理海量数据的方法。分享给大家供大家参考，具体如下：Hibernate批量处理海量其实从性能上考虑，它是
- 前言一般生成的PDF文档默认的文档底色为白色，我们可以通过一定方法来更改文档的背景色，以达到文档美化以及保护双眼的作用。 以下内容提供了Ja
- 本文实例为大家分享了java微信公众号支付示例代码，供大家参考，具体内容如下开始之前，先准备好：appid、商家号、商户密匙。工具类：MD5
- 前言我们知道volatile关键字的作用是保证变量在多线程之间的可见性，它是java.util.concurrent包的核心，没有volat
- IP地址与整数之间的转换1、IP地址转换为整数原理：IP地址每段可以看成是8位无符号整数即0-255，把每段拆分成一个二进制形式组合起来，然
- C#事件实例详解C#和JAVA有许多相似的地方，设计思想差不多，语法及其相像，均传承自面向对象设计思想，灵感来自C++并取其精华去其“糟粕（
- 想要实现无限轮播,一直向左滑动,当到最后一个view时,会滑动到第一个,无限…可以自己写ViewPager然后加handler先实现自动滚动
- 一.前言：CentOS7.0虽然自带JDK1.7和1.8，运行“java -version”命令也可以看到版本信息，但是jdk的安装环境不全
- 0.解释器(Interpreter)模式定义 ：给定一门语言，定义它的文法的一种表示，并定义一个解释器，该解释器使用该表示来解释语言中句子。
- 同学们在开发过程中，经常需要查看程序与数据库之间的SQL语句，以便于调试和分析。本文将介绍如何在控制台中显示MyBatis的SQL语句，帮助
- 这篇文章主要介绍了dotnet core链接mongodb代码实例,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价
- 先来看问题纠结了几个小时终于找到了问题所在,因为shiro的realm属于Filter,简单说就是初始化realm时,spring还未加载相
- import java.io.ByteArrayOutputStream;import java.io.InputStream;//从输入流
- 对于初学java的同学来说，第一件事不是写hello world，而是搭建好java开发环境，下载jdk，安装，配置环境变量。这些操作在xp
- 【说明】 TextView是用来显示文本的组件。以下介绍的是XML代码中的属性，在java代码中同样可通过 ”组件名.setXXX()方法设
- 花了很长时间的实践，终于搞清楚了。类或者链表等，在指针赋值的时候，会使用新的指针。比如：Foo a = c;Foo b = new Foo(
