目录:
一.线性表
二.顺序表
一.线性表 :
三.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));}}
}
来看一下输出: