数据结构--2:ArrayList与顺序表

1.顺序表的创建                 2.常见操作                   3.遍历                  4.扩容机制                  5.例子

1.顺序表的创建

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

2.常见操作

代码实现

import java.util.ArrayList;
import java.util.List;public class Test1 {public static void main(String[] args) {//ArrayList<Integer> arrayList1 = new ArrayList<>();List<Integer> list = new ArrayList<>();//尾插   List 是可以直接打印的. 不像数组, 还需要转成 Stringlist.add(1);list.add(2);list.add(3);list.add(4);list.add(2);System.out.println(list);// add 也可以指定位置来插入. 往下标 2 这个元素之前插入 100. 插入成功之后, 100 元素的下标就是 2 .list.add(2,100);System.out.println(list);// 头插list.add(0, 200);System.out.println(list);// list.add(100, 300); 显然不行. 100 下标太大了.下标越界了;但是可以往 6 这个位置插入. 就相当于尾插.list.add(6, 300);System.out.println(list);//插入一组元素List<Integer> list1 = new ArrayList<>();list1.addAll(list);System.out.println(list1);//按照下标删除  但下标不能超出总长度范围    也可以同时记录一下被删除的元素   返回resultInteger result = list.remove(1);System.out.println(list);System.out.println(result);//按照值来删除   下标也不能超出指定的范围  如果 List 中不包含这个值, 就返回 falseboolean isRemoved = list.remove(Integer.valueOf(1));System.out.println(list);System.out.println(isRemoved);// 虽然是删除 2 这个值, 由于有多个, 实际上只删除了第一个.list.remove(Integer.valueOf(2));System.out.println(list);//但这样可以删除所有2List<Integer> toRemove = new ArrayList<>();toRemove.add(2);list.removeAll(toRemove);System.out.println(list);//获取元素System.out.println(list.get(1));//修改元素list.set(0,100);System.out.println(list);//清空list1.clear();System.out.println(list1);//判断某元素是否存在System.out.println(list.contains(3));//返回第一个元素所在的下标System.out.println(list.indexOf(100));//返回最后一个元素所在的下标System.out.println(list.lastIndexOf(100));//截取部分list  subList   [1,3)  前闭后开System.out.println(list.subList(1,3));System.out.println(list);//subList 操作, 并不是创建一个 "副本" (拷贝一份), 而是得到原始 List 的片段.//注:此处 subList 方法的返回值类型是 List<E>,而不是 ArrayList<E>List<Integer> subList = list.subList(1,3);subList.set(0,1);System.out.println(subList);//针对 subList 修改, 也会影响到原始的 ListSystem.out.println(list);//获取元素个数   sizeSystem.out.println(list.size());list.add(8);System.out.println(list.size());}
}

3.遍历

ArrayList可以使用三种方式遍历:for循环+下标、foreach、使用迭代器

import java.util.ArrayList;
import java.util.Iterator;public class Test3 {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);for(int i = 0; i < list.size(); i++){System.out.println(list.get(i));// list[i] 这样的写法是不行的.}//通过 foreach 遍历.   num 就会依次被赋值成 list 中的每个元素//这里的 num 只能用来 "读" 不能用来 "写"     foreach 本质上就是迭代器写法的简化写法.// 此处 num 是一个临时变量. 不会影响到 List 中的元素的.for(Integer num: list){System.out.println(num);}//数组不具备的方式, 通过 "迭代器" 来遍历.  典型的 Java 风格的迭代器写法. 不仅仅是在集合类里.Iterator<Integer> iterator = list.iterator();while (iterator.hasNext()){//通过 next 获取到 list 中的每个元素. 通过 hasNext 判定是否遍历结束.System.out.println(iterator.next());}}}

4.扩容机制

ArrayList是⼀个动态类型的顺序表,即:在插入元素的过程中会自动扩容

5.例子

5.1 模拟扑克牌

import java.util.ArrayList;
import java.util.Collections;// 通过一个类, 表示 "一张牌"
class Card{private String rank; //点数private String suit; //花色public Card(String rank, String suit){this.rank = rank;this.suit = suit;}// 搞一个 toString, 方便后续打印牌的内容public String toString(){return "(" + suit + rank + ")";}
}public class shi_xian_pukepai {// 通过这个方法创建一副扑克牌. 通过 ArrayList 表示了.  deck--一副牌private static ArrayList<Card> creatDeck() {ArrayList<Card> deck = new ArrayList<>();// 把 4 种花色, 每个花色 13 个牌都创建进去.  不包含大小王String[] suits = {"♠", "♥", "♣", "♦"};for (String suit : suits) {//处理2-10for (int i = 2; i <= 10; i++) {Card card = new Card("" + i, suit);deck.add(card);}//处理JQKAdeck.add(new Card("J", suit));deck.add(new Card("Q", suit));deck.add(new Card("K", suit));deck.add(new Card("A", suit));}return deck;}public static void main(String[] args) {//Card card = new Card("A", "♦");//System.out.println(card);ArrayList<Card> deck = creatDeck();System.out.println(deck);// 洗牌, 标准库有一个现成的方法, shuffle, 就可以完成洗牌. 打乱 ArrayList 中的顺序.// 修改原有的 ArrayList.Collections.shuffle(deck);System.out.println("洗牌后: " + deck);// 发牌, 假设有 3 个玩家, 每个玩家发 5 张牌. (梭哈)   使用三个 ArrayList 表示三个玩家.
//        ArrayList<Card> player1 = new ArrayList<>();
//        ArrayList<Card> player2 = new ArrayList<>();
//        ArrayList<Card> player3 = new ArrayList<>();// 通过类似于 "二维数组" 的方式, 构造二维的 ArrayList.ArrayList<ArrayList<Card>> players = new ArrayList<>();for(int i = 0; i < 3; i++){players.add(new ArrayList<>());}// 发牌, 取出牌堆中的第一张牌, 放到第一个玩家的 ArrayList 中.// 再取出牌堆中的第二张牌, 放到第二个玩家的 ArrayList 中. 以此类推.   发 5 个轮次for(int round = 0; round < 5; round++){for(int i = 0; i < 3; i++){// 取出牌堆中的第一张牌Card card = deck.remove(0);// 放到对应玩家的 ArrayList 中ArrayList<Card> player = players.get(i);player.add(card);}}// 打印每个玩家的牌for(int i = 0; i < 3; i++){ArrayList<Card> player = players.get(i);System.out.println("玩家" + (i+1) + "的牌" + player);}}
}

5.2 杨辉三角

import java.util.ArrayList;
import java.util.List;public class yang_hui_san_jiao {public List<List<Integer>> generate(int numRows) {List<List<Integer>> result = new ArrayList<>();//每次循环,构造一行数据for (int i = 0; i < numRows; i++) {//构造ArrayList 表示当前行List<Integer> row = new ArrayList<>();//填写若干列for (int j = 0; j <= i; j++) {//针对第一列和最后一列 都是1if (j == 0 || j == i) {row.add(1);}//其他情况  先取出上一行  再找到两数相加else {List<Integer> lastRow = result.get(i - 1);int curValue = lastRow.get(j - 1) + lastRow.get(j);row.add(curValue);}}//此时这一行构造完 把这一行都添加到 result 中result.add(row);}return result;}
}

6.模拟实现 ArrayList

代码实现

// 不写成泛型的方式.  只是保存 String 类型的数据~~
// 泛型方式, 写起来更麻烦一些. 未来面试的时候, 一般也都不要写泛型版本的.
public class MyArrayList {private String[] data = null;    // 通过这个数组, 来表示顺序表中的元素private int size = 0;    // 表示有效元素的个数.public MyArrayList() {data = new String[10];}  // 默认的初始容量为 10public MyArrayList(int capacity) {if(capacity <= 10) capacity = 10;data = new String[capacity];}@Overridepublic String toString() {// 把有效元素转为字符串, 并拼接到一起.StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");for (int i = 0; i < size; i++) {stringBuilder.append(data[i]);// 如果 i 是 size - 1, 说明是最后一个元素, 不需要加 , 了.if (i < size - 1)  stringBuilder.append(", ");}stringBuilder.append("]");return stringBuilder.toString();}// 实现扩容操作.private void resize() {// 1. 创建更长的数组, 新的数组容量是之前的 1.5 倍.String[] newData = new String[data.length + (data.length >> 1)];// 2. 把旧数组的元素, 复制到新数组上.for (int i = 0; i < size; i++) { newData[i] = data[i]; }// 3. 使用新数组代替旧数组.data = newData;}// 实现尾插操作. 把新的元素添加到顺序表末尾.  elem 就是 element(元素) 的缩写. 时间复杂度 O(1)// 虽然可能触发扩容 O(N), 但是认为在使用的时候通过设置良好的初始容量, 降低扩容的次数.public void add(String elem) {// 把 elem 放到 data 的最后一个位置上. 也就是下标为 size 的位置.// [0, size) 区间是有效元素.  需要实现扩容逻辑.if (size >= data.length)  resize();  // 扩容操作.data[size] = elem;size++;}// 往中间位置插入. 往 index 元素之前插入, 确保新元素的下标就是 index. 时间复杂度 O(N)public void add(int index, String elem) {// 判定 index 是否合法.  此处是否要写作 index <= 0  或者 index >= size??  边界值都需要重点讨论.// 如果 index 为 0, 意思是插入完毕后, 元素就处于 0 号位置. 就相当于 "头插"// 如果 index 为 size, 意思是插入完毕后, 元素处于 size 号位置. 就相当于 "尾插"if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);if (size >= data.length)  resize();   // 扩容操作.// 把元素放到 index 位置上. 进行搬运, 把 index 之后的元素, 都往后移动一个位置.// 需要从后往前遍历, 代入 size 为 6 的时候, 最后一个元素下标就是 5; 初始的搬运就是把 data[5] 放到 data[6] 上去// 最终的代码就是 data[i+1] = data[i]是写作 i >= index 还是 i > index??for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; }// 把新元素放到 index 位置上data[index] = elem;size++;}// 按照下标删除   返回被删除的元素的值   时间复杂度 O(N)public String remove(int index){if(index < 0 || index >= size)  throw new IndexOutOfBoundsException("Index: " + index + ", size: " + size);// 提前把删除的元素的值保存一份. 否则后面搬运的时候就会覆盖.String elem = data[index];for(int i = index; i < size-1; i++)  data[i] = data[i+1];size--;return elem;}// 按照元素值来删除  如果删除成功, 返回 true. 否则, 返回 false.  如果 elem 本身不存在, 就认为是删除失败. 时间复杂度 O(N)public boolean remove(String elem) {// 先找到 elem 对应的位置在哪里int removePos = 0;// 找到了. i 这个下标就是要删除的元素的位置.for (; removePos < size; removePos++) { if (data[removePos].equals(elem)) break; }// 上述循环结束, 有两种可能:  1. 没找到 elem, i 和 size 相等了.if (removePos == size) return false;//2. 找到了elem  拿着 removePos 进行删除  进行搬运操作.for (int i = removePos; i < size - 1; i++)  { data[i] = data[i + 1]; }size--;//第二点也可以直接服用上一个删除用法  即  remove(removePos)return true;}//获取下标index的元素   时间复杂度 O(1)public String get(int index){if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);return data[index];}//将下标index位置元素设置为element  时间复杂度 O(1)public void set(int index, String element){if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);data[index] = element;}// 删除所有元素.  时间复杂度 O(1)  不需要把数组中的每个元素都设为 null 之类的public void clear() { size = 0; }//遍历, 看 elem 元素是否存在. 存在就返回 true    时间复杂度 O(N)public boolean contains(String elem) {for (int i = 0; i < size; i++) { if(data[i].equals(elem)) return true; }return false;}// 从前往后遍历, 看 elem 元素是否存在. 存在就返回它的第一个下标. 时间复杂度 O(N)public int indexOf(String elem){for(int i = 0; i < size; i++) { if(data[i].equals(elem)) return i; }return -1;}// 从后往前遍历, 看 elem 元素是否存在. 存在就返回它的最后一个下标. 时间复杂度 O(N)public int lastIndexOf(String elem){for(int i = size - 1; i >= 0; i--) { if(data[i].equals(elem)) return i; }return -1;}// 截取[fromIndex, toIndex) 区间的元素.   时间复杂度 O(N)// 创建一个新的 MyArrayList 对象. 把上述区间的元素, 添加到新的对象中即可.public MyArrayList subList(int fromIndex, int toIndex){// 注意边界值. fromIndex 如果为 0, 是合法的情况. toIndex 如果是 size, 也是合法的情况// fromIndex == toIndex 的时候, 也是合法, 得到空的区间.if(fromIndex < 0 || toIndex > size || fromIndex > toIndex)throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + ", toIndex: " + toIndex);MyArrayList subList = new MyArrayList(toIndex-fromIndex);for(int i = fromIndex; i < toIndex; i++){String elem = this.get(i);subList.add(elem);}return subList;}// 测试尾插// 测试代码也很关键. 把每个功能点的测试代码单独拎出来, 作为一个测试方法.// 这种测试的思路称为 "单元测试"private static void text1(){MyArrayList list = new MyArrayList();list.add("Hello");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");System.out.println(list);// 还有办法, 不通过打印, 也能看到 list 中的内容. 借助调试器}// 测试中间位置插入private static void text2(){MyArrayList list = new MyArrayList();list.add(0,"a");list.add(0,"b");list.add(0,"c");list.add(0,"d");list.add(2,"x");System.out.println(list);}// 测试删除操作private static void test3(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");String elem = list.remove(1);System.out.println(elem);System.out.println(list);}private static void test4(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");boolean ret = list.remove("dd");System.out.println(ret);System.out.println(list);}private static void test5(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");System.out.println(list.contains("bb"));}private static void test6(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");System.out.println(list.indexOf("bb"));}private static void test7(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");list.add("dd");System.out.println(list.subList(1,3));}public static void main(String[] args) {test7();}}







本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/web/93897.shtml
繁体地址,请注明出处:http://hk.pswp.cn/web/93897.shtml

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

相关文章

【Kubesphere】K8s容器无法访问内网xx网络问题

问题遇到的现象和发生背景 Kubesphere中运行的一个容器&#xff0c;可以ping通我们公司内网网段172.16.XX.XX&#xff0c;但是在容器内无法ping通192.168.5.XX&#xff0c;但是我在宿主机是可以ping通192.168.5.XX&#xff0c;这个192.168.5.XX是通过xx设备接进来的&#xff0c…

【开发语言】Groovy语言:Java生态中的动态力量

博客目录一、Groovy 的诞生与发展二、核心特性深度解析1. 与 Java 的无缝集成2. 动态类型与可选静态类型3. 强大的集合操作三、Groovy 在实际开发中的应用场景1. 构建自动化&#xff08;Gradle&#xff09;2. 测试开发&#xff08;Spock 框架&#xff09;3. 脚本任务自动化四、…

Obsidian 1.9.10升级

概述 Obsidian发布了更新版本1.9.10&#xff0c;是一次比较大的升级&#xff0c;尤其是增加了一些以前没有的核心插件&#xff0c;尤其是重磅的数据库功能。虽然可能还是比较初期&#xff0c;但是这意味着OB还是往更好的方向进化了。 本文以一些目前的视频教程加自己的实际上手…

内容审计技术

一、 内容审计需求背景1.网络安全法要求明确责任人&#xff1a;制定内部安全管理制度和操作规程&#xff0c;落实安全保护责任。监测、记录并保留日志&#xff1a;采取监测、记录网络运行状态、网络安全事件的技术措施&#xff0c;并按照规定留存相关网络日志不少于六个月。采取…

反序列化漏洞

php反序列化 1.什么是序列化和反序列化 office word是程序 doc/docx是数据 保存word文件&#xff1a;程序--保存(序列化)-->数据文件 打开word文件&#xff1a;程序--加载数据文件-->还原(反序列化) 游戏存档&#xff1a;角色等级&#xff0c;任务&#xff0c;人物坐…

Lecture 4 Mixture of experts课程笔记

什么是MoE?用&#xff08;多个&#xff09;大型前馈网络和一个选择器层取代大型前馈网络。你可以在不影响浮点运算次数的情况下增加专家数量。 MoE受欢迎的原因 相同的浮点运算次数&#xff0c;更多的参数表现更好训练混合专家模型&#xff08;MoEs&#xff09;速度更快训练混…

微服务架构的演进:从 Spring Cloud Netflix 到云原生新生态

过去十年,Spring Cloud 凭借 Netflix 全家桶(Eureka、Ribbon、Hystrix、Zuul 等)几乎成为 Java 微服务的事实标准。但随着这些核心组件逐步停止更新或进入维护模式,微服务架构正经历一场深刻的演进。新的微服务架构更加注重 云原生兼容性、社区活跃度、企业级稳定性和低运维…

网络流量分析——基础知识

文章目录所需技能和知识TCP/IP 堆栈和 OSI 模型基本网络概念常用端口和协议IP 数据包和子层的概念协议传输封装环境与设备常见的流量分析工具BPF 语法执行网络流量分析NTA工作流程NTA工作流程网络 - 第 1-4 层OSI / TCP-IP 模型寻址机制MAC地址IP 寻址IPv4IPv6IPv6 寻址类型IPv…

ansible playbook 实战案例roles | 实现基于 IHS 的 AWStats 访问监控系统

文章目录一、核心功能描述二、roles内容2.1 文件结构2.2 主配置文件2.3 tasks文件内容三、files文件内容四、关键价值免费个人运维知识库&#xff0c;欢迎您的订阅&#xff1a;literator_ray.flowus.cn 一、核心功能描述 这个 Ansible Role 的核心功能是&#xff1a;​实现 ​…

DELL服务器 R系列 IPMI的配置

1、iDRAC功能默认都是关闭&#xff0c;需要在BIOS面启用&#xff0c;首先重启计算机&#xff0c;按F2然后进入BIOS&#xff0c;选择iDRAC Setting进行iDRAC配置 2、重置一下idrac卡-重置才能恢复默认密码 3、进入iDRAC Setting之后&#xff0c;选择设置网络Network 4、启用iDRA…

模式组合应用-桥接模式(一)

写在前面Hello&#xff0c;我是易元&#xff0c;这篇文章是我学习设计模式时的笔记和心得体会。如果其中有错误&#xff0c;欢迎大家留言指正&#xff01;文章为设计模式间的组合使用&#xff0c;涉及代码较多&#xff0c;个人觉得熟能生巧&#xff0c;希望自己能从中学习到新的…

【clion】visual studio的sln转cmakelist并使用clion构建32位

我想在linux上运行,所以先转为cmake工程 例如可以把exe mfc 部分不构建,这样ubuntu就不用移植。 先转cmakelist,而后clion完成win32的构建,与vs构建对比,验证脚本正确性。 Vcxproj2CMake https://github.com/gns333/Vcxproj2CMake cmakeconverter https://github.com/pave…

MySQL之分区功能

序言 随着业务发展&#xff0c;我们维护的项目数据库中的数据可能会越来越大&#xff0c;那么单张表的数据变多后&#xff0c;接口查询效率可能会变慢&#xff0c;那我们就直接照抄大厂常见的分库分表吗&#xff1f;—— 当然不是的&#xff0c;分库分表不是万能的。 分库分表…

java_spring boot 中使用 log4j2 及 自定义layout设置示例

1. log4j2对比 原始Logback 优势 对于 Spring Boot 3.x&#xff0c;Logback 是默认日志框架&#xff0c;但在高并发、异步日志场景下&#xff0c;Log4j2 通常表现更优。当业务百万级用户、微服务、日志量大时&#xff1a; ✅ 1. Logback&#xff08;默认 Spring Boot 集成&am…

记录Webapi Excel 导出

文章目录1、helper2、control3、前端 axios记录webapi excel 导出File示例.NET8.0 NPOI2.731、helper using NPOI.SS.UserModel; using NPOI.XSSF.UserModel; using System.Data; using System.IO; /// <summary> /// 导出EXCEL /// </summary> public class Exce…

VPS服务器安全审计方案:从风险评估到防护实施

随着云计算技术的快速发展&#xff0c;VPS服务器已成为企业信息化建设的重要基础设施。随之而来的安全威胁也日益增多&#xff0c;如何通过专业的安全审计方案保障VPS服务器的稳定运行成为关键课题。本文将系统阐述从漏洞扫描到应急响应的全周期安全审计实施策略&#xff0c;帮…

libmicrohttpd 入门

libmicrohttpd 是一个小型的 C 库&#xff0c;用于在项目中嵌入 HTTP 服务器功能。它设计简单、轻量级&#xff0c;适合需要 HTTP 接口但不想要大型 Web 服务器开销的应用程序。 安装 libmicrohttpd Linux 系统 在基于 Debian/Ubuntu 的系统上&#xff1a; bash sudo apt-…

【网络】使用 DNAT 进行负载均衡时,若未配置配套的 SNAT,回包失败

【网络】iptables 1 概念 【网络】iptables 2 查看规则 【网络】使用 DNAT 进行负载均衡时&#xff0c;若未配置配套的 SNAT&#xff0c;回包失败 【网络】回包路由原理 使用 DNAT 进行负载均衡时&#xff0c;若未配置配套的 SNAT&#xff0c;后端服务器将直接回包给客户端&am…

深入解析GCC:从编译原理到嵌入式底层实战

继续更新编译器底层系列&#xff01;&#xff01;&#xff01;硬核C语言的屠龙之术&#xff1a;从GCC到汇编的底层征途&#xff08;一&#xff09;总纲&#xff1a; 恭喜你&#xff0c;决定踏上这条通往嵌入式大佬的硬核之路。这条路的起点&#xff0c;不是C语言的语法书&#…

最新MySQL面试题(2025超详细版)

2025最新超详细MySQL面试题 文章目录2025最新超详细MySQL面试题[toc]一、 SQL 和基本操作1. SQL的执行顺序2. 如何优化MySQL查询3. 常用的聚合函数4. 数据库事务5. 事务的四大特性(ACID)6. 视图7. MySQL中使用LIMIT子句进行分页8. MySQL中使用变量和用户定义的函数9. MySQL中的…