数据结构与集合源码

目录

一、数据结构

1.1 数据结构概念

1.2 研究对象

1.3 常见存储结构

1.3.1 数组

1.3.2 链表

1.单向链表

2.双向链表

1.3.3 二叉树

1.3.4 栈（FILO，先进后出）

1.3.5 队列（FIFO，先进先出）

二、集合源码

2.1 List

2.1.1 ArrayList

2.1.2 Vector

2.1.3 Linkedlist

2.1.4 小结

2.2 Map

2.2.1 HashMap

2.2.2 LinkedHashMap

2.3 Set

2.4 练习

一、数据结构

1.1 数据结构概念

数据结构，就是一种程序设计优化的方法论，研究数据的`逻辑结构`和`物理结构`以及它们之间相互关系，并对这种结构定义相应的`运算`，目的是加快程序的执行速度、减少内存占用的空间。

1.2 研究对象

研究对象1:数据之间的逻辑关系

  • 集合结构
  • 线性结构:一对一关系
  • 树形结构:一对多关系
  • 图形结构:多对多关系

研究对象2:数据的存储结构(或物理结构)

  • 顺序结构
  • 链式结构
  • 索引结构
  • 散列结构

研究对象3:相关的算法操作

  • 分配资源，建立结构，释放资源
  • 插入和删除
  • 获取和遍历
  • 修改和排序

在开发中，习惯上如下的方式理解存储结构:

  • 线性表(一对一关系):一维数组、单向链表、双向链表、栈、队列
  • 树(一对多关系):各种树。比如:二叉树、B+树
  • 图(多对多关系)
  • 哈希表:比如:HashMap、HashSet

1.3 常见存储结构

1.3.1 数组

  • 数组是一个容器，用于存储一组相同类型的数据。数组在创建时需要指定大小，并且大小在数组创建后不能更改。

// 声明数组
int[] numbers; // 推荐的方式
int numbers[]; // 另一种方式

// 初始化数组
numbers = new int[5]; // 创建一个长度为5的整数数组

// 也可以在声明时直接初始化
int[] numbers = new int[]{1, 2, 3, 4, 5}; // 显式初始化
int[] numbers = {1, 2, 3, 4, 5}; // 简化的初始化

优点

  • 访问速度快：由于数组的元素是连续存储的，因此可以通过索引快速访问元素。
  • 内存利用效率高：数组在内存中是连续存储的，减少了内存碎片。

缺点

  • 固定大小：数组的大小在创建后不可更改，可能导致空间浪费或不足。
  • 插入和删除操作复杂：在数组中插入或删除元素需要移动元素，效率较低。

1.3.2 链表

链表中的基本单位;Node

1.单向链表

结构

  • 数据域：存储节点的数据。
  • 指针域：指向下一个节点的引用。

特点

  • 单向性：每个节点只能向后访问，不能向前访问。
  • 动态大小：链表的大小可以动态调整，适合需要频繁插入和删除的场景。
  • 不连续存储：链表的节点在内存中不必连续存储。

图示：

大体格式：

//创建对象
public class Test1{ @Test public void test(){ Node node1 = new Node("Aa"); Node node2 = new Node("Bb"); node1.next = node2; }
}
//节点类
class Node{Object date; //数据域Node next;//指针域public void setDate(Object date) {this.date = date;}
}

应用场景

  • 当需要频繁插入和删除元素时。
  • 对于元素数量不确定的场景，链表比数组更合适。
2.双向链表

结构

  • 数据域：存储节点的数据。
  • 前驱指针：指向前一个节点的引用。
  • 后继指针：指向下一个节点的引用。

特点

  • 双向性：每个节点可以向前和向后访问，操作灵活。
  • 动态大小：动态调整链表的大小。
  • 占用空间多：相较于单向链表，节点需要更多的空间来存储前驱指针。

图示

大体格式：

public class Dtest {//创建对象@Testpublic void test(){DNode node1 = new DNode("Aa",null,null);DNode node2 = new DNode("Bb",null,node1);DNode node3 = new DNode("Cc",null,node2);node1.next = node2;node2.next = node3;}  }
class DNode {Object data;   // 数据域DNode next;    // 后继指针DNode prev;    // 前驱指针public DNode(Object data) {this.data = data;}public DNode(Object data, DNode next, DNode prev) {this.data = data;this.next = next;this.prev = prev;}
}

应用场景

  • 当需要频繁进行前向和后向遍历时。
  • 适用于需要双向操作的场景，例如浏览器的前进和后退按钮。

1.3.3 二叉树

两个子节点被称为左子节点和右子节点。

节点：

  • 数据
  • 指向左子节点的引用
  • 指向右子节点的引用

二叉树的遍历：

  • 前序遍历：根 -> 左 -> 右
  • 中序遍历：左 -> 根 -> 右
  • 后序遍历：左 -> 右 -> 根
  • 层序遍历：逐层访问，每一层从左到右。

大体格式：

class TreeNode {TreeNode left;Object date;TreeNode right;public TreeNode(Object date) {this.date = date;}public TreeNode(Object date, TreeNode left, TreeNode right) {this.date = date;this.left = left;this.right = right;}
}// 测试
public class BinaryTreeTest {@Testpublic void test1(){TreeNode treeNode = new TreeNode("A",null,null);TreeNode leftNode = new TreeNode("B",null,null);TreeNode rightNode = new TreeNode("V",null,null);treeNode.left = leftNode;treeNode.right = rightNode;}
}

1.3.4 栈（FILO，先进后出）

 栈的基本概念

  • 栈的特性：

    • 只能在栈顶进行插入和删除操作。
    • 具有栈顶和栈底两个指针，栈顶指针指向最近添加的元素，栈底指针指向最早添加的元素。

  • 基本操作：

    • push：将元素压入栈顶。
    • pop：将栈顶元素弹出并返回。
    • peek（或 top）：查看栈顶元素但不弹出。
    • isEmpty：检查栈是否为空。
    • size：获取栈中元素的数量。

图示

使用数组实现栈

class ArrayStack {private int maxSize; // 栈的最大容量private int[] stack; // 存放栈元素的数组private int top; // 栈顶指针// 构造函数public ArrayStack(int size) {this.maxSize = size;this.stack = new int[maxSize];this.top = -1; // 初始时栈为空}// 入栈public void push(int value) {if (top >= maxSize - 1) {throw new RuntimeException("栈空间已满，入栈失败！");}stack[++top] = value;}// 出栈public int pop() {if (isEmpty()) {throw new RuntimeException("栈空间已空，出栈失败！");}return stack[top--];}
}

使用链表实现栈

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedListStack {
    private Node top; // 栈顶节点

    // 构造函数
    public LinkedListStack() {
        this.top = null;
    }

    // 入栈
    public void push(int value) {
        Node newNode = new Node(value);
        newNode.next = top;
        top = newNode;
    }

    // 出栈
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空间已空，出栈失败！");
        }
        int value = top.data;
        top = top.next;
        return value;
    }
}

1.3.5 队列（FIFO，先进先出）

图示

二、集合源码

2.1 List

2.1.1 ArrayList

1.ArrayList的特点:

  • 实现了List接口，存储有序的、可以重复的数据
  • 底层使用0bject[]数组存储
  • 线程不安全的

2.ArrayList源码解析:

2.1 jdk7版本:(以jdk1.7.0_07为例)

/*如下代码的执行:底层会初始化数组，数组的长度为10。

0bject[]elementData= new 0bject[10];*/

ArrayList<String> list = new ArrayList<>();
list.add("AA");   //elementData[0]= "AA";

list.add("BB");   //elementData[1]= "BB";

2.2 jdk8版本:(以jdk1.8.0_271内例)

//如下代码的执行:底层会初始化数组，即:0bject[]elementData= new 0bject[]{};
ArrayList<String> list =new ArrayList<>();
List.add("AA");

//首次添加元素时，会初始化数组elementData= new 0bject[10]; elementData[0]="AA

List.add("BB");       //elementData[1]="BB";

小结：

  • jdk1.7.0_07类似 饿汉式
  • jdk1.8.0_271类似 懒汉式
  • 两者都是：当要添加第11个元素的时候，底层的elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组中的元素复制到新的数组中。

2.1.2 Vector

1.Vector的特点:

  • 实现了List接口，存储有序的、可以重复的数据
  • 底层使用0bject[]数组存储
  • 线程安全的

2.Vector源码解析:(以jdk1.8.0-271为例)

Vector v= new Vector();//底层初始化数组，长度为10.0bject[]elementData = new bject[10];
v.add("AA");//elementData[0] = "AA":
v.add("BB");//elementData[1]="BB";

当添加第11个元素时，需要扩容。默认扩容为原来的2倍

2.1.3 Linkedlist

1.LinkedList的特点:

  • 实现了List接口，存储有序的、可以重复的数据
  • 底层使用双向链表存储
  • 线程不安全的

2.LinkedList在jdk8中的源码解析:

LinkedList<String>list = new LinkedList<>();//底层也没做啥
List,add("AA")://将"AA"封装到一个Node对象1中，list对象的属性first、last都指向此Node对象1。

List.add("BB");//将"BB"封装到一个Node对象2中，对象1和对象2构成一个双向链表，同时last指向此Node对象2。

因为LinkedList使用的是双向链表，不需要考虑扩容问题。

LinkedList内部声明:

private static class Node<E>{E item;Node<E> next;Node<E> prel.
}

2.1.4 小结

  1. Vector基本不使用了。
  2. ArrayList底层使用数组结构，查找和添加(尾部添加)操作效率高，时间复杂度为0(1)，删除和插入操作效率低，时间复杂度为0(n)
  3. LinkedList底层使用双向链表结构，删除和插入操作效率高，时间复杂度为0(1)，查找和添加(尾部添加)操作效率高，时间复杂度为0(n)(有可能添加操作是0(1)

在选择了ArrayList的前提下，

  • new ArrayList():底层创建长度为10的数组。                                             
  • new ArrayList(int capacity):底层创建指定capacity长度的数组。（推荐大体确认数组的长度）

2.2 Map

2.2.1 HashMap

1. HashMap中元素的特点

  • HashMap中的所有的key彼此之间是不可重复的、无序的。所有的key就构成一个Set集合。--->key 所在的类要重写 hashcode()和equals()
  • HashMap中的所有的value彼此之间是可重复的、无序的。所有的value就构成一个Collection集合。--->valve 所在的类要重写 equals()
  • HashMap中的一个 key-value ,就构成了一个 entry。
  • HashMap中的所有的 entry 彼此之间是不可重复的、无序的。所有的entry就构成了一个Set集合。

图示：

2.HashMap源码解析

2.1 jdk7中创建对象和添加数据过程(以JDK1.7.0_07为例说明):

//创建对象的过程中，底层会初始化数组Entry[]table=new Entry[16];
HashMap<String,Integer> map = new HashMap<>();

...
map.put("AA",78);//"AA"和78封装到一个Entry对象中，考虑将此对象添加到table数组中。

...

添加/修改的过程

说明

  • 情况1:将(key1,value1)存放到数组的索引i的位置
  • 情况2,情况3:(key1,valve1)元素与现有的(key2，value2)构成单向链表结构，(key1,value1)指向(key2,vaue2)

注意

随着不断的添加元素，在满足如下的条件的情况下，考虑扩容:

  • (eize >= threshold)&&(null != table[i])

当元素的个数达到临界值(->数组的长度 *加载因子)时，就考虑扩容。

  • 默认的临界值 = 16 *0.75 --> 12
  • 默认扩容为原来的2倍。

2.2 jdk8与jdk7 的区别

2.2.2 LinkedHashMap

1.LinkedHashMap与HashMap 的关系:

  • >LinkedHashMap是HashMap的子类。
  • >LinkedHashMap在HashMap使用的数组+单向链表+红黑树的基础上，又增加了一对双向链表，记录添加的(key，value)的先后顺序。便于我们遍历所有的key-valve。

2.LinkedHashMap重写了HashMap的如下方法：

Node<K,V> newNode(int hash, K key, V value, Node<K,V>  e){
        LinkedHashMap.Entry<K,V> p = new LinkedHashMap.EntrykK,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
}

2.底层结构:LinkedHashMap内部定义了一个Entry

static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before，after;//增加的一对双向链表Entry(int hash, K key, v value, Node<K,V> next){super(hash, key, value, next);}
}

2.3 Set

Hashset底层使用的是HashMap
LinkedHashSet底层使用的是LinkedHashMap

2.4 练习

题目1：分析此map的内存结构

public class BinaryTreeTest {public static void main(String[] args) {HashMap<Integer, String> map = new HashMap<>();map.put(31, "张三");map.put(31,"李四");map.put(47, "王五");map.put(45,"赵六");}
}

解析：

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

基于卷积神经网络的蔬菜识别系统，resnet50，mobilenet模型【pytorch框架+python源码】

基于卷积神经网络的蔬菜识别系统，resnet50，mobilenet模型【pytorch框架+python源码】

更多目标检测和图像分类识别项目可看我主页其他文章 功能演示&#xff1a; 基于卷积神经网络的蔬菜识别系统&#xff0c;resnet50&#xff0c;mobilenet【pytorch框架&#xff0c;python&#xff0c;tkinter】_哔哩哔哩_bilibili &#xff08;一&#xff09;简介 基于卷积神…
阅读更多...
Java设计模式梳理：行为型模式（策略，观察者等）

Java设计模式梳理：行为型模式（策略，观察者等）

行为型模式 行为型模式关注的是各个类之间的相互作用&#xff0c;将职责划分清楚&#xff0c;使得我们的代码更加地清晰。 策略模式 策略模式太常用了&#xff0c;所以把它放到最前面进行介绍。它比较简单&#xff0c;我就不废话&#xff0c;直接用代码说事吧。 下面设计的…
阅读更多...
软件架构之构件复用技术

软件架构之构件复用技术

简介 软件架构复用 在应用软件系统的开发过程中&#xff0c;通常包含以下几个关键阶段&#xff1a;需求分析、设计、编码、测试和维护。在这些阶段中&#xff0c;复用技术均可以得到有效应用。特别是&#xff0c;软件架构复用作为一种大粒度、高抽象级别的复用方式&#xff0…
阅读更多...
55 | 享元模式（下）：剖析享元模式在Java Integer、String中的应用

55 | 享元模式（下）：剖析享元模式在Java Integer、String中的应用

上篇文章&#xff0c;我们通过棋牌游戏和文本编辑器这样两个实际的例子&#xff0c;学习了享元模式的原理、实现以及应用场景。用一句话总结一下&#xff0c;享元模式中的“享元”指被共享的单元。享元模式通过复用对象&#xff0c;以达到节省内存的目的。 今天&#xff0c;我…
阅读更多...
[PHP]重复的Notice错误信息

[PHP]重复的Notice错误信息

<?php $a []; var_dump($a[name]);执行结果&#xff1a; 原因&#xff1a; display_errors和error_reporting都打开了Notice错误信息
阅读更多...
线性回归实现

线性回归实现

1.从数据流水线、模型、损失函数、小批量随机梯度下降优化器 %matplotlib inline import random import torch from d2l import torch as d2l 2.根据带有噪声的线性模型构造人造数据集。使用线性模型参数w [2,-3.4]T、b 4.2和噪声项ε生成数据集及标签 y Xw b ε def …
阅读更多...
windows 上验证请求接口是否有延迟

windows 上验证请求接口是否有延迟

文件名&#xff1a;api_request_script.bat &#xff0c;直接右键点击执行即可。 echo off setlocal:: 配置:: 替换为实际接口URL set "logFilelog.txt" set "errorLogFileerror_log.txt" set "interval3" :: 请求间隔&#xff08;秒&#xff…
阅读更多...
React之组件渲染性能优化

React之组件渲染性能优化

关键词&#xff1a; shouldComponentUpdate、PureComnent、React.memo、useMemo、useCallback shouldComponentUpdate 与 PureComnent shouldComponentUpdate 与 PureComnent 用于类组件。虽然官方推荐使用函数组件&#xff0c;但我们依然需要对类组件的渲染优化策略有所了解…
阅读更多...
面经汇总——第一篇

面经汇总——第一篇

1. int数据类型做了什么优化 Java在处理整数类型时&#xff0c;进行了多种优化&#xff0c;主要体现在编译器层面和JVM层面&#xff0c;目的是提高性能、减少内存开销。 常量池优化 Java中的Integer类有一个缓存机制&#xff0c;对于值在-128到127之间的int数字&#xff0c;Int…
阅读更多...
springBoot集成nacos注册中心以及配置中心

springBoot集成nacos注册中心以及配置中心

一、安装启动nacos 访问&#xff1a;http://127.0.0.1:8848/nacos/index.html#/login 二、工程集成nacos 1、引入依赖 我这里搭建的父子工程哈&#xff0c;在子工程引入 <dependencies><!-- SpringBoot Web --><dependency><groupId>org.sp…
阅读更多...
代码审计-Python Flask

代码审计-Python Flask

1.Jinjia2模版注入 Flask是一个使用 Python 编写的轻量级 Web 应用框架。其 WSGI 工具箱采用 Werkzeug &#xff0c;模板引擎则使用 Jinja2。jinja2是Flask作者开发的一个模板系统&#xff0c;起初是仿django模板的一个模板引擎&#xff0c;为Flask提供模板支持&#xff0c;由于…
阅读更多...
MySQL-30.索引-介绍

MySQL-30.索引-介绍

一.索引 为什么需要索引&#xff1f;当我们没有建立索引时&#xff0c;要在一张数据量极其庞大的表中查询表里的某一个值&#xff0c;会非常的消耗时间。以一个6000000数据量的表为例&#xff0c;查询一条记录的时间耗时约为13s&#xff0c;这是因为要查询符合某个值的数据&am…
阅读更多...
RabbitMQ系列学习笔记（八）--发布订阅模式

RabbitMQ系列学习笔记（八）--发布订阅模式

文章目录 一、发布订阅模式原理二、发布订阅模式实战1、消费者代码2、生产者代码3、查看运行结果 本文参考&#xff1a; 尚硅谷RabbitMQ教程丨快速掌握MQ消息中间件rabbitmq RabbitMQ 详解 Centos7环境安装Erlang、RabbitMQ详细过程(配图) 一、发布订阅模式原理 在开发过程中&…
阅读更多...
SpringBoot+MyBatis+MySQL项目基础搭建

SpringBoot+MyBatis+MySQL项目基础搭建

一、新建项目 1.1 新建springboot项目 新建项目 选择SpringBoot&#xff0c;填写基本信息&#xff0c;主要是JDK版本和项目构建方式&#xff0c;此处以JDK17和Maven举例。 1.2 引入依赖 选择SpringBoot版本&#xff0c;勾选Lombok&#xff0c;Spring Web&#xff0c;MyBa…
阅读更多...
UI自动化测试 —— web端元素获取元素等待实践！

UI自动化测试 —— web端元素获取元素等待实践！

前言 Web UI自动化测试是一种软件测试方法&#xff0c;通过模拟用户行为&#xff0c;自动执行Web界面的各种操作&#xff0c;并验证操作结果是否符合预期&#xff0c;从而提高测试效率和准确性。 目的&#xff1a; 确保Web应用程序的界面在不同环境(如不同浏览器、操作系统)下…
阅读更多...
设计模式和软件框架的关系

设计模式和软件框架的关系

设计模式和软件框架在软件开发中都有助于解决复杂问题和提高代码质量&#xff0c;但它们在概念和使用上存在一些区别。它们的关系可以通过以下几点理解&#xff1a; 层次与抽象程度 设计模式&#xff08;Design Patterns&#xff09;是一组通用的、可复用的解决方案&#xff0c…
阅读更多...
完爆YOLOv10！Transformer+目标检测新算法性能无敌，狠狠拿捏CV顶会！

完爆YOLOv10！Transformer+目标检测新算法性能无敌，狠狠拿捏CV顶会！

百度最近又搞了波大的&#xff0c;推出了一种全新的实时端到端目标检测算法RT-DETRv3&#xff0c;性能&耗时完爆YOLOv10。 RT-DETRv3基于Transformer设计&#xff0c;属于代表模型DETR的魔改进化版。这类目标检测模型都有着强大的扩展性与通用性&#xff0c;因为Transform…
阅读更多...
MySQL—CRUD—进阶—(二) (ಥ_ಥ)

MySQL—CRUD—进阶—(二) (ಥ_ಥ)

文本目录&#xff1a; ❄️一、新增&#xff1a; ❄️二、查询&#xff1a; 1、聚合查询&#xff1a; 1&#xff09;、聚合函数&#xff1a; 2&#xff09;、GROUP BY子句&#xff1a; 3&#xff09;、HAVING 子句&#xff1a; 2、联合查询&#xff1a; 1&#xff09;、内连接…
阅读更多...
基于FPGA的以太网设计（五）

基于FPGA的以太网设计（五）

之前简单介绍并实现了ARP协议&#xff0c;今天简单介绍一下IP协议和ICMP协议。 1.IP协议 IP协议即Internet Protocol&#xff0c;是网络层的协议。 IP协议是TCP/IP协议族的核心协议&#xff0c;其主要包含两个方面&#xff1a; IP头部信息。IP头部信息出现在每个IP数据报中…
阅读更多...
第13篇：无线与移动网络安全

第13篇：无线与移动网络安全

目录 引言 13.1 无线网络的安全威胁 13.2 无线局域网的安全协议 13.3 移动通信中的安全机制 13.4 蓝牙和其他无线技术的安全问题 13.5 无线网络安全的最佳实践 13.6 总结 第13篇&#xff1a;无线与移动网络安全 引言 无线和移动网络的发展为我们的生活带来了极大的便利…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023