数据结构2-集合类ArrayList与洗牌算法

★引言：

该篇博客带大家一起模拟实现一个简易版集合ArrayList，并结合洗牌算法来验证正确性，喜欢的话可以点赞和收藏

一. MyArrayList模拟实现

（一）IList

1. 查看ArrayList源码可以发现：ArrayList继承了抽象类AbstractList，而AbstractList又实现了List接口
2. 这里我们省去AbstractList的过程，直接实现一个IList接口，让ArrayList重写接口当中的方法

package list;/*** Created with IntelliJ IDEA.* Description:* User: 32309* Date: 2025-07-20* Time: 15:57*/
public interface IList<T> {// 新增元素,默认在数组最后新增public void add(T data) ;public void add(int pos, T data) ;public boolean contains(Object toFind) ;public int indexOf(Object toFind) ;// 获取 pos 位置的元素public Tget(int pos) ;public void set(int pos, T value) ;//删除第⼀次出现的关键字keypublic boolean remove(Object toRemove) ;// 获取顺序表⻓度public int size() ;// 清空顺序表public void clear() ;// 打印顺序表，注意：该⽅法并不是顺序表中的⽅法，为了⽅便看测试结果给出的public void display();
}

（二）MyArrayList

1. 首先我们要创建一个Object数组，用来接收所有类型，以及实际使用数量count和默认容量DEFAULT_CAPACITY

public class MyArrayList<T> implements IList<T> {private Object[] array;private int count;private final int DEFAULT_CAPACITY = 10;
}

2. 提供两个构造方法，带容量参数initcapacity，new一个用户想要容量的数组，与不带参数的构造方法，new默认容量的数组

/*** Created with IntelliJ IDEA.* Description:* User: 32309* Date: 2025-07-20* Time: 15:55*/
public class MyArrayList<T> implements IList<T> {private Object[] array;private int count;private final int DEFAULT_CAPACITY = 10;// 默认构造⽅法public MyArrayList() {array = new Object[DEFAULT_CAPACITY];}// 将顺序表的底层容量设置为initcapacitypublic MyArrayList(int initcapacity) {if (initcapacity > 0) {array = new Object[initcapacity];return;}array = new Object[DEFAULT_CAPACITY];}
}

（1）add(T data)

1. 这里我们默认采用尾插法，尾插法的时间复杂度为O(1)，更为快捷
2. 在插入数据之前我们首先要判断的就是，数组是否满了 isFull，满了就要扩容 grow

   // 默认尾插@Overridepublic void add(T data) {if (isFull()) {grow();}array[count++] = data;}// 扩容private void grow() {array = Arrays.copyOf(array,count << 1);}// 判满private boolean isFull() {return count == array.length;}

（2）add(int pos, T data)

1. 指定下标插入，是add的重载方法
2. 插入之前同样要判满与扩容
3. 检查下标是否合法 checkPos1
4. 下标不合法要抛出异常 IllgalPosException
5. 插入时采用从后向前覆盖的方式，给pos位置留出位置

 // 在 pos 位置新增元素@Overridepublic void add(int pos, T data) {if (isFull()) {grow();}if (checkPos(pos)) {throw new IllgalPosException("pos下标不合法：" + pos);}// 从后往前覆盖for (int i = count - 1; i >=  pos; i--) {array[i + 1] = array[i];}array[pos] = data;count++;}// 检查下标是否合法private boolean checkPos1(int pos) {if (pos < 0 || pos > count) {return true;}return false;}

（3）IllgalPosException

下标不合法异常

package list;/*** Created with IntelliJ IDEA.* Description:* User: 32309* Date: 2025-07-20* Time: 16:41*/
public class IllgalPosException extends RuntimeException{public IllgalPosException() {}public IllgalPosException(String message) {super(message);}
}

（4）indexOf(Object toFind)

1. 查找对应位置传入值的下标
2. 遍历数组查找到返回下标，找不到返回-1，因为数组下标没有-1
3. 注意：这里面比较值是否相等要调用 equals方法，不能用 **==**直接比较

    // 查找某个元素对应的位置@Overridepublic int indexOf(Object toFind) {for (int i = 0; i < count; i++) {if (array[i].equals(toFind)) {return i;}}return -1;}

（5）contains(Object toFind)

1. 查找数组中是否有这个值
2. 直接调用 indexOf方法，根据返回的下标来判断是否存在

   // 判定是否包含某个元素@Overridepublic boolean contains(Object toFind) {int index = indexOf(toFind);return index != -1;}

（6）get(int pos)

1. 获取 pos 位置的元素的方法
2. 判断 pos位置是否合法，不合法抛出异常，合法就返回该下标的值

    // 判断下标知否合法private boolean checkPos2(int pos) {if (pos < 0 || pos >= count) {return true;}return false;}// 获取 pos 位置的元素@Overridepublic T get(int pos) {if (checkPos2(pos)) {throw new IllgalPosException("下标位置不合法！！！");}else {return (T) array[pos];}}

（7）set(int pos, T value)

1. 给 pos 位置的元素设为 value的方法
2. 先判断 pos 是否合法，再设置值

    // 给 pos 位置的元素设为 value@Overridepublic void set(int pos, T value) {if (checkPos2(pos)) {throw new IllgalPosException("下标位置不合法！！！");}array[pos] = value;}

（8）remove(Object toRemove)

1. 删除第⼀次出现的关键字key的方法
2. 先判断数组有没有这个值
3. 采用从前向后覆盖方式，同时注意将末尾位置置为null

    // 删除第⼀次出现的关键字key@Overridepublic boolean remove(Object toRemove) {int index = indexOf(toRemove);if (index == -1) {System.out.println("没有你要删除的值！！！");return false;}for (int i = index; i < count - 1; i++) {array[i] = array[i + 1];}array[count--] = null;return true;}

（9）size()

返回顺序表长度

// 获取顺序表⻓度@Overridepublic int size() {return count;}

（10）clear()

清空顺序表，注意：需要将数组中所有元素都置为null

// 清空顺序表@Overridepublic void clear() {for (int i = 0; i < count; i++) {array[i] = null;}count = 0;}

（11）display()

打印顺序表

    // 打印顺序表@Overridepublic void display() {for (int i = 0; i < count; i++) {System.out.print(array[i] + " ");}System.out.println();}

（12）remove(int pos)

1. remove 的重载方法，该方法可以返回删除位置的元素
2. 需要验证数组中是否是空的，以及pos位置是否合法

    public T remove(int pos) {if (isEmpty()) {throw new EmptyException("空数组异常！！！");}if (checkPos2(pos)) {throw new IllgalPosException("pos 下标非法！！！");}T t = get(pos);remove(t);return t;}

（13）EmptyException

空数组异常

package list;public class EmptyException extends RuntimeException {public EmptyException() {}public EmptyException(String message) {super(message);}
}

二. 洗牌算法

（一）Card

一张扑克牌上的属性有花色 suit 与 数字 rank

package card;/*** Created with IntelliJ IDEA.* Description:* User: 32309* Date: 2025-07-20* Time: 9:55*/
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 + "}";}
}

（二）CardArrayList

1. 所有扑克牌放到该集合中
2. 使用我们刚写好的MyArrayList
3. 分为三部分：买牌 buyCard，洗牌 shuffle，交换 swap
4. 设置号四种花色

（1）buyCard()

54张扑克牌，1~13，每张花色不同，外加小王与大王

    private static final String[] suits = {"♥","♠","♦","♣"};public static MyArrayList<Card> buyCard() {MyArrayList<Card> cards = new MyArrayList<>(54);for (int i = 1; i <= 13; i++) {int rank = i;for (int j = 0; j < 4; j++) {String suit = suits[j];Card card = new Card(suit,rank);cards.add(card);}}Card card1 = new Card("大王🃏",999);cards.add(card1);Card card2= new Card("小王🃏",888);cards.add(card2);return cards;}

（2）shuffle(MyArrayList cardList)

通过设置随机数，从末尾开始来交换，来达到洗牌目的

    public static void shuffle(MyArrayList<Card> cardList) {Random random = new Random();for (int i = cardList.size() - 1; i > 0; i--) {int index = random.nextInt(i);swap(cardList,i,index);}}

（3）swap(MyArrayList cardList,int i,int j)

作为洗牌的辅助方法

    private static void swap(MyArrayList<Card> cardList,int i,int j) {Card card = cardList.get(i);cardList.set(i, cardList.get(j));cardList.set(j,card);}

三. 测试

1. 分别调用买牌 buyCard，洗牌 shuffle，这两二方法来打印牌的信息来测试方法是否正确
2. 三个人轮流揭牌，把所有牌全部揭完

package list;import card.Card;
import card.CardArrayList;public class Test {public static void main(String[] args) {MyArrayList<Card> cards = CardArrayList.buyCard();System.out.print("买牌后：");cards.display();System.out.print("洗牌后：");CardArrayList.shuffle(cards);cards.display();// 三个人轮流抓五张牌MyArrayList<MyArrayList<Card>> hands = new MyArrayList<>();hands.add(new MyArrayList<>());hands.add(new MyArrayList<>());hands.add(new MyArrayList<>());// 抓牌for (int i = 0; i < 18; i++) {for (int j = 0; j < 3; j++) {// 获取第几个人hands.get(j).add(cards.remove(0));}}System.out.print("A 的牌：");hands.get(0).display();System.out.print("B 的牌：");hands.get(1).display();System.out.print("C 的牌：");hands.get(2).display();System.out.print("剩余的牌：");cards.display();}
}