一.线性表 ：
1.线性表（linear list）是n个 具有相同特性的数据元素的有限序列 。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在 物理结构上 并 不一定是连续 的，线性表在 物理上存储时 ，通常以 数组和链式 结构的形式存储。
二.顺序表：
顺序表是用一段物理地址连续的存储单元，依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表底层就是数组。学习时可以画图理解学习。
三.ArrayList的简介 ：
1.在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：
2. ArrayList是以泛型方式实现的，使用时必须要先实例化 ，ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问，
ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
ArrayList实现了Serializable接口，表明ArrayList是支持序列化的 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList
ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
上图我们可以看出ArrayList，继承了很多类，并且扩展了很多接口使用，自身也有很多方法。
四.ArrayList自我实现和使用（这里我们没有用泛型类实现）：
我们可以仿照源码自己去实现，这里我们实现几个常见的方法，（注意ArrayList不止这些方法），自己的ArrayList
下面先来说明一下，自己模仿的每一个类的分配如图：
1.这里是IList接口里的方法：
代码语言：javascript复制package listtest;
/**
* Created with IntelliJ IDEA.
* Description:
* User: 苏
* Date: 2024-06-09
* Time: 20:23
*/
public interface IList {
//判满
public boolean isFull();
// 新增元素,默认在数组最后新增
public void add(int data);
// 在 pos 位置新增元素
public void add(int pos, int data);
// 判定是否包含某个元素
public boolean contains(int toFind);
// 查找某个元素对应的位置
public int indexOf(int toFind);
// 获取 pos 位置的元素
public int get(int pos);
// 给 pos 位置的元素设为 value
public void set(int pos, int value);
//删除第一次出现的关键字key
public void remove(int toRemove);
// 获取顺序表长度
public int size();
// 清空顺序表
public void clear();
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
public void display();
}2.这里是继承了My_ArrayList的类，具体方法构架界面：这里注意：要在某位置插入，这个位置的，前驱一定不能为空
代码语言：javascript复制package listtest;
import java.util.Arrays;
/**
* Created with IntelliJ IDEA.
* Description:
* User: 苏
* Date: 2024-06-09
* Time: 20:10
*/
public class My_ArrayList implements IList {
public int[] array;
public int usedSize;//大小默认就是0，数组的有效长度
public static final int DEFAULT_CAPACITY = 10;//数组的默认长度
public My_ArrayList() {
this.array = new int[DEFAULT_CAPACITY];
}
public boolean isFull() {
return this.usedSize == this.array.length; //满了
}
//扩容
private void grow() {
//2倍扩容
this.array = Arrays.copyOf(this.array, 2*this.array.length);
}
//检查pos位置下标，是否合法
private void checkPosOf(int pos) throws IllegalPos {
if (pos < 0 || pos > this.usedSize) {
throw new IllegalPos("pos位置不合法");
}
}
@Override
public void add(int data) {
if (isFull()) {
//扩容
grow();
}
this.array[this.usedSize ] = data;
}
@Override
public void add(int pos, int data) {
try {
checkPosOf(pos);
if (isFull()) {
//扩容
grow();
}
/**注意以下：
* 要在某位置插入，这个位置的，前驱一定不能为空
*/
//挪动元素
for (int i = 0; i >= pos ; i--) {
this.array[i 1] = this.array[i];
}
//插入
this.array[pos] = data;
usedSize ;
}catch (IllegalPos e) {
e.printStackTrace();
}
}
@Override
public boolean contains(int toFind) {
for (int i = 0; i < usedSize; i ) {
//这里如果是自己，定义的引用类型，那么要用equal比较
if (array[i] == toFind) {
return true;
}
}
return false;
}
@Override
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i ) {
//这里如果是自己，定义的引用类型，那么要用equal比较
if (array[i] == toFind) {
return i;
}
}
return -1;
}
private void checkPosOf2(int pos) throws IllegalPos {
if (pos < 0 || pos >= this.usedSize) {
throw new IllegalPos("pos位置不合法");
}
}
//顺序表判空
public boolean isEmpty() {
return this.usedSize == 0;
}
private void checkOfList() {
if (this.isEmpty()) {
throw new EmptyException("顺序表为空");
}
}
@Override
public int get(int pos) {
try {
//顺序表本来就为空时
this.checkOfList();
checkPosOf2(pos);
return array[pos];
}catch (IllegalPos e) {
e.printStackTrace();
}catch (EmptyException e) {
e.printStackTrace();
}
return -1;
}
//更新
@Override
public void set(int pos, int value) {
try {
//顺序表本来就为空时
this.checkOfList();
checkPosOf2(pos);
array[pos] = value;
}catch (IllegalPos e) {
e.printStackTrace();
}catch (EmptyException e) {
e.printStackTrace();
}
}
@Override
public void remove(int toRemove) {
try {
//判空
this.checkOfList();
//找到要删除的下标
int pos = this.indexOf(toRemove);
if (pos == -1) {
System.out.println("找不到你要删除的元素");
return;
}
for (int i = pos; i < usedSize-1/*这里注意,因为是array[i] = array[i 1]*/; i ) {
this.array[i] = array[i 1];
}
this.usedSize--;
}catch (EmptyException e) {
e.printStackTrace();
}
}
@Override
public int size() {
return this.usedSize;
}
@Override
public void clear() {
//如果是引用类型，要把，引用置为空
/*for (int i = 0; i < this.usedSize; i ) {
this.array[i] = null;
}
this.usedSize = 0;*/
//基本类型直接这样写
this.usedSize = 0;
}
@Override
public void display() {
for (int i = 0; i < usedSize; i ) {
System.out.print(array[i] " ");
}
}
}3.这里是两个自定义异常EmptyException（检查顺序表是否为空）和IllegalPos（检查下标是否合法）：
代码语言：javascript复制package listtest;
/**
* Created with IntelliJ IDEA.
* Description:
* User: 苏
* Date: 2024-06-09
* Time: 22:41
*/
public class IllegalPos extends RuntimeException {
public IllegalPos() {
super();
}
public IllegalPos(String msg) {
super(msg);
}
}package listtest;
/**
* Created with IntelliJ IDEA.
* Description:
* User: 苏
* Date: 2024-06-10
* Time: 12:22
*/
public class EmptyException extends RuntimeException {
public EmptyException() {
super();
}
public EmptyException(String msg) {
super(msg);
}
}使用注意一：使用时ArrayList不传参数，他会Add给你分配内存，可以传另一个定义的顺序表（list）不过需要是，该泛型或泛型子类
使用注意二：ArrayList的遍历：
ArrayList 可以使用三方方式遍历：for循环 下标、foreach、使用迭代器
1.for循环 下标遍历：
代码语言：javascript复制public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
//for循环打印
for (int i = 0; i < list.size(); i ) {
System.out.print(list.get(i) " ");
}
}2.foreach遍历：
代码语言：javascript复制public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
//for each循环打印
for(Integer x/*每一个元素的类型*/: list/*对象引用类型*/) {
System.out.print(x " ");
}
}3.使用迭代器遍历：
代码语言：javascript复制public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
//使用迭代器输出
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
System.out.print(it.next() " ");
}
}五.ArrayList的扩容机制（略）： 有兴趣可以去看看源码，jdk17被一层一层封装看起来麻烦，可以看jdk8
1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要库容的大小，初步 预估按照 1.5倍 大小扩容
如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
3.真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
4. 使用copyOf进行扩容
六.简易的洗牌算法:
1.学了ArrayLisy之后，来看一下其应用，这里的洗牌算法，会用集合来定义二维数组，来把牌分别放到不同玩家手中，接下来有我娓娓到来：
2.老规矩，来看一下，定义的，类的结构：
3.具体实现：
Card类，定义基本的对象和构造方法：
代码语言：javascript复制package card;
/**
* Created with IntelliJ IDEA.
* Description:
* User: 苏李涛
* Date: 2024-06-13
* Time: 20:45
*/
public class Card {
public int rank;//牌的面值
public String suit;//牌的花色
public Card(int rank, String suit) {
this.rank = rank;
this.suit = suit;
}
@Override
public String toString() {
/*return "Card{"
"rank=" rank
", suit='" suit '''
'}';*/
return "{" suit rank "}";
}
}cardDemo类定义，买牌，洗牌，揭牌方法具体如下：
（1）买52张牌：这里注意要，声明Card对象，来通过构造方法来，初始化，每一张牌，每一张牌又有四种花色。
代码语言：javascript复制public class CardDemo {
public static final String[] suits = new String[]{"♥", "♠", "♣", "♦"};
//1.买52张牌
public List<Card> buyCard() {
List<Card> cardList = new ArrayList<>();
//1.买52张牌
for (int i = 1; i <= 13; i ) {
for (int j = 0; j < 4; j ) {
//赋值，增加代码可读
String suit = suits[j];
int rank = i;
//初始化构造方法
Card card = new Card(rank, suit);
cardList.add(card);
}
}
return cardList;
}（2）洗牌：这里巧妙，利用生产随机数，这里也要注意，交换牌时的Swap方法，通过集合来交换，会有一个开区间下标，不在生成随机数的范围内，通过这来打乱牌，我画了一个图来理解：
//2.洗牌
/**
* 生成随机数，区间也是"[)"这样的，
* 所以我们用 i 值，的前面生成随机数，然后和i位置交换
* @return
*/
public List<Card> shuffle(List<Card> cardList ) {
Random random = new Random();
for (int i = cardList.size()-1; i>0; i--) {
int pre = random.nextInt(i);
//这里会有，开区间数，index，这个数每次和随机数交换
//i是下面index的值，也就是开区间的值
swap(cardList, pre, i);
}
return cardList;
}
private void swap(List<Card> cardList, int i/*这个i是生产随机数值的，下标*/, int index/*是开区间下标*/) {
/**注意不能注意写：因为cardList不是数组，是集合里面有数组
*
* cardList tmp = cardList[i]
* index就是，生成随机数的，开区间下标 i
* cardList[i] = cardList[index];
* cardList[index] = tmp
*/
//这个tmp就是，cardList.get(i)里元素的类型
Card tmp = cardList.get(i);
//把生成随机数下标的值，换成，随机数,开区间下标的值
cardList.set(i, cardList.get(index));
cardList.set(index, tmp);
}揭牌：这里注意：定义了一个二维数组，存放玩家揭的牌，也要注意，删除是以集合中覆盖的形式，如图：
//3.揭牌
public List<List<Card>> playCard(List<Card> cardList) {
List<List<Card>> ret = new ArrayList<>();//存放一维数组的二维数组
//下面是三个存放玩家，抽的牌，的一维数组
List<Card> hand0 = new ArrayList<>();
List<Card> hand1 = new ArrayList<>();
List<Card> hand2 = new ArrayList<>();
ret.add(hand0);
ret.add(hand1);
ret.add(hand2);
//每个人每次，抽一张，每人抽5张
for (int i = 0; i < 5; i ) {
for (int j = 0; j < 3; j ) {
//从上往下抽，一个删除一个，放到一维数组中，用二维数（ List<List<Card>>）组访问。
/**
* 注意这里的删除，应该是，顺序表中remove,这个删除是以覆盖的形式
*/
//删除扑克牌对象
Card card = cardList.remove(0);//从0位置开始覆盖
//把删除（覆盖）的扑克牌，放到二维数组中
ret.get(j).add(card);
}
}
return ret;//返回二维数组，用二维数组访问一维数组
}CardTest测试类：
代码语言：javascript复制import card.Card;
import card.CardDemo;
import java.util.ArrayList;
import java.util.List;
/**
* Created with IntelliJ IDEA.
* Description:
* User: 苏李涛
* Date: 2024-06-13
* Time: 20:45
*/
public class CardTest {
public static void main(String[] args) {
//1.买52张牌
CardDemo cardDemo = new CardDemo();
//调用返回值为List<Card>的，泛型方法
List<Card> cardList = cardDemo.buyCard();
System.out.println(cardList);
System.out.println();
System.out.println();
//2.洗牌
List<Card> cardList1 = cardDemo.shuffle(cardList);
System.out.println(cardList1);
System.out.println();
System.out.println();
//3.揭牌
//注意：揭牌的删除是，顺序表里的覆盖
List<List<Card>> cardList2 = cardDemo.playCard(cardList);
for (int i = 0; i < cardList2.size(); i ) {
System.out.println("玩家" (i 1) "的牌: " cardList2.get(i));
}
}
}来看一下输出：
