【数据结构】顺序表与ArrayList

2023-09-22 08:39:38

作者主页：paper jie 的博客

本文作者：大家好，我是paper jie，感谢你阅读本文，欢迎一建三连哦。

本文录入于《JAVA数据结构》专栏，本专栏是针对于大学生，编程小白精心打造的。笔者用重金(时间和精力)打造，将javaSE基础知识一网打尽，希望可以帮到读者们哦。

其他专栏：《算法详解》《C语言》《javaSE》等

内容分享：本期将会对数据结构中的顺序表进行讲解

目录

线性表

顺序表

简单顺序表的模拟实现

集合框架

ArrayList介绍

ArrayList的使用

ArrayList的构造

ArrayList的基本方法

ArrayList的遍历

ArrayList的扩容机制

画图分析

ArrayList的具体使用

顺序表ArrayList存储结构的优缺点

线性表

线性表就是有多个相同属性的数据元素的有限序列。线性表是一种在我们工作中广泛可以使用到的数据结构，常见的线性表：顺序表，链表，栈，队列……

线性表在逻辑上是线性结构，是一条连续的直线。但是它在物理结构上可可能不是连续的。线性表在物理上存储时，一般是以数组和链式结构的方式存储。

顺序表

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

简单顺序表的模拟实现

大家可以移步到我的Gitee上看代码，有点多，这里就不展示了：structure_code/java2023.9.12/src/mylist · 彭子杰/数据结构 - 码云 - 开源中国 (gitee.com)

集合框架

java集合框架，也称为容器，是定义在java.util包下的一组接口interfaces和其实现类class。它是要的作用是将多个元素element置于一个单元中，用于对这些元素进行快速，便捷的存储store，检索retrieve，管理manipulate，即平时我们说的增删查改。

类与接口总览：

ArrayList介绍

在java的集合框架（容器）中，ArrayList就是一个顺序表，它是一个普通的类，实现了List接口，框架如下：

注意：

ArrayList是以泛型方式实现的，使用时需要先实例化

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

ArrayList实现了cloneble接口，表明ArrayList是可以clone的

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

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

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

ArrayList的使用

ArrayList的构造

public class Test {

    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);
    }
}

ArrayList的基本方法

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("JavaSE");
        list.add("JavaWeb");
        list.add("JavaEE");
        list.add("JVM");
        list.add("测试课程");
        System.out.println(list);
// 获取list中有效元素个数
        System.out.println(list.size());
// 获取和设置index位置上的元素，注意index必须介于[0, size)间
        System.out.println(list.get(1));
        list.set(1, "JavaWEB");
        System.out.println(list.get(1));
// 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
        list.add(1, "Java数据结构");
        System.out.println(list);
// 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
        list.remove("JVM");
        System.out.println(list);
// 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
        list.remove(list.size()-1);
        System.out.println(list);
    } // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
        list.add("JavaSE");
        System.out.println(list.indexOf("JavaSE"));
        System.out.println(list.lastIndexOf("JavaSE"));
        // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
        // List<String> ret = list.subList(0, 4);
        System.out.println(ret);
        list.clear();
        System.out.println(list.size());
}

ArrayList的遍历

ArrayList可以使用三个方式来遍历：for循环，foreach，迭代器

    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);
// 使用下标+for遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        } System.out.println();
// 借助foreach遍历
        for (Integer integer : list) {
            System.out.print(integer + " ");
        } System.out.println();
// 使用迭代器遍历        
        Iterator<Integer> it = list.listIterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        } System.out.println();
    }

这里的迭代器是设计模式的一种。

ArrayList的扩容机制

 首选我们来看一段代码：

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            list.add(i);
        }
    }

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

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);
} r
eturn minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (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;
}

画图分析

【总结】

检查是否真正需要扩容，如果是g调用了row准备扩容

估计需要库容的大小

初步按照1.5倍的大小扩容

如果用户需要的大小超过1.5倍，则按照用户所需大小扩容

真正扩容之前检查是否可以扩容成功，防止太大导致扩容失败

使用copyof进行扩容

ArrayList的具体使用

这里举一个简单的洗牌算法：

public class Card {
public int rank; // 牌面值
public String suit; // 花色
@Override
public String toString() {
return String.format("[%s %d]", suit, rank);
}
}

import java.util.List;
import java.util.ArrayList;
import java.util.Random;
public class CardDemo {
public static final String[] SUITS = {"♠", "♥", "♣", "♦"};
// 买一副牌
private static List<Card> buyDeck() {
List<Card> deck = new ArrayList<>(52);
for (int i = 0; i < 4; i++) {
for (int j = 1; j <= 13; j++) {
String suit = SUITS[i];
int rank = j;
Card card = new Card();
card.rank = rank;
card.suit = suit;
deck.add(card);
}
} 
return deck;
}
private static void swap(List<Card> deck, int i, int j) {
Card t = deck.get(i);
deck.set(i, deck.get(j));
deck.set(j, t);
}
private static void shuffle(List<Card> deck) {
Random random = new Random(20190905);
for (int i = deck.size() - 1; i > 0; i--) {
int r = random.nextInt(i);
swap(deck, i, r);
}
}
public static void main(String[] args) {
List<Card> deck = buyDeck();
System.out.println("刚买回来的牌:");
System.out.println(deck);
shuffle(deck);
System.out.println("洗过的牌:");
System.out.println(deck);
// 三个人，每个人轮流抓 5 张牌
List<List<Card>> hands = new ArrayList<>();
hands.add(new ArrayList<>());
hands.add(new ArrayList<>());
hands.add(new ArrayList<>());
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
hands.get(j).add(deck.remove(0));
}
} 
System.out.println("剩余的牌:");
System.out.println(deck);
System.out.println("A 手中的牌:");
System.out.println(hands.get(0));
System.out.println("B 手中的牌:");
System.out.println(hands.get(1));
System.out.println("C 手中的牌:");
System.out.println(hands.get(2));
}
}

顺序表ArrayList存储结构的优缺点

优点

不用为了表达清楚元素之间的关系而增加额外的存储空间。

可以快速地存取表中的任意一个位置的元素

缺点

在任位置删除插入元素的时间复杂度为O(N)，所以需要移动大量的元素

当顺序表长度变化较大时，难以确定存储空间的容量。

容易造成存储空间的碎片，也就是浪费空间。

更多推荐

线性代数的本质(十一)——复数矩阵

文章目录复数矩阵附录极大线性无关组向量叉积复数矩阵矩阵AAA的元素aij∈Ca_{ij}\in\Complexaij​∈C，称为复矩阵。现将实数矩阵的一些概念推广到复数矩阵，相应的一些性质在复数矩阵同样适用。定义：设复矩阵A=(aij)m×nA=(a_{ij})_{m\timesn}A=(aij​)m×n​矩阵Aˉ=(

SkyWalking快速上手（五）——存放在内存、数据持久化

文章目录存放在内存一、概述二、数据存放方式1.指标数据2.跟踪数据三、优势和注意事项四、总结数据持久化一、指标数据的持久化二、跟踪数据的持久化三、注意事项四、总结存放在内存一、概述SkyWalking是一个开源的分布式系统追踪和性能监控工具，用于帮助开发人员和运维人员监控和分析分布式系统的性能问题。在SkyWalkin

SkyWalking入门之Agent原理初步分析

一、简介当前稍微上点体量的互联网公司已经逐渐采用微服务的开发模式，将之前早期的单体架构系统拆分为很多的子系统，子系统封装为微服务，彼此间通过HTTP协议RESETAPI的方式进行相互调用或者gRPC协议进行数据协作。早期微服务只有几个的情况下，我们遇到问题可以直接简单、快速地通过采集日志进行分析，是A服务存在问题还是B

ReadWriteLock（读写锁）和阻塞队列BlockingQueue与同步队列SynchronousQueue

1.ReadWriteLockpackagecom.kuang.rw;importjava.util.HashMap;importjava.util.Map;importjava.util.concurrent.locks.ReadWriteLock;importjava.util.concurrent.locks.R

传导和辐射EMI有什么区别？

当我们设计原型或使用开发板时，通常可以忽略电磁干扰。但EMI在现实生活中的电子设备和系统中是一个重要的主题，工程师有责任确保电路能够在预期的EMI水平下正常运行，并且不会产生过多的EMI。我倾向于将EMI与无线干扰联系起来，考虑到名称，这并不令人惊讶：它被称为电磁干扰，我们自然将其与电磁辐射联系起来。但正如您从本文标题

实在智能携手40+央企，探索财务大模型及数智化实践与应用

“这次培训给我一个最大的感触就是，过去以为AI智能化、大模型技术是很高深的事情。但现在，我们通过RPA等数字化工具，自主根据自己的工作岗位，完成业务自动化流程的开发和设计。AI技术没有想象中的那么难入门。”这是一位参加了“财务大模型及AI+RPA数智化实践与应用”专题研修班的学员，培训后有感而发的心得。探索财务数智化落

基于矩阵分解算法的智能Steam游戏AI推荐系统——深度学习算法应用(含python、ipynb工程源码)+数据集（三）

目录前言总体设计系统整体结构图系统流程图运行环境模块实现1.数据预处理2.模型构建1）定义模型结构2）优化损失函数3.模型训练及保存1）模型训练2）模型保存4.模型应用1）制作页面2）模型导入及调用3）模型应用代码相关其它博客工程源代码下载其它资料下载前言本项目采用了矩阵分解算法，用于对玩家已游玩的数据进行深入分析。它

10年经验之谈 —— 如何做接口测试呢？接口测试有哪些工具？

回想入职测试已经10年时间了，初入职场的我对于接口测试茫然不知。后来因为业务需要，开始慢慢接触接口测试。从最开始使用工具进行接口测试到编写代码实现接口自动化，到最后的测试平台开发。回想这一路走来感触颇深，因此为了避免打算学习接口测试的同学走冤枉路，特此分享我的学习经验。之前我已经在知乎做过几次接口的分享一、接口的重要性

5W2H分析法

1.概念它的历史可以追溯到二战时期的美国陆军兵器修理部，虽然具体由谁发明可能存在争议，但可以肯定的是，这种方法在当时被广泛应用，并被证明是一种非常有效的创新和问题解决方法。5W2H分析法以五个以W开头的英语单词和两个以H开头的英语单词为线索，帮助人们发现问题，寻找解决方案，进行设计构思，从而创新和发明新的项目。它与其他

QT Day5

目录1.针对登入框，新加入了注册功能，使用数据库存储账号密码信息widget.hwidget.cppsecond.hsecond.cpp2.思维导图1.针对登入框，新加入了注册功能，使用数据库存储账号密码信息widget.h#ifndefWIDGET_H#defineWIDGET_H#include<QWidget>#

7.1 实现进程内存块枚举

在Windows操作系统中，每个进程的虚拟地址空间都被划分为若干内存块，每个内存块都具有一些属性，如内存大小、保护模式、类型等。这些属性可以通过VirtualQueryEx函数查询得到。该函数可用于查询进程虚拟地址空间中的内存信息的函数。它的作用类似于Windows操作系统中的TaskManager中的进程选项卡，可以

热文推荐
  1. 基于TensorFlow+CNN+协同过滤算法的智能电影推荐系统——深度学习算法应用(含微信小程序、ipynb工程源码)+MovieLens数据集（七）

    目录前言总体设计系统整体结构图系统流程图运行环境模块实现1.模型训练1）数据集分析2）数据预处理3）模型创建4）模型训练5）获取特征矩阵2.后端Django3.前端微信小程序1）小程序全局配置文件2）推荐电影页面3）个人信息界面以及用户登录记录页面系统测试1.模型损失曲线2.测试效果相关其它博客工程源代码下载其它资料下

  2. 让机器人飞入寻常百姓家丨青源Workshop「人形机器人」观点集锦

    人形机器人并非新事物，早在上世纪70年代，日本早稻田大学加藤一郎就带领团队研发出世界上第一台人形智能机器人——WABOT-1。而去年马斯克Optimus的发布，也对“机器人热”再度推波助澜。人形机器人领域的发展，需要软件和硬件的共同迭代和优化，同时相比于无人驾驶，人形机器人涉及更加复杂的真实世界多模态环境。机器人技术依

  3. Cpp/Qt-day020918Qt

    目录完善登录框点击登录按钮后，判断账号（admin）和密码（123456）是否一致，如果匹配失败，则弹出错误对话框，文本内容“账号密码不匹配，是否重新登录”，给定两个按钮ok和cancel，点击ok后，会清除密码框中的内容，继续进行登录；如果点击cancel按钮，则关闭界面。如果账号和密码匹配，则弹出信息对话框，给出提

  4. CSI及CPHY的学习知识点

    1.CPHY不需要linecoding8b/10b这些线路编码是不需要的，CPHY的三线编码本身就解决了连续0/1的情况。2.CPHY的三线编码使用状态跳变传递信息的有六个线态(wirestate),每一个当前线态都可以跳变到另外5个线态。每一次跳变对应3bitsymbol【跳变有5种可能，用3bit表示，所以3bit

  5. OpenCV自学笔记二十：图像分割和提取

    1、用分水岭算法实现图像分割与提取分水岭算法是一种经典的图像分割算法，用于将图像中的前景和背景进行分离。它基于图像中的灰度值和梯度信息来确定边界，并通过填充区域将图像分割成多个连通的区域。以下是分水岭算法的基本原理：1.预处理：首先对输入图像进行预处理操作，例如灰度化、平滑滤波和边缘检测等，以便更好地捕捉图像的特征。2

  6. 新工具 ！一键无限重置 Jetbrain 2023 最新版系列

    今天逛github，看到了一个新的Jetbrains系列软件的无限30天试用的方法，体验了下，感觉还不错，使用方法很简单。我看介绍软件还处于测试阶段，大家感兴趣的可以试试看。演示软件RubyMine2023.1JetbrainKiller0.5.0使用方法软件名称叫JetbrainKiller，使用方法就是打开软件，一

  7. 基于 Socket 网络编程

    基于Socket网络编程前言一、基于Socket的网络通信传输（传输层）二、UDP的数据报套接字编程1、UDP套接字编程API2、使用UDPSocket实现简单通信三、TCP流套接字编程1、TCP流套接字编程API2、使用TCPSocket实现简单通信3、使用Tcp协议进行网络传输的“五大要点”前言我们再进行网络编程时

  8. VFP保存大文件到MSSQL，最大2G，超过得上手段

    目前社群在聊这个大文件读取的问题，赵总说要把image字段换成BASE64来读取，我就一脸蒙。为什么要转BASE64，体积暴涨三分之一，明显直取更快，200MB文件对单个文件来说，不算大。赵总还写了啥直读程序，于是就来验证一下情况拿出猫框，简单的操作一下建立MSSQL数据库表1生成猫框DAL类DefineClassDa

  9. 思腾云计算

    为推动AI行业的国产化布局，迎合国产化服务器的市场需求，思腾合力推出华思系列服务器。1.前置24盘12GSASEXP硬盘背板，可以插24个3.5/2.5寸SAS/SATA硬盘；2.后置12盘12GSASEXP硬盘背板，可插12个3.5/2.5寸SAS/SATA硬盘，外加4口U.2硬盘背板1套；3.内置2个M.2SATA