当前位置： 首页 > news >正文

List-顺序表--2

news 2025/1/8 4:55:57

目录

1、ArrayList

2、ArrayList构造方法

3、ArrayList常见方法

4、ArrayList的遍历

5、ArrayList的扩容机制

6、ArrayList的具体使用

6.1、杨辉三角

6.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、ArrayList构造方法

底层代码分析：

1. 带一个参数的构造方法，初始化 ArrayList 时可以指定初始容量

2. 不带参数的构造方法，初始化时分配的是一个空数组

既然没有分配内存，那这个 ArrayList 对象是如何存数据的呢？

^

继续查看 add 方法的原码,得出结论：

结论1：虽然初始化时没有分配内存，但是第一次 add 的时候会分配大小为10的内存

结论2：对于ArrayList来说，当容量满了，采用的扩容方式是1.5倍扩容

^

3. 有通配符的构造方法

参数列表的含义：

Collection：表示传入的参数是 Collection 类型的，实现了Collection接口的类型也可以

<? extends E>：通配符上界，这里表示可以传入的参数类型是 E 或者 E 的子类

^

例如：

ArrayList<Integer> list = new ArrayList<>();

ArrayList<Number> list1 = new ArrayList<>(list);

首先，list 是实现了 Collection 接口的，？：Integer ；E： Number，Integer 是 Number 的子类，list 满足这两个条件，所以可以作为参数正确执行。相当于把 list 表中数据打包给到 list

    public static void main(String[] args) {LinkedList<Integer> list1 = new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);ArrayList<Number> list2 = new ArrayList<>(list1);list2.add(99);list2.add(88);System.out.println(list2); // 输出 [1,2,3,99,88]}

3、ArrayList常见方法

    public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);ArrayList<Number> list123 = new ArrayList<>();list123.addAll(list); // 与上述第三个构造方法类似System.out.println(list123);//123list123.remove(2); // 删除 2 位置元素list123.remove(new Integer(2)); // 删除遇到的第一个 2System.out.println(list123);//23list123.get(0);list123.set(1,2);list123.contains(1);list.add(4);list.add(5);//并不会产生新的对象！List<Integer> list1 = list.subList(1,3); // [1,3)System.out.println(list1);System.out.println("==============");list1.set(0,99);System.out.println(list1);System.out.println(list);}

上述 subList 方法执行结果：

list1：  [99,3]

list：    [1, 99, 3,4, 5]

发现通过 list1 修改，list 也会发生改变，所以 subList 的执行过程并不会产生新的对象，在这个案例中，list1 的起始位置指向 list 的 1 下标

4、ArrayList的遍历

1. for循环+下标

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

2. foreach

^

for(Integer x : list) {
    System.out.print(x+" ");

}
System.out.println();

3. 迭代器

只有实现了 literable 接口的类型，才能使用迭代器；Map 就不能使用，因为他没有实现 literable 接口

Iterator<Integer> it = list.iterator();    --  通用迭代器

Iterator<Integer> it = list.listIterator();    --  List 的专属迭代器

^

//使用 迭代器 遍历集合类 list
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next()+" ");

}

注意：ArrayList最长使用的遍历方式是：for循环+下标 以及 foreach 

5、ArrayList的扩容机制

在上述构造方法中，通过查看 add 方法的底层代码得出结论：ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容

底层代码总结：

1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要库容的大小

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

3. 使用copyOf进行扩容

6、ArrayList的具体使用

6.1、杨辉三角

力扣118

分析 List<List<Integer>> 

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();// 1. 先处理第一行List<Integer> list = new ArrayList<>();list.add(1);ret.add(list);// 2. 从第2行开始计算 每个list当中的数据for(int i = 1;i < numRows;i++) {// 3. 先准备当前行数据List<Integer> curRow =  new ArrayList<>();// 4. 准备当前行的第一个数据curRow.add(1);// 5. 准备当前的中间数据List<Integer> prevRow = ret.get(i-1); // 拿到上一行的数据for(int j = 1; j < i;j++) {// 上一行的当前列 + 上一行的前一列int val = prevRow.get(j) + prevRow.get(j-1);curRow.add(val);}// 6. 准备当前行最后一个数据curRow.add(1);// 7. 把这个数据放到二维数组当中去ret.add(curRow);}return ret;}
}

6.2、简单的洗牌算法

实现这个算法要解决的问题：

1.买一副牌【要生成一副扑克牌】放到哪里？

2.洗牌，怎么洗?

3.揭牌，每个人轮流抓5张牌，怎么抓牌?抓的牌放到哪里？

1. 创建一个 card 类，定义 花色 和 数字 两个属性；生成 get 和 set 方法；生成toString方法

package card;public class Card {private String suit;//花色private int rank;//数字public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public int getRank() {return rank;}public void setRank(int rank) {this.rank = rank;}@Overridepublic String toString() {return suit+":"+rank+" ";}
}

2. 创建 CardDemo 和 Test 类；CardDemo类中定义一个买牌的方法，在Test类中测试

    一共52张牌 1-k，其中1对应A、J对应11、Q对应12、K对应13

 3. 在CardDemo 类中再定义一个花色类，并完善buyCard方法

4. 买完牌后洗牌，这里使用生成随机数的方式，从最后一张牌开始，与随机生成的牌交换

5. 揭牌，3个人每人轮流揭5张，每次揭1张

把三个人的关系用一个二维数组表示

每揭一张牌，就把整副牌的0下标位置删除

CardDemo 类的完整代码

public class CardDemo {private  final String[] suits = {"♥","♠","♦","♣"};/*** 52张 1-K*      J   Q  K*      11 12 13* @return*/public List<Card> buyCard() {List<Card> cardList = new ArrayList<>();for (int i = 0; i < 4; i++) {for (int j = 1; j <= 13; j++) {Card card = new Card(suits[i],j);cardList.add(card);}}return cardList;}public void shuffle(List<Card> cardList) {Random random = new Random();for (int i = cardList.size()-1; i > 0; i--) {int index = random.nextInt(i);//index  i 交换swap(cardList,i,index);}}private void swap(List<Card> cardList,int a,int b) {Card tmp = cardList.get(a);cardList.set(a,cardList.get(b));cardList.set(b,tmp);/*** tmp = a* a = b* b = tmp*/}/*** 揭牌* 3个人 每个人轮流揭牌5张* @param cardList*/public void getCard(List<Card> cardList) {List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();List<Card> hand3 = new ArrayList<>();List<List<Card>> hands = new ArrayList<>();hands.add(hand1);hands.add(hand2);hands.add(hand3);//3个人 轮流抓牌5张 每次揭牌1张for (int i = 0; i < 5; i++) {//j代表人for (int j = 0; j < 3; j++) {Card card = cardList.remove(0);hands.get(j).add(card);}}System.out.println("第1个揭牌如下：");System.out.println(hand1);System.out.println("第2个揭牌如下：");System.out.println(hand2);System.out.println("第3个揭牌如下：");System.out.println(hand3);System.out.println("剩下的牌：");System.out.println(cardList);}
}

Test 类中代码

public class Test {public static void main(String[] args) {CardDemo cardDemo = new CardDemo();List<Card> cardList =  cardDemo.buyCard();System.out.println("买的牌如下：");System.out.println(cardList);System.out.println("洗牌：");cardDemo.shuffle(cardList);System.out.println(cardList);System.out.println("揭牌：");cardDemo.getCard(cardList);}
}

7、顺序表的优缺点

缺点：

  1. 插入数据必须移动其他数据，最坏情况下，就是插入到0位置。时间复杂度O(N)
  2. 删除数据也需要移动数据，最坏情况下，就是删除0位置。时间复杂度O(N)
  3. 扩容之后有可能会浪费空间

优点：在给定下标进行查找的时候，时间复杂度O(1)

总结：顺序表比较适合进行给定下标查找的场景。


http://www.mrgr.cn/news/82717.html

相关文章：

  • 【C++面向对象——类与对象】Computer类（头歌实践教学平台习题）【合集】
  • java.lang.Error: FFmpegKit failed to start on brand:
  • Excel | 空格分隔的行怎么导入excel?
  • 我用Ai学Android Jetpack Compose之TextField
  • 桌面运维岗面试三十问
  • 信息筛查系统的实战开发与实现
  • vue3 vite 动态加载路由遇到的问题
  • [python3]Excel解析库-openpyxl
  • 开源存储详解-分布式存储与ceph
  • [python3]Excel解析库-XlsxWriter
  • Redis 5设计与源码分析读书笔记
  • 33.时间函数相关 C#例子
  • 下载excel
  • node.js之---集群（Cluster）模块
  • 单片机-串转并-74HC595芯片
  • Java虚拟机（Java Virtual Machine，JVM）
  • 学习Video.js
  • K8s高可用集群之Kubernetes集群管理平台、命令补全工具、资源监控工具部署及常用命令
  • 第四、五章补充：线代本质合集（B站：小崔说数）
  • [SAP ABAP] SMARTFORMS表单开发
  • Nginx (40分钟学会，快速入门)
  • 【操作系统不挂科】操作系统期末考试卷＜2＞（单选题＆简答题＆计算与分析题＆程序分析题＆应用题）
  • 01：C语言的本质
  • 深入探索 Kubernetes：从基础概念到实战运维
  • LLM - 使用 LLaMA-Factory 部署大模型 HTTP 多模态服务 教程 (4)
  • 多模态论文笔记——CogVLM和CogVLM2