🌠作者：@TheMythWS.
🎆专栏：《集合和数据结构》
🎇座右铭：不走心的努力都是在敷衍自己，让自己所做的选择，熠熠发光。
目录
👀线性表和顺序表
🔎ArrayList简介
▶ArrayList使用
▶ArrayList常见操作
▶ArrayList的遍历
▶ArrayList的扩容机制
🔎简单的洗牌算法
🔎OJ练习
🔎ArrayList的问题及思考？
线性表和顺序表
线性表：
线性表是具有n(n≥0)个相同类型元素的有限序列
线性表中的元素个数n(n≥0)定义为线性表的长度，n=0时称为空表
对于非空的线性表或线性结构，其特点是：
- 存在唯一的一个被称作”第一个“的数据元素；
- 存在唯一的一个被称作”最后一个“的数据元素；
- 除第一个之外，结构中的每个数据元素均只有一个前驱；
- 除最后一个之外，结构中的每个数据元素均只有一个后继；
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常有顺序存储(类似数组)和链式存储结构。
顺序表：
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。逻辑上相邻的数据元素，其物理次序也是相邻的。只要确定了存储线性表的起始位置，线性表中的任一元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的的存储结构。
优点：查找 ，时间复杂度O(1)
缺点：插入，删除的时间复杂度O(n)（最坏情况），会导致大量元素移动，降低效率
总结：顺序表不太适合对数据进行频繁的增删的场景，适合给定下标，也就是查找的场景。
接口的实现（用动态数组演示顺序表）：
import java.util.Arrays;class IndexOutOfException extends RuntimeException{ public IndexOutOfException() { } public IndexOutOfException(String message) { super(message); }}public class MySeqList { private int[] elem; private int usedSize;//存储了多少个有效的数据 private static final int DEFAULT_SIZE = 10; public MySeqList() { this.elem = new int[DEFAULT_SIZE]; } // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的 public void display() { for (int i = 0; i < this.usedSize; i++) { System.out.print(this.elem[i] + " "); } } // 获取顺序表长度 public int size() { return this.usedSize; } // 判定是否包含某个元素 public boolean contains(int toFind) { for (int i = 0; i < usedSize; i++) { //如果是引用类型，用equals if (this.elem[i] == toFind) { return true; } } return false; } // 查找某个元素对应的位置 public int indexOf(int toFind) { for (int i = 0; i < usedSize; i++) { //如果是引用类型，用equals if (this.elem[i] == toFind) { return i; } } return -1;//数组没有负数下标 } // 新增元素,默认在数组最后新增 public void add(int data) { if (this.isFull()) { this.resize(); } this.elem[this.usedSize] = data; this.usedSize++; } //判断顺序表的元素是否满了 public boolean isFull() { return this.elem.length == this.usedSize; } //扩容 private void resize() { this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length); } // 在 pos 位置新增元素 O(n) public void add(int pos, int data) { checkAddIndex(pos); if (this.isFull()) { this.resize(); } for (int i = usedSize - 1; i >= pos; i--) { this.elem[i + 1] = this.elem[i]; } this.elem[pos] = data; this.usedSize++; } //检查 新增元素 位置合法性 private void checkAddIndex(int pos) { //pos = usedSize可以，是最后一个元素的下一个位置，如果插入元素的下标大于usdSize，说明插入的元素没有直接前驱，不符合顺序表的结构 if (pos < 0 || pos > this.usedSize) { throw new IndexOutOfException("新增元素位置不合法，请检查合法性！"); } } // 获取 pos 位置的元素 public int get(int pos) { checkGetIndex(pos); return this.elem[pos]; } //检查 获取元素 位置合法性 private void checkGetIndex(int pos) { //pos = usedSize不可以，是最后一个元素的下一个位置，这个位置上没有元素 if (pos < 0 || pos >= this.usedSize) { throw new IndexOutOfException("获取元素位置不合法，请检查合法性！"); } } // 给 pos 位置的元素设为 value O(1) public void set(int pos, int value) { checkSetIndex(pos); this.elem[pos] = value; } //检查 设置元素 位置合法性 private void checkSetIndex(int pos) { //pos = usedSize可以，是最后一个元素的下一个位置，这个位置上可以设置元素 if (pos < 0 || pos > this.usedSize) { throw new IndexOutOfException("设置元素位置不合法，请检查合法性！"); } } //删除第一次出现的关键字key O(n) public boolean remove(int toRemove) { int index = indexOf(toRemove); if (index != -1) { for (int i = index; i < this.usedSize - 1; i++) { this.elem[i] = this.elem[i + 1]; } this.usedSize--; this.elem[usedSize] = 0; return true; } else { System.out.println("没有这个数据！"); return false; } } // 清空顺序表 public void clear() { this.usedSize = 0; }}class Test { //这是一个main方法，是程序的入口： public static void main(String[] args) { MySeqList mySeqList = new MySeqList(); mySeqList.add(1); mySeqList.add(2); mySeqList.add(3); mySeqList.add(4); mySeqList.add(5); mySeqList.add(6); mySeqList.add(7); mySeqList.add(8); mySeqList.add(9); mySeqList.remove(10); //mySeqList.clear(); mySeqList.display(); }} 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底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
ArrayList使用
ArrayList的构造：
（1）无参构造：
（2）利用其他 Collection 构建 ArrayList：
（3）指定顺序表初始容量：
ArrayList常见操作
关于subList()需要注意的地方：
关于toString()需要注意的地方：
ArrayList本身当中是没有重写toString()的
toString()可省略
ArrayList的遍历
3种方式遍历：for循环、foreach（底层也是通过迭代器实现的）、迭代器
import java.util.ArrayList;import java.util.ListIterator;public class Main { //这是一个main方法，是程序的入口： public static void main(String[] args) { ArrayList arrayList = new ArrayList<>(); arrayList.add(12); arrayList.add(23); arrayList.add(34); arrayList.add(45); arrayList.add(56); arrayList.add(67); //（1）for循环+下标： for (int i = 0; i < arrayList.size(); i++) { System.out.print(arrayList.get(i) + " "); } System.out.println(); System.out.println("================="); //（2）foreach： for (Integer x : arrayList) { System.out.print(x + " "); } System.out.println(); System.out.println("================="); //（3）迭代器： ListIterator it = arrayList.listIterator(); while (it.hasNext()) { System.out.print(it.next() + " "); } }} 迭代器的原理：
注意：
1. ArrayList最长使用的遍历方式是：for循环+下标 以及 foreach
2. 迭代器是设计模式的一种，后序容器接触多了再给大家铺垫
ArrayList的扩容机制
ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。
1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要库容的大小
- 初步预估按照1.5倍大小扩容
- 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
- 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用copyOf进行扩容
简单的洗牌算法
扑克牌类：
public class Poker { private String suit;//花色 private int rank;//牌面值 public Poker(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; } @Override public String toString() { return String.format("[%s %d]", suit, rank); }} 游戏类：
import java.util.ArrayList;import java.util.List;import java.util.Random;public class Game { private static final String[] SUITS = {"♥", "♣", "♦", "♠"}; //买一副牌 public List buyPoker() { List pokers = new ArrayList<>(52); for (int i = 0; i < 4; i++) { for (int j = 1; j <= 13; j++) { Poker poker = new Poker(SUITS[i], j);//生成扑克牌的对象 pokers.add(poker);//添加扑克牌到牌组里 } } return pokers; } //打乱扑克牌 public void shuffle(List pokers) { for (int i = pokers.size() - 1; i > 0; i--) { Random random = new Random(); int index = random.nextInt(i);//让下标为51的牌和下标在随机数[0,51)之间的牌交换 swap(pokers, i, index); } } private void swap(List pokers, int i, int j) { Poker tmp = pokers.get(i); pokers.set(i, pokers.get(j)); pokers.set(j, tmp); } public List> game(List pokers) { List> hand = new ArrayList<>(); //3个人的牌 List hand1 = new ArrayList<>(); List hand2 = new ArrayList<>(); List hand3 = new ArrayList<>(); hand.add(hand1); hand.add(hand2); hand.add(hand3); //规则：3个人，每人每次摸一张，进行5轮摸牌 for (int i = 0; i < 5; i++) {//轮数 for (int j = 0; j < 3; j++) {//每人每次摸一张 //每次删除pokers中的0下标元素，将删除的元素添加到每个人的hand中 Poker removePoker = pokers.remove(0); hand.get(j).add(removePoker); } } return hand; }} 测试类：
import java.util.List;public class Test { //这是一个main方法，是程序的入口： public static void main(String[] args) { Game game = new Game(); //买牌 List pokers = game.buyPoker(); System.out.println(pokers); //洗牌 System.out.println("洗牌："); game.shuffle(pokers); System.out.println(pokers); //揭牌 System.out.println("揭牌："); List> hand = game.game(pokers); for (int i = 0; i < hand.size(); i++) { System.out.println("第 " + (i + 1) + " 个人的牌：" + hand.get(i)); } System.out.println("剩下的牌："); System.out.println(pokers); }} 图解洗牌算法：
运行结果：
OJ练习
(1)删除某个字符串中的字符
s1:"welcome to themyth"
s2:"come"
要求：删除s1中的字符，这些字符都是s2中出现的。
s1:"wl t thyth"
import java.util.ArrayList;public class Main { //这是一个main方法，是程序的入口： public static void main(String[] args) { ArrayList arrayList = new ArrayList<>(); String s1 = "welcome to themyth"; String s2 = "come"; for (int i = 0; i < s1.length(); i++) { char ch = s1.charAt(i); //注意：contains里面只能是字符串序列，ch是单个字符，ch+""就变成了字符串 if (!s2.contains(ch + "")) { //s2中不包含s1中的字符就添加到list中 arrayList.add(ch); } } //System.out.println(arrayList);//[w, l, , t, , t, h, y, t, h] for (int i = 0; i < arrayList.size(); i++) { System.out.print(arrayList.get(i));//wl t thyth } }} (2)杨辉三角
在屏幕上打印杨辉三角。
1
1 1
1 2 1
1 3 3 1
……........
数组实现：
public class Main { //这是一个main方法，是程序的入口： public static void main(String[] args) { int[][] arr = new int[10][10]; int i = 0; int j = 0; for (i = 0; i < 10; i++) { for (j = 0; j <= i; j++) { if (i == j) { arr[i][j] = 1; } if (j == 0) { arr[i][j] = 1; } if (i >= 2 && j >= 1) { arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1]; } } } for (i = 0; i < 10; i++) { for (j = 0; j <= i; j++) { System.out.print(arr[i][j] + " "); } System.out.println(); } }} ArrayList实现：
做题连接：力扣
思路：
class Solution { public List> generate(int numRows) { List> ret = new ArrayList<>(); List row = new ArrayList<>(); //第一行 row.add(1); ret.add(row); //第二行开始遍历, 假设走到第三行了. for (int i = 1; i < numRows; i++) { List prevRow = ret.get(i - 1);//前一行 List curRow = new ArrayList<>();//当前行(假设已经到了第三行了) curRow.add(1);//第一个1 //中间curRow list的赋值 for (int j = 1; j < i; j++) {//j的活动范围在第一个1之后和最后一个1之间 int x = prevRow.get(j) + prevRow.get(j - 1);//[i][j] = [i-1][j] + [i-1][j-1] curRow.add(x); } curRow.add(1);//最后一个1 ret.add(curRow); } return ret; }} ArrayList的问题及思考？
1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
