【Java数据结构】顺序表、队列、栈、链表、哈希表

顺序表

定义

存放数据使用数组但是可以编写一些额外的操作来强化为线性表，底层依然采用顺序存储实现的线性表，称为顺序表

代码实现

创建类型

先定义一个新的类型

public class ArrayList<E> {
    int capacity = 10; //顺序表的最大容量
    int size = 0; //当前已经存放的元素数量
    private Object[] array = new Object[capacity]; //底层存放的数组
}

在这里插入图片描述

由此可见，顺序表是紧凑的，不能出现空位

插入

但是这样少了条件限制，也就是容量的问题，范围只是[0,size]，所以需要判断

public void add(E element, int index) {
    if(index<0 || index>size)
        throw new IndexOutOfBoundsException("invalid, size:0~"+size);
    for(int i=size; i>index; i--) {
        array[i] = array[i-1];
    }
    array[index] = element;
    size++;
}

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(10,1); //是一个可以得到异常的函数
}

此时此刻，就很成功的报错了
在这里插入图片描述

完善 - 扩容

我们可以让我们的操作更加完美，比如，扩容

public void add(E element, int index) {
    if(index<0 || index>size)
        throw new IndexOutOfBoundsException("invalid, size:0~"+size);
    if(capacity == size) {
        int newCapacity = capacity +(capacity >> 1);
        Object[] newArray = new Object[newCapacity];
        System.arraycopy(array, 0, newArray, 0, size);
        array = newArray;
        capacity = newCapacity;
    }
    for(int i=size; i>index; i--) {
        array[i] = array[i-1];
    }
    array[index] = element;
    size++;
}

打印

public String toString() {
    StringBulider bulider = new StringBuilder();
    for(int i=0; i<size; i++) {
        builder.append(array[i].append(" "));
        return builder.toString();
    }
}

删除

@SuppressWarnings("unchecked")
public E remove(int index){
    if(index < 0 || index > size - 1)
        throw new IndexOutOfBoundsException("删除位置非法，合法的插入位置为：0 ~ "+(size - 1));
    E e = (E) array[index];
    for (int i = index; i < size; i++)
        array[i] = array[i + 1];
    size--;
    return e;
}

获取

public E get(int index) {
if(index<0 || index>(size-1)) 
	throw new IndexOutOfBoundsException("invalid: position 0~" +(size-1));
return (E) array[index];
}

public int size() {
	return size;
}

链表

链表通过指针来连接各个分散的结点，形成链状的结构，不需要申请连续的空间，逻辑依然是每个元素相连

链表分带头结点的和不带头结点的

带头结点的就是不存放数据，一般设计都会采用带头结点的

设置

public class LinkedList<E> {
    private final Node<E> head = new Node<>(null);
	private int size = 0;

	private static class Node<E> {
   		E element;
    	Node<E> next;
    	public Node(E element) {
        	this.element = element;
    	}
	}
}

插入

考虑的点：插入位置是否合法

public void add(E element, int index){
    if(index < 0 || index > size)
        throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置为：0 ~ "+size);
    Node<E> prev = head;
    for (int i = 0; i < index; i++)
        prev = prev.next;
    Node<E> node = new Node<>(element);
    node.next = prev.next;
    prev.next = node;
    size++;
}

重写 toString()

@Override
public String toString() {
	StringBuilder builder = new StringBuilder();
    Node<E> node = head.next;
    while(node != null) {
        bulider.append(node.element).append(" ");
        node = node.next;
    }
    return builder.toString();
}

删除

public E remove(int index) {
    if(index<0 || index>size-1) {
        throw new IndexOutOfBoundsException("invalid,position: 0~" + (size - 1));
    }
    Node<E> prev = head;
    for(int i=0; i<index; i++) {
        prev = prev.next;
    }
    E e = prev.next.element;
    size--;
    return e;
}

获取对应位置上的元素

public E get(int index) {
    if(index<0 || index>size-1) {
        throw new IndexOutOfBoundsException("invalid position:0~" + (size-1));
    }
    Node<E> node = head;
    while(index-- >= 0) {
        node = node.next;
    }
    return node.element;
}

public int size() {
    return size;
}

总结

链表在随机访问数据的时候，需要通过遍历来完成，而顺序表则利用数组的特性可以直接访问得到，当我们读取数据多于插入删除操作的时候，使用顺序表会更好；顺序表在进行插入删除操作的时候，因为需要移动后续元素，会很浪费时间，链表则不需要，只需要修改结点的指向就行了。所以在进行频繁的插入删除操作的时候，使用链表必然是更好的

栈-先进后出

**FILO: First in, Last out **

是一种特殊的线性表，只能在表尾进行插入删除操作；有点像堆积木，最后堆上去的往往是最先拿下来的

底部称为栈底，顶部称为栈顶；所有的操作只能在栈顶进行

栈可以使用顺序表实现，也可以使用链表实现，使用链表会更加方便。直接将头结点指向栈顶结点，而栈顶结点连接后续的栈内结点

链表实现

类

public class LinkedStack<E> {
    private final Node<E> head = new Node<>(null);
    private static class Node<E> {
        E element;
        Node<E> next;
        public Node(E element) {
            this.element = element;
        }
    }
}

入栈操作

public pop() {
    if(head.next == null) {
        throw new NoSuchElementException("Stack is empty");
    }
    E e = head.next.element;
    return e;
}

测试

public static void main(String[] args) {
    LinkedStack<String> stack = new LinkedStack<>();
    stack.push("AAA");
    stack.push("BBB");
    stack.push("CCC");
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
}

队列

FIFO First in First out

类似于在超市买东西，先进先出
队列有队头和队首
实现方式：链表、顺序表
利用链表则不需要考虑容量的问题，我们需要同时保存队首和队尾两个指针

创建队列

public class LinkedQueue<E> {
	private final Node <E> head = new Node<>(null);
//入队操作
	public void offer(E element) {
		Node<E> last = head;
		while(last.next != null) {
			last = last.next;
		}
		last.next = new Node<>(element);
	}
//出队操作
	public E pull() {
		if(head.next == null) 
			throw new NoSuchElementException(“Queue is empty”);
		E e = head.next.element;
		head.next = head.next.next;
		return e;
	}

	private static class Node<E> {
		E element;
		Node<E> next;
		public Node(E element) {
			this.element = element;
		}
}

使用

public static void main(String[] Args) {
	LinkedQueue<String> stack = new LinkedQueue<>();
	stack.offer(“AAA”);
	stack.offer(“BBB”);
	stack.offer(“CCC”);
	System.out.println(stack.pull());
	System.out.println(stack.pull());
	System.out.println(stack.pull());

哈希表

散列（Hashing)通过散列函数（哈希函数）将要参与检索的数据与散列值（哈希值）关联，生成一种便于搜索的数据结构，称其为散列表（哈希表）

我们需要将一堆数据保存起来，这些数据会通过哈希函数进行计算，得到与其对应的哈希值，下次需要查找的时候，只需要再次计算哈希值就行了

哈希函数在现实生活中应用十分广泛，目前应用最广泛的是SHA-1、MD5；比如我们下载的IDEA，她的校验文件，就是安装包文件通过哈希算法计算得到的

我们可以将这些元素保存到哈希表，保存的位置与其对应的哈希值有关，哈希值是通过哈希函数计算得到的，我们只需要将对应元素的key提供给哈希函数就可以进行计算了。一般比较简单的哈希函数就是取模操作。哈希表长度（最好是素数）多少，模就是多少

保存到数据是无序的，我们并不清楚计算完哈希值之后会被放到那个位置，哈希表在查找时只需要进行一次哈希函数计算就能直接找到对应元素的存储位置，效率极高

实现简单的哈希表和哈希函数，通过哈希表，可以将数据的查找时间复杂度提升到常数阶

public class HashTable<E> {
    private final int TABLE_SIZE = 10;
    private final Object[] TABLE = new Object[TABLE_SIZE];
    
    public void insert(E element) {
        int index = hash(element);
        TABLE[index] = element;
    }
    
    public boolean contains(E element) {
        int index = hash(element);
        return TABLE[index] == element;
    }
    
    private int hash(Object object) {
        int hashCode = object.hashCode(); //每一个对象都有一个独一无二的哈希值，可以通过hashCode方法得到，只有极小概率会重复
        return hashCode % TABLE_SIZE;
    }
}

会出现哈希碰撞的情况，也就是不同的元素计算出来的哈希值是一样的，这种情况是不可避免的，我们只能通过使用更加高级的哈希函数来尽可能避免这种情况

常见的哈希冲突解决方案是链地址法 ，当出现哈希冲突的时候，我们依然将其保存在对应的位置上，可以将其连接为一个链表的形式

当元素太多的时候，我们一般将其横过来看
在这里插入图片描述

但是当链表变得很长的时候，查找效率也就会变得很低下，所以我们可以考虑在链表长度达到一定值的时候，使用其他数据结构，例如平衡二叉树、红黑树，这样就可以一定程度上缓解查找的压力

public class HashTable<E> {
    private final int TABLE_SIZE = 10;
    private final Node<E>[] TABLE = new Node[TABLE_SIZE];
    
    public HashTable() {
        for(int i=0; i<TABLE_SIZE; i++) {
            TABLE[i] = new Node<>(null);
        }
    }
    
    public void insert(E element) {
        int index = hash(element);
        Node<E> prev = TABLE[index];
        while(prev.next != null) {
            prev = prev.next;
        }
        prev.next = new Node<>(element);
    }
    
    public boolean contains(E element) {
        int index = hash(element);
        Node<E> node = TABLE[index].next;
        while(node != null) {
            if(node.element == element) 
                return true;
            node = node.next;
        }
        return false;
    }
    
    private int hash(Object object) {
        int hashCode = object.hashCode();
        return hashCode % TABLE_SIZE;
    }
    
    private static class Node<E> {
        private final E element;
        private Node<E> next;
        
        private Node(E element) {
            this.element = element;
        }
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/16620.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Java笔试强训 6】

【Java笔试强训 6】

&#x1f389;&#x1f389;&#x1f389;点进来你就是我的人了博主主页&#xff1a;&#x1f648;&#x1f648;&#x1f648;戳一戳,欢迎大佬指点! 欢迎志同道合的朋友一起加油喔&#x1f93a;&#x1f93a;&#x1f93a; 目录 一、选择题 二、编程题 &#x1f525;不要二 …
阅读更多...
基于微信小程序的垃圾分类系统的研究与实现（附源码和教程）

基于微信小程序的垃圾分类系统的研究与实现（附源码和教程）

1. 简介 本文介绍的事基于微信小程序的垃圾分类系统&#xff0c;主要实现的功能有登录、注册、垃圾分类查询、垃圾预约回收、垃圾分类功能。 2.系统设计与实现 本章节是论文的重点&#xff0c;基于上一章介绍的总体设计框架的搭建&#xff0c;详细对小程序的页面布局、流程设…
阅读更多...
Photoshop如何使用选区之实例演示？

Photoshop如何使用选区之实例演示？

文章目录 0.引言1.利用快速选择工具抠图2.制作网店产品优惠券3.利用选区改变眼睛颜色4.抠取复杂的花束5.制作丁达尔光照效果6.利用选区调整图像局部颜色 0.引言 因科研等多场景需要进行绘图处理&#xff0c;笔者对PS进行了学习&#xff0c;本文通过《Photoshop2021入门教程》及…
阅读更多...
MySQL基础

MySQL基础

目标&#xff1a; 掌握MySQL的安装&#xff0c;登录&#xff0c;基础操作 掌握DDL语句 掌握DML语句 掌握DQL语句 1、数据库相关概念 以前我们做系统&#xff0c;数据持久化的存储采用的是文件存储。存储到文件中可以达到系统关闭数据不会丢失的效果&#xff0c;当然文件存储…
阅读更多...
Mysql为json字段创建索引的两种方式

Mysql为json字段创建索引的两种方式

目录 一、前言二、通过虚拟列添加索引&#xff08;Secondary Indexes and Generated Columns&#xff09;三、多值索引&#xff08;Using multi-valued Indexes&#xff09;四、官网地址 一、前言 JSON 数据类型是在mysql5.7版本后新增的&#xff0c;同 TEXT&#xff0c;BLOB …
阅读更多...
【社区图书馆】二、LED子系统——硬件驱动层

【社区图书馆】二、LED子系统——硬件驱动层

个人主页&#xff1a;董哥聊技术 我是董哥&#xff0c;嵌入式领域新星创作者 创作理念&#xff1a;专注分享高质量嵌入式文章&#xff0c;让大家读有所得&#xff01; 文章目录 1、gpio_led_probe分析1.1 相关数据结构1.1.1 gpio_led_platform_data1.1.2 gpio_leds_priv 1.2 实…
阅读更多...
【论文代码阅读】LORA: LOW-RANK ADAPTATION OF LARGE LAN- GUAGE MODELS

【论文代码阅读】LORA: LOW-RANK ADAPTATION OF LARGE LAN- GUAGE MODELS

最近很多工作好像都绕不开lora&#xff0c;无论是sd还是llm.... 1. 背景 问题&#xff1a;大模型重新训练所有模型参数的完全微调变得不太可行。lora在做什么 我们提出了低秩自适应&#xff0c;即LoRA&#xff0c;它冻结预先训练的模型权重&#xff0c;并将可训练的秩分解矩…
阅读更多...
【Redis—哨兵机制】

【Redis—哨兵机制】

概念 当进行主从复制时&#xff0c;如果主节点挂掉了&#xff0c;那么没有主节点来服务客户端的写操作请求了&#xff0c;也没有主节点给从节点进行数据同步了。此时需要进行主从切换&#xff08;主从节点故障转移&#xff09;&#xff0c;Redis在 2.8 版本以后提供的哨兵&…
阅读更多...
C++标准库 --- 动态内存 (Primer C++ 第五版 · 阅读笔记)

C++标准库 --- 动态内存 (Primer C++ 第五版 · 阅读笔记)

C标准库 --动态内存 (Primer C 第五版 阅读笔记&#xff09; 第12章 动态内存------(持续更新)12.1、动态内存与智能指针12.1.1、shared_ptr类12.1.2、直接管理内存12.1.3、shared_ptr和new结合使用12.1.4、智能指针和异常12.1.5、unique_ptr12.1.6、weak_ptr 12.2、动态数组1…
阅读更多...
抓马，互联网惊现AI鬼城：上万个AI发帖聊天，互相嗨聊，人类被禁言

抓马，互联网惊现AI鬼城：上万个AI发帖聊天，互相嗨聊，人类被禁言

近日又有一个社区迷惑走红 上万个AI发帖聊天&#xff0c;人类不得入内&#xff1f; 据红星新闻报道 近日&#xff0c;一个名为Chirper的AI网络社区突然爆火 上万个AI聊天机器人在其中 激烈地聊天、互动、分享 社区主页右上角明确写着&#xff1a; “这是一个人工智能的社交…
阅读更多...
【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】

【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】

❓ 409. 最长回文串 难度&#xff1a;简单 给定一个包含大写字母和小写字母的字符串 s &#xff0c;返回 通过这些字母构造成的 最长的回文串 。 在构造过程中&#xff0c;请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 示例 1: 输入:s “abccccdd”…
阅读更多...
蒙蒂霍尔悖论

蒙蒂霍尔悖论

贝叶斯与频率主义对蒙蒂霍尔问题的解 在定义概率时&#xff0c;通常有两种思想流派&#xff1a;贝叶斯主义和频率主义。前者将概率视为我们对事件发生的信念程度&#xff0c;而后者则将其视为事件发生的相对频率。这篇文章介绍了使用贝叶斯和频率主义方法来解决著名的蒙蒂霍尔问…
阅读更多...
IDEA Java 第一个mybatis入门程序

IDEA Java 第一个mybatis入门程序

文章目录 准备mysql 开始新建maven项目maven添加引用mybatis配置文件工具类创建实例类添加mappermappermapper.xml 测试类 发现问题org.apache.ibatis.binding.BindingException: Type interface com.cpyy.mapper.UserMapper is not known to the MapperRegistry.The error may…
阅读更多...
chatGPT国内可用镜像源地址

chatGPT国内可用镜像源地址

chatGPT国内可用镜像源地址 彷丶徨丶 关注 IP属地: 湖北 0.811 2023.03.15 16:02:16 字数 1,152 阅读 249,582 如果你正在尝试访问Chatgpt网站&#xff0c;但由于某些原因无法访问该网站&#xff0c;那么你可以尝试使用Chatgpt的国内镜像网站。以下是一些Chatgpt国内镜像网站的…
阅读更多...
【MYSQL】数据类型和约束

【MYSQL】数据类型和约束

目录 数据类型 1.数值类型 1.1.位--类型bit(M) 1.2. 整数类型--tinyint&#xff0c;smallint&#xff0c;int&#xff0c;bigint 1.3.小数类型--float、decimal 2.字符类型--char、varchar 3.日期类型--datetime、timestamp 4.string类型--enum和set mysql的约束 1.空…
阅读更多...
【人工智能】— 不确定性、先验概率/后验概率、概率密度、贝叶斯法则、朴素贝叶斯 、最大似然估计

【人工智能】— 不确定性、先验概率/后验概率、概率密度、贝叶斯法则、朴素贝叶斯 、最大似然估计

【人工智能】— 不确定性 不确定性不确定性与理性决策基本概率符号先验概率(无条件概率)/后验概率(条件概率)随机变量概率密度联合概率分布公理完全联合分布概率演算独立性 贝叶斯法则例1例2 使用贝叶斯规则&#xff1a;合并证据朴素贝叶斯最大似然估计小结 不确定性 不确定性与…
阅读更多...
PCIe物理层详细总结-PCIE专题知识（一）

PCIe物理层详细总结-PCIE专题知识（一）

目录 一、简介二、PCIe物理层结构及功能2.1 PCIe端对端连接方式2.2 PCIe组成2.2.1 逻辑层(Logic)1 发送逻辑2 接收逻辑 2.2.2 电气层(Electrical)1 物理层-电气(Physical Layer Electrical)2 数据传送----差分方式 2.2.3 PLP介绍 三、其他相关链接1、PCI总线及发展历程总结2、P…
阅读更多...
mockjs学习笔记

mockjs学习笔记

文章目录 一、什么是mockjs二、安装mockj项目安装mock 三、mock语法生成字符串生成文本生成标题和句子生成段落生成数字生成自增id生成姓名-地址-身份证随机生成图片生成时间 mock拦截请求定义get请求定义post请求 四、实现新闻管理案例获取数据添加新闻删除新闻 一、什么是moc…
阅读更多...
最优化方法Python计算：一元函数搜索算法——二分法

最优化方法Python计算：一元函数搜索算法——二分法

设一元目标函数 f ( x ) f(x) f(x)在区间 [ a 0 , b 0 ] ⊆ R [a_0,b_0]\subseteq\text{R} [a0​,b0​]⊆R&#xff08;其长度记为 λ \lambda λ&#xff09;上为单峰函数&#xff0c;且在 ( a 0 , b 0 ) (a_0,b_0) (a0​,b0​)内连续可导&#xff0c;即其导函数 f ′ ( x ) f…
阅读更多...
PySpark基础入门（1）：基础概念＋环境搭建

PySpark基础入门（1）：基础概念＋环境搭建

目录 Spark基础入门 spark基础概念 spark架构 Spark环境搭建 local模式 Standalone 模式 Spark On YARN 模式 PySpark开发环境搭建 Python On Spark 执行原理 更好的阅读体验&#xff1a;PySpark基础入门&#xff08;1&#xff09;&#xff1a;基础概念&#xff0b;环…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站