ArrayList与顺序表

目录：

 一.线性表 

二.顺序表

 一.线性表 ： 

三.ArrayList的简介 ：

 2. ArrayList是以泛型方式实现的，使用时必须要先实例化 ，ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问，

 上图我们可以看出ArrayList，继承了很多类，并且扩展了很多接口使用，自身也有很多方法。

  四.ArrayList自我实现和使用（这里我们没有用泛型类实现）：

我们可以仿照源码自己去实现，这里我们实现几个常见的方法，（注意ArrayList不止这些方法），自己的ArrayList

下面先来说明一下，自己模仿的每一个类的分配如图：

1.这里是IList接口里的方法：

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 位置的元素设为 valuepublic void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove);// 获取顺序表长度public int size();// 清空顺序表public void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display();
}

2.这里是继承了My_ArrayList的类，具体方法构架界面：这里注意：要在某位置插入，这个位置的，前驱一定不能为空

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位置不合法");}}@Overridepublic void add(int data) {if (isFull()) {//扩容grow();}this.array[this.usedSize++] = data;}@Overridepublic 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();}}@Overridepublic boolean contains(int toFind) {for (int i = 0; i < usedSize; i++) {//这里如果是自己，定义的引用类型，那么要用equal比较if (array[i] == toFind) {return true;}}return false;}@Overridepublic 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("顺序表为空");}}@Overridepublic int get(int pos) {try {//顺序表本来就为空时this.checkOfList();checkPosOf2(pos);return array[pos];}catch (IllegalPos e) {e.printStackTrace();}catch (EmptyException e) {e.printStackTrace();}return -1;}//更新@Overridepublic void set(int pos, int value) {try {//顺序表本来就为空时this.checkOfList();checkPosOf2(pos);array[pos] = value;}catch (IllegalPos e) {e.printStackTrace();}catch (EmptyException e) {e.printStackTrace();}}@Overridepublic 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();}}@Overridepublic int size() {return this.usedSize;}@Overridepublic void clear() {//如果是引用类型，要把，引用置为空/*for (int i = 0; i < this.usedSize; i++) {this.array[i] = null;}this.usedSize = 0;*///基本类型直接这样写this.usedSize = 0;}@Overridepublic void display() {for (int i = 0; i < usedSize; i++) {System.out.print(array[i] +" ");}}}

3.这里是两个自定义异常EmptyException（检查顺序表是否为空）和IllegalPos（检查下标是否合法）：

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循环+下标遍历：

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遍历：

 

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.使用迭代器遍历：

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.学了ArrayLisy之后，来看一下其应用，这里的洗牌算法，会用集合来定义二维数组，来把牌分别放到不同玩家手中，接下来有我娓娓到来：

 2.老规矩，来看一下，定义的，类的结构：

3.具体实现：

Card类，定义基本的对象和构造方法：

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;}@Overridepublic String toString() {/*return "Card{" +"rank=" + rank +", suit='" + suit + '\'' +'}';*/return "{" + suit + rank + "}";}
}

cardDemo类定义，买牌，洗牌，揭牌方法具体如下： 

（1）买52张牌：这里注意要，声明Card对象，来通过构造方法来，初始化，每一张牌，每一张牌又有四种花色。

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测试类：

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

来看一下输出：