JAVA-顺序表ArrayList(实现ArrayList)

ops/2024/11/12 21:12:57/

1.线性表

线性表 （ linear list ） 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构(从内存看来)并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

1.1 什么是List

在集合框架中，List是一个接口，继承自Collection。

Collection也是一个接口，该接口中规范了后序容器中常用的一些方法，具体如下所示：

Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的，具体如下：

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删 改查以及变量等操作。

1.2 List常用方法

List常用方法：

List所有方法：

 

1.3 List的使用

注意：List是个接口，并不能直接用来实例化。

如果要使用，必须去实例化List的实现类。在集合框架中，ArrayList和LinkedList都实现了List接口

2. 顺序表

顺序表是用一段物理地址连续(内存)的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成 数据的增删查改。

2.1 ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：

【说明】

1. ArrayList是以泛型方式实现的，使用时必须要先实例化

2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问

3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的

4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的

5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList

6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

2.2 ArrayList的使用 

2.2.1 ArrayList的构造方法

ArrayList有三个构造方法

无参的构造方法 ：

 

参数为int的构造方法：

泛型参数构造方法:

由于这个方法：套了很多方法不好讲解，我就对参数和最终使用做讲解

 使用：

ArrayList推荐写法：

java">public static void main(String[] args) {// ArrayList创建，推荐写法// 构造一个空的列表List<Integer> list1 = new ArrayList<>();// 构造一个具有10个容量的列表List<Integer> list2 = new ArrayList<>(10);list2.add(1);list2.add(2);list2.add(3);// list2.add("hello");  // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素// list3构造好之后，与list中的元素一致ArrayList<Integer> list3 = new ArrayList<>(list2);// 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难List list4 = new ArrayList();list4.add("111");list4.add(100);}

 2.2.2 ArrayList常见方法

2.2.2.1 add或者addAll

一共有3种方法：

 

2.2.2.2  remove

 

2.2.2.3 get和set

这个很简单就不多说了

 

 2.2.2.4 contains

 判断是否有这个参数

2.2.2.5 indexOf和lastIndexOf

 

2.2.2.6 subList

注意：java中凡是区间都是左闭右开[ , )  也就是说上面代码只能截取到1和2下标 

2.2.2.7 clear

清空顺序表

2.3 ArrayList的遍历

java">public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);//直接sout打印System.out.println("===sout===");System.out.println(list);// 使用下标+for遍历System.out.println("===for===");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();// 借助foreach遍历System.out.println("===foreach===");for (Integer integer : list) {System.out.print(integer + " ");}System.out.println();//迭代器System.out.println("===Iterator===");Iterator<Integer> it1 = list.iterator();while (it1.hasNext()) {System.out.print(it1.next() + " ");}System.out.println();System.out.println("===ListIterator===");//专门给List用的迭代器ListIterator<Integer> it2 = list.listIterator();while(it2.hasNext()){System.out.print(it2.next() + " ");}System.out.println();System.out.println("===ListIterator 倒着打印===");ListIterator<Integer> it3 = list.listIterator(list.size());while (it3.hasPrevious()) {System.out.print(it3.previous() + " ");}System.out.println();}

这里面迭代器可能大家看不懂我给大家说明一下：

那hasprevious其实是判断前面是否还有？是true否false

previous向前移一位，sout并打印

 

2.4 ArratList扩容机制

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式：

java">Object[] elementData;   // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // 默认空间
private static final int DEFAULT_CAPACITY = 10;  // 默认容量大小
public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {// 获取旧空间大小int oldCapacity = elementData.length;// 预计按照1.5倍方式扩容int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
比特就业课if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 调用copyOf扩容elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {// 如果minCapacity小于0，抛出OutOfMemoryError异常if (minCapacity < 0)throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

【总结】

1. 检测是否真正需要扩容，如果是调用grow准备扩容

2. 预估需要库容的大小

  • 初步预估按照1.5倍大小扩容
  • 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
  • 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

3. 使用copyOf进行扩容

 

3. 实现顺序表

简单实现一下顺序表的大概

把要实现的方法都放在接口中：

java">public interface IList {// 新增元素,默认在数组最后新增void add(int data);// 在 pos 位置新增元素void add(int pos, int data);// 判定是否包含某个元素boolean contains(int toFind);// 查找某个元素对应的位置int indexOf(int toFind);// 获取 pos 位置的元素int get(int pos);// 给 pos 位置的元素设为 value -> 更新void set(int pos, int value);//删除第一次出现的关键字keyvoid remove(int toRemove);// 获取顺序表长度int size();// 清空顺序表void clear();// 打印顺序表，// 注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的void display();
}

在用类去实现此接口，后面所有的方法都在此类中实现：

java">public class MyArrayList implements IList{private int[] array;//存放数据private int size;//用来记录元素个数//实现一个构造方法，默认初始化为大小为10public MyArrayList(){this.array = new int[10];}
}

size会默认为0，所有不用对他初始化

3.1 实现add

我们有size实现作为记录元素个数的下标，当刚好可以做为尾插的位置

 

但如果刚好满了，我们就需要扩容所以，可以用单独写一个方法判断一下

java">   @Overridepublic void add(int data) {if(isFull()){//拷贝原有元素并，扩容两倍this.array = Arrays.copyOf(array,size * 2);}this.array[size] = data;this.size++;}@Overridepublic boolean isFull() {if(array.length == size){return true;}return false;}

利用Arrays.copyOf进行扩容，他不仅可以拷贝原有的元素，还可以进行扩容操作。

 

那么在来做指定位置插入:

想要在指定位置插入，但是又不删除原位置的数据，就必须要移动

想要达到此效果，就需要从有效数据最后位置一个一个往后移动最终直接用给定的下标进行插入就可以了。

但是一旦有下标就需要进行判断下标是否合法：

java">    @Overridepublic void add(int pos, int data) {try {checkPosOfAdd(pos);//检查pos是否合法}catch (PosNotLegalException e) {e.printStackTrace();}//移动原数组for (int i = size-1; i >= pos; i--) {this.array[i + 1] = this.array[i];}this.array[pos] = data;this.size++;}private void checkPosOfAdd(int pos) {if(pos > size || pos < 0) {throw new PosNotLegalException("位置不合法");}}

注意：

尾插是可以做到的，所以判断pos合法性的时候 pos == size的位置可以不做判断

异常：

java">public class PosNotLegalException extends RuntimeException{public PosNotLegalException() {}public PosNotLegalException(String mag) {super(mag);}
}

3.2 实现contains

java">    @Overridepublic boolean contains(int toFind) {for (int i = 0; i < size; i++) {if(array[i] == toFind) {return true;}}return false;}

3.3 实现indexOf 

java">    @Overridepublic int indexOf(int toFind) {for (int i = 0; i < size; i++) {if(array[i] == toFind) {return i;}}return -1;}

3.4 实现get

java">    @Overridepublic int get(int pos) {try {checkPosOfGetAndSet(pos);//检查pos位置是否合法}catch (PosNotLegalException e) {e.printStackTrace();}return this.array[pos];}private void checkPosOfGetAndSet(int pos) {if(pos >= size || pos < 0) {throw new PosNotLegalException("Get/Set位置不合法");}}

3.5 实现set

java">    @Overridepublic void set(int pos, int value) {try {checkPosOfGetAndSet(pos);}catch (PosNotLegalException e) {e.printStackTrace();}array[pos] = value;}

3.6 实现remove

直接用indexOf判断是否有这个数据,有就从pos后面的数据一个个向前移动，但是最后的那个元素还是会在原位置上，不用担心size-1就可以做到删除了，再次add数据就会覆盖到他

java">    @Overridepublic void remove(int toRemove) {int pos = indexOf(toRemove);if(pos == -1) {System.out.println("没有要删除的数字");return;}for (int i = pos; i < size; i++) {array[i] = array[i+1];}this.array[size] = 0;this.size--;}

 3.7 实现size

java">    @Overridepublic int size() {return this.size;}

3.8 实现clear

java">    @Overridepublic void clear() {for (int i = 0; i < size; i++) {this.array[i] = 0;
//            this.array[i] = null;   如果顺序表是指针类型需要全部置为空
//        因为，只要没有引用这篇空间的引用，才会释放}this.size = 0;}

3.9 实现display

java">    @Overridepublic void display() {for (int i = 0; i < size; i++) {System.out.print(array[i] + " ");}System.out.println();}


http://www.ppmy.cn/ops/132695.html

相关文章

设计模式-七个基本原则之一-开闭原则 + SpringBoot案例

设计模式-七个基本原则之一-开闭原则 + SpringBoot案例

开闭原则:(SRP) 面向对象七个基本原则之一 对扩展开放&#xff1a;软件实体&#xff08;类、模块、函数等&#xff09;应该能够通过增加新功能来进行扩展。对修改关闭&#xff1a;一旦软件实体被开发完成&#xff0c;就不应该修改它的源代码。 要看实际场景&#xff0c;比如组内…
阅读更多...
（自用复习题）常微分方程08

（自用复习题）常微分方程08

题目来源 常微分方程(第四版) (王高雄,周之铭,朱思铭,王寿松) 高等教育出版社 书中习题4.1 对应知识 非齐次线性微分方程 3.已知齐次线性微分方程的基本解组 x 1 , x 2 x_1,x_2 x1​,x2​&#xff0c;求下列方程对应的非齐次线性微分方程的通解 三道题都是常数变易法 (1)…
阅读更多...
PHP常用的安全函数作用

PHP常用的安全函数作用

在PHP开发中&#xff0c;安全是非常重要的一个方面。以下是一些常用的PHP安全函数及其作用&#xff1a; 这些函数和方法有助于提升PHP应用的安全性&#xff0c;但安全是一个综合性的问题&#xff0c;需要综合使用多种手段&#xff0c;如输入验证、输出编码、会话管理、错误处理…
阅读更多...
最长公共子序列python

最长公共子序列python

一、问题描述 一个序列的子序列是在该序列中删去若干元素后得到的序列。例:“ABCD”和“BDF”都是“ABCDEFG”的子序列。 最长公共子序列(LCS)问题:给定两个序列X和Y&#xff0c;求X和Y长度最大的公共子序列 例:X"ABBCBDE" Y"DBBCDB" LCS(X,Y)"BB…
阅读更多...
PySide6百炼成真（6）

PySide6百炼成真（6）

布局控件 布局用处的介绍 常用的三种布局 垂直布局水平布局格子布局 项目&#xff1a;使用格子布局重新制作一个计算器 项目&#xff1a;重新制作进制转换器 其实还有一种布局QFormLayout但是后期开发用的比较少 from PySide6.QtWidgets import QApplication, QWidget, QVB…
阅读更多...
基于混沌序列和小波变换层次化编码的遥感图像加密算法matlab仿真

基于混沌序列和小波变换层次化编码的遥感图像加密算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 基于小波变换层次化编码的遥感图像加密算法matlab仿真。分析加解密处理后图像的直方图&#xff0c;相关性&#xff0c;熵&#xff0c;解密后图像质量等。 2.测试…
阅读更多...
sql速度优化多条合并为一条语句

sql速度优化多条合并为一条语句

在 SQL 中&#xff0c;结合 CASE 和 SUM 可以实现根据特定条件进行分组求和。在 ThinkPHP 中也可以使用类似的方式进行数据库查询操作。 例如&#xff0c;假设有一个销售数据表&#xff0c;包含字段 product_id &#xff08;产品 ID&#xff09;、 quantity &#xff08;销…
阅读更多...
B2119 删除单词后缀

B2119 删除单词后缀

B2119 删除单词后缀 #include <iostream> using namespace std; # include <string.h> #include <ctype.h> #include <algorithm> #include <string.h> int main(){ string word; cin>>word; if(word.size()> 2 && word.…
阅读更多...
最新文章

Copyright @ 2022~2023