数据结构(Java版)第四期：ArrayLIst和顺序表(上)

article/2025/8/15 18:51:56

目录

一、顺序表

1.1. 接口的实现

二、ArrayList简介

2.1. ArrayList的构造

2.2. ArrayList的常见操作

2.3. ArrayList的扩容机制 

三、ArrayList的具体使用

3.1. 洗牌算法

3.2. 杨辉三角

一、顺序表

        上一期我们讲到过，顺序表本质上和数组是差不多的，只不过数组只能访问或修改某个元素，而作为顺序表，需要实现更多的功能。

1.1. 接口的实现

 //新增元素,默认在数组最后新增public void add(int data) {  }// 在pos位置新增元素public void add(int pos, int data) {  }//判定是否包含某个元素public boolean contains(int toFind) { return true; }//查找某个元素对应的位置public int indexOf(int toFind) { return -1; }//获取pos位置的元素public int get(int pos) { return -1; }// 给pos位置的元素设为value 
public void set(int pos, int value) {    
//删除第⼀次出现的关键字key 
public void remove(int toRemove) {    
// 获取顺序表⻓度public int size() { return 0; }
//清空顺序表public void clear() {    
}

二、ArrayList简介

2.1. ArrayList的构造

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//第一种方式，创建ArrayList对象，构造空的顺序表ArrayList<String> arrayList1 = new ArrayList<>();//第二种方式List<String> list = new ArrayList<>();}
}

        其中ArrayList里面，也是实现了List的接口。也就是说，我们完全可以通过向上转型，把List引用指向ArrayList的实例。

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable

        我们来看下面两段代码的，两个都是构造空的顺序表，二者有什么区别呢？第一个是创建了一个盒子，盒子里面为空，而第二个却连盒子都没有。

ArrayList<String> arrayList1 = new ArrayList<>();
ArrayList<String> arrayList2 = null;
//使用arrayList1复制一份，生成arrayList3
ArrayList<String> arrayList3 = new ArrayList<>(arrayList1);
//构造的同时，可以去指定初始容量
ArrayList<String> arrayList4 = new ArrayList<>(10);

        当前构造出来的ArrayList初始容量为10，这里与数组的区别是：数组我们在一开始就规定好了它的容量，不能在进行修改了；而ArrayList的容量可以进行动态扩容，只要机器内存允许，就能一直扩容，把想要的元素容纳进去。

2.2. ArrayList的常见操作

（1）add尾插操作 

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");System.out.println(list);}
}

（2）获取元素个数

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//获取元素个数，数组提供了.length属性获取到元素个数，集合类提供了size()方法获取元素个数List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");System.out.println(list.size());}
}

      事实上，不仅是List，只要是集合类，都可以通过.size来获取长度。

（3）ArrayList的访问和修改

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//获取或者设置list中的元素List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");//进行了自动扩容System.out.println(list.get(0));System.out.println(list.get(1));System.out.println(list.get(2));System.out.println(list.get(3));System.out.println(list.get(4));}
}

        如果我们运行一下，此时也会出现下标越界访问的异常。 

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//获取或者设置list中的元素List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");//进行了自动扩容list.set(0,"eee");System.out.println(list);}
}

（4）ArrayList的遍历

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("aaa");list.add("bbb");list.add("ccc");list.add("ddd");//遍历是可能会进行各种操作的，不一定是打印for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}System.out.println();//for-each写法for (String s : list) {System.out.print(s+" ");}}
}

        并不是所有的类都能写进for-each里面，要求这个类必须能够实现Iterable接口。实现Iterable接口中的iterator方法，得到一个迭代器对象，进行近一步循环遍历。

public interface List<E> extends Collection<E>
public interface Collection<E> extends Iterable<E> 
Iterator<E> iterator();

        迭代也是计算机中的专业术语，可以理解成“逐渐接近目标”。集合类中用到迭代。上面的for-each循环，我们可以看作是以下代码的简化。

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){System.out.println(iterator.next());
}

        hasNext用于判断有没有下一个元素，iterator.next用于取出当前元素，并准备下一个元素。hasNext的工作机理可以如下图所示，按照箭头从上到下依次去遍历。

（5）其他的一些操作

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//通过contains判读元素是否存在List<String> list1 = new ArrayList<>();list1.add("aaa");list1.add("bbb");list1.add("ccc");list1.add("ccc");list1.add("ccc");list1.add("ddd");System.out.println(list1.contains("aaa"));//通过indexOf获取元素第一次出现的位置System.out.println(list1.indexOf("ccc"));//通过lastIndexOf获取元素最后一次出现的位置list1.lastIndexOf("ccc");main1(args);main2(args);main3(args);}public static void main3(String[] args) {List<String> list1 = new ArrayList<>();list1.add("aaa");list1.add("bbb");list1.add("ccc");list1.add("ddd");//按照元素内删除list1.remove("ddd");System.out.println(list1);}public static void main2(String[] args) {List<String> list1 = new ArrayList<>();list1.add("aaa");list1.add("bbb");list1.add("ccc");list1.add("ddd");//按照下标删除元素list1.remove(2);System.out.println(list1);}public static void main1(String[] args) {List<String> list1 = new ArrayList<>();list1.add("aaa");list1.add("bbb");list1.add("ccc");list1.add("ddd");//在任意位置添加元素list1.add(1,"eee");System.out.println(list1);}
}

2.3. ArrayList的扩容机制 

        当ArrayList内存不够时，就会自动申请额外的内存空间。ArrayList内部持有一个数组，设置的初始容量相当于数组的大小。比如说我们初始容量为10，当循环到第11次的时候，发现元素已经满了；add真正写进元素之前，就要创建一个更大的数组。新的数组要把旧的数组里的元素添加进来，新的元素也要添加进新的数组里面，原来旧的数组要进行释放。

三、ArrayList的具体使用

3.1. 洗牌算法

       问题描述：现有一副扑克牌，对其进行洗牌。

      我们先来定义一个Card类，用来表示一张扑克牌。

class Card {public String suit;//表示花色public String rank;//表示点数public Card(String suit, String rank) {this.suit = suit;this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public String getRank() {return rank;}public void setRank(String rank) {this.rank = rank;}@Overridepublic String toString() {return this.suit+this.rank;}
}

        接下来要先把Card这个对象实例化，并用ArrayList把所有的牌添加进去。

public class Main {public static void main(String[] args) {//使用ArrayList表示一副扑克牌}public static ArrayList<Card> CreateDeck() {//创建一副扑克牌ArrayList<Card> deck = new ArrayList<>();String[] suits = {"♠","♦","♥","♣"};//通过两层for循环，第一层先循环花色，第二层在循环点数//每个花色中，生成对应的点数for (String suit:suits){for (int i = 2; i <= 10; i++) {Card cardNum = new Card(suit,""+i);deck.add(cardNum);//添加到扑克牌中}Card cardJ = new Card(suit,"J");Card cardQ = new Card(suit,"Q");Card cardK = new Card(suit,"K");Card cardA = new Card(suit,"A");deck.add(cardJ);deck.add(cardQ);deck.add(cardK);deck.add(cardA);}return deck;}
}

       然后我们调用CreateDeck方法，对这副牌进行一个打印。

public class Main {public static void main(String[] args) {//使用ArrayList表示一副扑克牌ArrayList<Card> deck = CreateDeck();System.out.println(deck);}
}

        接下来是进行洗牌的操作，在Java标准库中，提供了进行洗牌的方法shuffle。 

import java.util.Collections;public class Main {public static void main(String[] args) {//使用ArrayList表示一副扑克牌ArrayList<Card> deck = CreateDeck();System.out.println("原始牌组:"+deck);//洗牌Collections.shuffle(deck);System.out.println("洗牌之后:"+deck);}
}

      我们也可以自己写一个方法，来进行洗牌。

    public static void shuffle(ArrayList<Card> deck){//把整个ArrayList从后往前遍历//每次取一张牌，生成一个随机下标，用当前的拍和随机下标的牌进行交换Random random = new Random();for (int i = deck.size(); i >0 ; i--) {int j = random.nextInt(deck.size());//生成随机下标[0,deck.size)//交换操作Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保tmp拿到i的下标，不能交换的时候发生修改deck.set(i, deck.get(j));deck.set(j, tmp);}}

      下面是发牌，一共有3个人，每个人发5张牌。我们可以看成一个3行5列的一个二维数组。

        ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组//先创建 3 个人手里的牌for (int i = 0; i < 3; i++) {ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌hands.add(hand);//发到每个人手里//已经添加了3个元素进去，但还是长度为0的ArrayList}

       最后是发牌的过程。

        for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {//发牌是轮流的过程.ArrayList<Card> currentHand = hands.get(j);Card card = deck.remove(0);currentHand.add(card);//一次循环，相当于取出一张牌交给玩家}}

 完整代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;class Card {public String suit;//表示花色public String rank;//表示点数public Card(String suit, String rank) {this.suit = suit;this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public String getRank() {return rank;}public void setRank(String rank) {this.rank = rank;}@Overridepublic String toString() {return this.suit+this.rank;}
}public class Main {public static void main(String[] args) {//使用ArrayList表示一副扑克牌ArrayList<Card> deck = CreateDeck();System.out.println("原始牌组:"+deck);//洗牌//Collections.shuffle(deck);System.out.println("洗牌之后:"+deck);ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组//先创建 3 个人手里的牌for (int i = 0; i < 3; i++) {ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌hands.add(hand);//发到每个人手里//已经添加了3个元素进去，但还是长度为0的ArrayList}for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {//发牌是轮流的过程.ArrayList<Card> currentHand = hands.get(j);Card card = deck.remove(0);currentHand.add(card);//一次循环，相当于取出一张牌交给玩家}}//打印每个人的手牌for (int i = 0; i < 3; i++) {System.out.println("第"+i+"个人的手牌"+hands.get(i));}}public static void shuffle(ArrayList<Card> deck){//把整个ArrayList从后往前遍历//每次取一张牌，生成一个随机下标，用当前的拍和随机下标的牌进行交换Random random = new Random();for (int i = deck.size(); i >0 ; i--) {int j = random.nextInt(deck.size());//生成随机下标[0,deck.size)//交换操作Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保tmp拿到i的下标，不能交换的时候发生修改deck.set(i, deck.get(j));deck.set(j, tmp);}}public static ArrayList<Card> CreateDeck() {//创建一副扑克牌ArrayList<Card> deck = new ArrayList<>();String[] suits = {"♠","♦","♥","♣"};//通过两层for循环，第一层先循环花色，第二层在循环点数//每个花色中，生成对应的点数for (String suit:suits){for (int i = 2; i <= 10; i++) {Card cardNum = new Card(suit,""+i);deck.add(cardNum);//添加到扑克牌中}Card cardJ = new Card(suit,"J");Card cardQ = new Card(suit,"Q");Card cardK = new Card(suit,"K");Card cardA = new Card(suit,"A");deck.add(cardJ);deck.add(cardQ);deck.add(cardK);deck.add(cardA);}return deck;}
}

3.2. 杨辉三角

        问题描述：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1: 输入: numRows = 5  输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2: 输入: numRows = 1 输出: [[1]]

       通过上面的图，我们可以总结出以下规律：1.第i行有i+1个列(因为要用二维数组解决，所以把第一行定义第0行)；2.每一行的第一列和最后一列都是1；3.第i行第j列的元素 = 第i-1行第j-1列的元素 + 第i-1行第j列的元素。

完整代码： 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {public List<List<Integer>> generate(int numRows) {//先写一个表示结果的二维数组List<List<Integer>> result = new ArrayList<List<Integer>>();//先来构造行for (int i = 0; i < numRows; i++) {List<Integer> rows = new ArrayList<>();//用到了向上转型。需要往这一行里面里面添加元素for (int j = 0; j < i+1; j++) {if (j==0 || j==i){rows.add(1);} else {List<Integer> prevRow = result.get(i - 1);int current = prevRow.get(j - 1) + prevRow.get(j);rows.add(current);}}//一行构造好了之后，把这一行添加到result中result.add(rows);}return result;}public static void main(String[] args) {Main m = new Main();Scanner num = new Scanner(System.in);int b = num.nextInt();List<List<Integer>> result = m.generate(b);System.out.println(result);}
}

http://www.hkcw.cn/article/PuNyurIQxo.shtml

相关文章

【Qt】：Dialog 对话框

【Qt】：Dialog 对话框

&#x1f4c3;个人主页&#xff1a;island1314 ⛺️ 欢迎关注&#xff1a;&#x1f44d;点赞 &#x1f442;&#x1f3fd;留言 &#x1f60d;收藏 &#x1f49e; &#x1f49e; &#x1f49e; 生活总是不会一帆风顺&#xff0c;前进的道路也不会永远一马平川&#xff0c;如何面…
阅读更多...
【C++】详解vector二维数组的全部操作（超细图例解析！！！）

【C++】详解vector二维数组的全部操作（超细图例解析！！！）

目录 一、前言 二、 深度理解vector 的二维数组&#xff08;重点&#xff01;&#xff09; 三、vector 二维数组的空间理解&#xff08;重点&#xff01;&#xff09; ✨问题分析 ✨如何合理定制vector的内存空间 四、vector 二维数组的初始化 五、vector 二维数组的 添加…
阅读更多...
已解决 javax.xml.transform.TransformerFactoryConfigurationError 异常的正确解决方法，亲测有效！！！

已解决 javax.xml.transform.TransformerFactoryConfigurationError 异常的正确解决方法，亲测有效！！！

已解决 javax.xml.transform.TransformerFactoryConfigurationError 异常的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 目录 一、问题分析 二、报错原因 三、解决思路 四、解决方法 五、总结 博主v&#xff1a;XiaoMing_Java 博主v&#x…
阅读更多...
【Python】FastAPI入门

【Python】FastAPI入门

文章目录 第一节&#xff1a;FastAPI入门一、FastAPI框架介绍什么是ASGI服务&#xff08;WSGI&#xff09;1、补充Web开发1&#xff09;Web前端开发2&#xff09;Web后端开发 二、FastAPI安装1、安装Python虚拟环境2、安装FastAPI 三、第一个FastAPI案例1、访问接口和文档2、接…
阅读更多...
【C++】踏上C++学习之旅（四）：细说“内联函数“的那些事

【C++】踏上C++学习之旅（四）：细说“内联函数“的那些事

文章目录 前言1. "内联函数"被创造出来的意义2. 内联函数的概念2.1 内联函数在代码中的体现2.2 普通函数和内联函数的汇编代码 3. 内联函数的特性&#xff08;重点&#xff09;4. 总结 前言 本章来聊一聊C的创作者"本贾尼"大佬&#xff0c;为什么要创作出…
阅读更多...
C++《string的模拟实现》

C++《string的模拟实现》

在之前的篇章C《string》中我们已经了解了string中关于构造、容量、访问、修改操作等函数的功能&#xff0c;以及初步学习了这些函数的使用该如何使用。通过学习string内的各个函数后我们可以发现在解决一些要使用到字符串的环境下有了string内的这些函数操作能大大简化&#x…
阅读更多...
2025华为OD机试真题最新题库 (B+C+D+E+2025A+2025B卷) + 在线OJ在线刷题使用（C++、Java、Python C语言 JS合集）（正在更新2025B卷，目前已收录710道）

2025华为OD机试真题最新题库 (B+C+D+E+2025A+2025B卷) + 在线OJ在线刷题使用（C++、Java、Python C语言 JS合集）（正在更新2025B卷，目前已收录710道）

2025年&#xff0c;已经开始使用AB卷题库&#xff0c;题目和往期一样&#xff0c;旧题加新题的组合&#xff0c;有题目第一时间更新&#xff0c;大家可以跟着继续学习&#xff0c;目前使用复用题较多&#xff0c;可在OJ上直接找到对应的AB卷学习&#xff0c;可以放心学习&#…
阅读更多...
基于Java的不固定长度字符集在指定宽度和自适应模型下图片绘制生成实战

基于Java的不固定长度字符集在指定宽度和自适应模型下图片绘制生成实战

目录 前言 一、需求介绍 1、指定宽度生成 2、指定列自适应生成 二、Java生成实现 1、公共方法 2、指定宽度生成 3、指定列自适应生成 三、总结 前言 在当今数字化与信息化飞速发展的时代&#xff0c;图像的生成与处理技术正日益成为众多领域关注的焦点。从创意设计到数…
阅读更多...
【C++】 —— 笔试刷题day_29

【C++】 —— 笔试刷题day_29

一、排序子序列 题目解析 一个数组的连续子序列&#xff0c;如果这个子序列是非递增或者非递减的&#xff1b;这个连续的子序列就是排序子序列。 现在给定一个数组&#xff0c;然后然我们判断这个子序列可以划分成多少个排序子序列。 例如&#xff1a;1 2 3 2 2 1 可以划分成 …
阅读更多...
企业微信自建应用实现接收消息和发送消息功能（python）

企业微信自建应用实现接收消息和发送消息功能（python）

# 这一周我不断的琢磨企业微信自建应用并且实现了自建应用的消息接收和发送功能 1.笔记&#xff0c;记录 第一步&#xff1a;打开企业微信后台 https://work.weixin.qq.com 1.1 如果没有企业可以在这里申请&#xff0c;如果有可以直接扫码登录 1.2 打开后台-应用管理-自建应用…
阅读更多...
【Rust多线程】Rust并发编程，如何轻松实现无畏并发

【Rust多线程】Rust并发编程，如何轻松实现无畏并发

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…
阅读更多...
2025粤港澳信息学创新大赛备考指南Python，C++，图形化历年真题训练题

2025粤港澳信息学创新大赛备考指南Python，C++，图形化历年真题训练题

官方指导文件 训练题目 ZCM5:Python小学组-单项选择题 1.小明安装软件的时候发现软件要求Windows环境&#xff0c;这 个要求限制的是? A.操作系统 B.计算机内存 C.网络设置 D.程序语言 答案‌&#xff1a;A. 操作系统 解析‌&#xff1a;软件运行的环境通常指的是操作系统&am…
阅读更多...
【C++指南】“单身狗问题”——只出现一次的数字 系列问题

【C++指南】“单身狗问题”——只出现一次的数字 系列问题

. &#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《C指南》 期待您的关注 文章目录 引言一、只出现一次的数字&#xff08;一&#xff09;简单题目描述解题思路代码实现及解释 二…
阅读更多...
优化 InfluxDB 写入性能：高效批处理策略实战指南

优化 InfluxDB 写入性能：高效批处理策略实战指南

在处理高吞吐量时序数据时&#xff0c;合理运用批处理&#xff08;Batching&#xff09;策略是提升 InfluxDB 写入性能的关键。本文介绍 时间驱动、大小驱动和混合批处理策略&#xff0c;并通过 Python 代码示例展示如何优化数据写入&#xff0c;平衡 延迟与吞吐量。同时&#…
阅读更多...
RedwoodJS：乱拳打倒老师傅 NextJS！

RedwoodJS：乱拳打倒老师傅 NextJS！

RedwoodJS 是一个全栈的 JavaScript/TypeScript 框架&#xff0c;其作用是帮助开发者高效地构建现代化的 Web 应用。它将前端、后端和数据库集成在一起&#xff0c;并使用一种“JAMstack”架构&#xff08;JavaScript、API 和 Markup&#xff09;来构建可扩展的应用程序。 Star…
阅读更多...
【C++】 —— 笔试刷题day_18

【C++】 —— 笔试刷题day_18

一、压缩字符串(一) 题目解析 题目给定一个字符str&#xff0c;让我们将这个字符串进行压缩&#xff1b; **压缩规则&#xff1a;**出现多次的字符压缩成字符数字&#xff1b;例如aaa压缩成a3。如果字符值出现一次&#xff0c;1不用写。 算法思路 这道题总的来说就非常简单了…
阅读更多...
谷歌浏览器如何禁用javaScript

谷歌浏览器如何禁用javaScript

通过禁用js&#xff0c;可以访问一些设置权限的内容。 Chrome 地址栏输入 chrome://settings/content 回车。 找到 JavaScript 选项。 切换为 不允许网站使用 JavaScript。 地址栏输入&#xff1a; chrome://settings/content/javascript?searchJavaScript Firefox 地址栏输入…
阅读更多...
Java从入门到“放弃”（精通）之旅——类和对象全面解析⑦

Java从入门到“放弃”（精通）之旅——类和对象全面解析⑦

Java从入门到“放弃”&#xff08;精通&#xff09;之旅&#x1f680;——类和对象全面解析⑦ 一、面向对象初探 1.1 什么是面向对象&#xff1f; Java是一门纯面向对象的语言(OOP)&#xff0c;在面向对象的世界里&#xff0c;一切皆为对象。面向对象是解决问题的一种思想&am…
阅读更多...
【Golang】第七弹----map

【Golang】第七弹----map

笔上得来终觉浅,绝知此事要躬行 &#x1f525; 个人主页&#xff1a;星云爱编程 &#x1f525; 所属专栏&#xff1a;Golang &#x1f337;追光的人&#xff0c;终会万丈光芒 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 1基本介绍 Go语言中的 map …
阅读更多...
C/C++程序员为什么要了解汇编？了解汇编有哪些好处？如何学习汇编？

C/C++程序员为什么要了解汇编？了解汇编有哪些好处？如何学习汇编？

目录 1、概述 2、从汇编的角度去理解问题的若干实例说明 2.1、使用空指针去访问类的数据成员或调用类的虚函数为什么会引发崩溃？ 2.2、从汇编代码的角度去理解多线程的执行细节，去理解多线程在访问共享资源时为什么要加锁 2.3、使用Windbg静态分析dump时先从崩溃的那条汇…
阅读更多...
推荐文章

Copyright @ 2022~2023