数据结构之ArrayList与顺序表（上）

2024-06-07 23:44
文章标签 数据结构 顺序 arraylist

本文主要是介绍数据结构之ArrayList与顺序表（上），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版）

顺序表的学习，点我

上面这篇博文是关于顺序表的基础知识，以及顺序表的实现。

目录

手动实现顺序表的源码：

分析Java 8 的 ArrayList 的源码 

字段：

构造方法：

ArrayList本身的扩容机制和分配内存机制

ArrayList常见操作

ArrayList的遍历 

普通for循环遍历

for-each遍历 

toString方法遍历 

迭代器遍历 

手动实现顺序表的源码：

下面是Java版的顺序表源码：

public class MyArraylist {public int[] elem;public int usedSize;//0//默认容量private static final int DEFAULT_SIZE = 10;public MyArraylist() {this.elem = new int[DEFAULT_SIZE];}/*** 打印顺序表:*   根据usedSize判断即可*/public void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(this.elem[i]+" ");}System.out.println();}// 新增元素,默认在数组最后新增public void add(int data) {// 增加元素之前得先判断数组是否已满if (isFull()) {expansion();}// 尾插数据不需要判断 pos 位置是否合法elem[this.usedSize++] = data;}// 扩容private void expansion() {// 原来数组的2倍扩容this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);}/*** 判断当前的顺序表是不是满的！* @return true:满   false代表空*/public boolean isFull() {// 判断这个数组的有效元素个数是否等于数组的长度return this.usedSize == this.elem.length;}private boolean checkPosInAdd(int pos) {if (pos < 0 || pos > this.usedSize) {return false;}return true;//合法}// 在 pos 位置新增元素public void add(int pos, int data) throws PosofAddException{if (!checkPosInAdd(pos)) {throw new PosofAddException("add(int pos, int data) " +"pos位置不合法");}// 判断是否为尾插if (pos == this.usedSize) {add(data);}else {// 开始移除元素（从后往前移除）for (int i = this.usedSize; i > pos; i--) {this.elem[i] = this.elem[i-1];}// 开始插入数据this.elem[pos] = data;this.usedSize++;}}// 判定是否包含某个元素public boolean contains(int toFind) {// 先判断这个数组是否有元素if (isEmpty()) {return false;}for (int i = 0; i < this.usedSize; i++) {if (this.elem[i] == toFind) {return true;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {if (this.elem[i] == toFind) {return i;}}return -1;}// 获取 pos 位置的元素public int get(int pos) throws PosofGetException{if (pos < 0 || pos > this.usedSize) {throw new PosofGetException("get(int pos)" +"pos位置不合法");}return this.elem[pos];}private boolean isEmpty() {// 有效数据个数为0，就是为空return this.usedSize == 0;}// 给 pos 位置的元素设为【更新为】 valuepublic void set(int pos, int value) throws PosofSetException{// 先得判断这个 pos 位置是否合法if (pos < 0 || pos >= this.usedSize) {throw new PosofSetException("set(int pos, int value)" +"要修改的位置不合法");}this.elem[pos] = value;}/*** 删除第一次出现的关键字key* @param key*/public void remove(int key) throws PosofRemoveException{int pos = indexOf(key); // 下标if (pos < 0) {throw new PosofRemoveException("remove(int key)" +"没有您要删除的数据");}for (int i = pos; i < this.usedSize - 1; i++) {// 后一个位置往前覆盖this.elem[i] = this.elem[i+1];}this.usedSize--;}// 获取顺序表长度public int size() {return this.usedSize;}// 清空顺序表public void clear() {// 由于存放的是基本数据类型，直接清空即可this.usedSize = 0;// 如果存放的是引用数据类型就得通过for循环遍历把数组的内容置为null// 注意：如果直接把数组置为null的话，就会存在安全问题，而且源码也是遍历的方式}
}

异常：

PosofAddException：

public class PosofAddException extends RuntimeException{public PosofAddException() {}public PosofAddException(String msg) {super(msg);}
}

 PosofGetException：

public class PosofGetException extends RuntimeException{public PosofGetException() {}public PosofGetException(String msg) {super(msg);}
}

PosofSetException： 

public class PosofSetException extends RuntimeException{public PosofSetException() {}public PosofSetException(String msg) {super(msg);}
}

PosofRemoveException： 

public class PosofRemoveException extends RuntimeException{public PosofRemoveException() {}public PosofRemoveException(String msg) {super(msg);}
}

分析Java 8 的 ArrayList 的源码 

实现了咱们自己写的顺序表了之后，就该来看Java本身的源码是怎么写的以及与我们的有什么不同？（注意：由于Java 17封装性太强，不好观看源码，因此下面的源码来自Java 8。）

字段：

elementData 就是我们自己实现的 elem 数组。

size 就是 usedSize ，也就是这个数组的有效元素的个数。 

构造方法：

Java 8 实现的顺序表有三个构造方法。 

带有一个 int 类型的参数的构造方法： 

 不带参数的构造方法：

带一个 Collection 类型的参数的构造方法：

下面的是其源码： 

首先，我们得知道Collection 到底是这个啥？ 

根据上面这个图可以得知：Collection 是一个接口。

上面的参数先不看泛型，那就是Collection c  这个意味着只要实现了Collection 接口，就可以被当成实参传过来。而从上图的关系可知：ArrayList 继承了 AbstractLIst 这个抽象类 ，并且实现了LIst这个接口，而 LIst 这个接口拓展了 Collection 这个接口的功能。也就意味着 ArrayList 这个类实现了 Collection 这个接口。那么 ArrayList 就可以被当成参数传过来。

接下来，就是了解 <? extends E> ，？就可以当成是被传过来的 ArrayList 中的泛型，也就是说被传过来的 ArrayList 中的泛型要是 E 或者 E的子类。例如：

了解了这些，我们就来看源码吧。这个源码的大概意思是把传入的 ArrayList 中的元素给全部拷贝到原来的 ArrayList 的后面。

ArrayList本身的扩容机制和分配内存机制

既然我们在创建一个顺序表的时候，原本是空，那么当我们去增加元素的时候，扩容的机制又是如何呢？

上面是分析过程（可忽略），总之，得出了下面这个结论： 

当顺序表为空时，我们如果去增加元素，就会初始化一个大小10的数组。并且数组在满了之后，会按照1.5倍的扩容方式来扩容。如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容。

ArrayList常见操作

ArrayList常用方法
boolean add(E e)尾插e
void add(int index, E element)将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)将c 中的元素进行尾插
E remove(int index)删除 index 位置元素
boolean remove(Object o)删除遇到的第一个o
E get(int index)获取下标index位置元素
E set(int index, E element)将下标 index 位置元素改为 element
void clear()清空
boolean contains(Object o）判断是否在顺序表中
int indexOf(Object o)返回第一个o所在下标
int lastlndexOf(Object o)返回最后一个o的下标
List<E> subList(int fromlndex, int tolndex)截取部分list

大部分方法，我们都很熟悉。因此这里只展示 addAll()方法 和 subList 方法。

addAll () 方法可以实现 ArrayList 的带Collection 类型的参数的构造方法。

从上面打印的结果可以看出来，ArrayList 是重写了toString 方法的。

从这里我们就可以看出来，被分割的数组应该是下面这样：

ArrayList的遍历 

普通for循环遍历

public class Test {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i)+" ");}}
}

for-each遍历 

public class Test {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);for (Integer x : arrayList) {System.out.print(x+" ");}}
}

toString方法遍历 

public class Test {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);System.out.println(arrayList.toString());}
}

迭代器遍历 

public class Test {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);// 调用iterator方法生成一个迭代器，用Iterator<E>来接收Iterator<Integer> integerIterator = arrayList.iterator();// 如果下一个元素有值话，就进入while循环，并且打印下一个值，最后自己往后走while (integerIterator.hasNext()) {System.out.print(integerIterator.next()+" ");}}
}

只要是实现了 Iterator 接口就可以使用迭代器的方式来遍历。就是下面这张图：

好啦！本期 数据结构之ArrayList与顺序表（上）的学习就到此结束啦！我们下一期再一起学习吧！

这篇关于数据结构之ArrayList与顺序表（上）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1040641。

相关文章

python 线程池顺序执行的方法实现

python 线程池顺序执行的方法实现

《python线程池顺序执行的方法实现》在Python中,线程池默认是并发执行任务的,但若需要实现任务的顺序执行,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录方案一：强制单线程（伪顺序执行）方案二：按提交顺序获取结果方案三：任务间依赖控制方案四：队列顺序消
阅读更多...
redis数据结构之String详解

redis数据结构之String详解

《redis数据结构之String详解》Redis以String为基础类型,因C字符串效率低、非二进制安全等问题,采用SDS动态字符串实现高效存储,通过RedisObject封装,支持多种编码方式（如... 目录一、为什么Redis选String作为基础类型？二、SDS底层数据结构三、RedisObject
阅读更多...
Spring Bean初始化及@PostConstruc执行顺序示例详解

Spring Bean初始化及@PostConstruc执行顺序示例详解

《SpringBean初始化及@PostConstruc执行顺序示例详解》本文给大家介绍SpringBean初始化及@PostConstruc执行顺序,本文通过实例代码给大家介绍的非常详细,对大家的... 目录1. Bean初始化执行顺序2. 成员变量初始化顺序2.1 普通Java类（非Spring环境）(
阅读更多...
浅析Spring如何控制Bean的加载顺序

浅析Spring如何控制Bean的加载顺序

《浅析Spring如何控制Bean的加载顺序》在大多数情况下,我们不需要手动控制Bean的加载顺序,因为Spring的IoC容器足够智能,但在某些特殊场景下,这种隐式的依赖关系可能不存在,下面我们就来... 目录核心原则：依赖驱动加载手动控制 Bean 加载顺序的方法方法 1：使用@DependsOn(最直
阅读更多...
Spring如何使用注解@DependsOn控制Bean加载顺序

Spring如何使用注解@DependsOn控制Bean加载顺序

《Spring如何使用注解@DependsOn控制Bean加载顺序》：本文主要介绍Spring如何使用注解@DependsOn控制Bean加载顺序,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录1.javascript 前言2. 代码实现总结1. 前言默认情况下，Spring加载Bean的顺
阅读更多...
Java中JSON格式反序列化为Map且保证存取顺序一致的问题

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》：本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时，需要提供方将Map类型的数据序列化为co
阅读更多...
MySQL中SQL的执行顺序详解

MySQL中SQL的执行顺序详解

《MySQL中SQL的执行顺序详解》：本文主要介绍MySQL中SQL的执行顺序,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql中SQL的执行顺序SQL执行顺序MySQL的执行顺序SELECT语句定义SELECT语句执行顺序总结MySQL中SQL的执行顺序
阅读更多...
SpringBoot中配置文件的加载顺序解读

SpringBoot中配置文件的加载顺序解读

《SpringBoot中配置文件的加载顺序解读》：本文主要介绍SpringBoot中配置文件的加载顺序,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot配置文件的加载顺序1、命令⾏参数2、Java系统属性3、操作系统环境变量5、项目【外部】的ap
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
Spring Boot 配置文件之类型、加载顺序与最佳实践记录

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2