List 接口相关知识 - ArrayList数据结构 - Java - 细节狂魔(估摸着有几万字)

x33g5p2x  于2021-12-09 转载在 Java  
字(5.8k)|赞(0)|评价(0)|浏览(217)

泛型的引入

实现一个通用的顺序表(直接实践)

准备工作,相信大家都看得懂。

class MyArrayList{
    private int[] elem;// 建立数组
    private int usedSize;// 有效元素个数

    public  MyArrayList(){// 构造方法
        this.elem = new int[10];// 默认数组初始容量为 10
    }
    public void add(int val){// 添加元素
        this.elem[usedSize] = val;
    }
    public int get(int pos){// 得到指定位置的元素
        return  this.elem[pos];
    }
}
public class Test {
}

但是这个代码并不通用,只能存储一种数据类型(int)。

开始掰扯

总结

包装类(Wrapper Class)

基本数据类型和包装类直接的对应关系

基本数据类型包装类
byteByte
shortShort
intInteger
longLong
floatFloat
doubleDouble
charCharacter
booleanBoolean

包装类存在的意义

实战(讲一个字符串类型转换成整形数据)

包装类的“装箱(boxing) / 装包” 和 “拆箱(unbosxing) / 拆包”

ArrayList 与 顺序表

边实践边讲解

实战前的铺垫

在使用任何一个 idea编译器写好的类的时候,一定要先去看一下这个类的构造方法

ArrayList的三种打印方式

拓展(迭代器打印)

ArrayList基础功能演示

add 和 addAll ,添加元素功能

public class TestDemo {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");// 添加List元素
        System.out.println(list);
        System.out.println("===============");
        list.add(1,"g");// 在List指定位置中添加元素
        System.out.println(list);
        System.out.println("========");
        List<String> list1 = new ArrayList<>();
        list1.add("x");
        list1.add("y");
        list.addAll(list1);// 将一个list1 整体添加 list中
        System.out.println(list);
    }
}

附图

remove - 删除 指定下标的元素,返回值为删除元素

附图(remove 内部实现)

remove - 输出从左往右 第一个指定数据 - 返回值为布尔类型

remove 函数 内部实现 附图

get - 换取指定下标位置的元素

附图 (get方法内部)

set - 将指定下标元素设置为指定数据(可以理解为更新指定下标元素) - 返回值为旧元素

set 内部附图

clear - 清空顺序表中的元素 - 无返回值

clear 内部实现 附图

contains 判断 指定数据 是否在线性表中 - 返回值为布尔类型

contains 内部实现 附图

indexOf - 返回指定数据在线性表中第一次出现的位置,所对应的下标

indexOf 内部实现附图

lastIndexOf - 返回 在线性表中,最后一个 与指定元素相等 的 元素下标

lastIndexOf 内部实现附图

subList - 截取部分 线性表数据 - 返回值 为 List < E > 类型

subList 内部实现 附图

ArrayList的扩容机制

来看一下,下面的代码是否存在缺陷

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        list.add(i);
    }
}

首先我们认为这个代码是没有缺陷的,但是因为ArrayList 底层的数组是有一定大小的,那么存放数组的过程中,一定会涉及到扩容,
前面我们讲到ArrayList 有三种方法,现在使用的是不带参数的,也就是说ArrayList 底层的数组初始容量为零。 那么第一个问题就出现了: 既然数组的容量是为零,那么它怎么还可以存入数据?
第二个问题: 假设数组初始化容量为10,超过了10,就需要扩容。而且扩容操作时在代码底层执行,是看不见的,也就是说ArrayList在存储数据,隐式的进行扩容操作,那么它的扩容机制是怎样的?

下面来跟着我一起 手撕它

模拟实现 ArrayList, 这次的模拟会比上次发的博客顺序表 和 链表 - 顺序表部分更细腻一些。

新建一个 MyArrayList 类,里面我们只需写上最重要的两个属性

然后就是构造方法:带参 和 不带参的 两个构造方法

先来看不带参的

带参的构造方法

&ensp;

接下来怎么写,按照这个表写,实现它的基础功能。(看不懂的,可以翻上去看,前面有实现)

// E 是数据类型

方法解释
boolean add(E e)尾插 e
void add(int index,E element)将e 插入到index位置
boolean addAll(Collection<? extends E> c)尾插 c 中的元素(将一个顺序表所有元素,尾插到另一个顺序表中)
E remove(int index)删除 index 位置元素
boolean remove(Object o)删除遇到的第一个 o
E get(int index)获取下标index位置元素
E set(int index,Eelement)将下标为index的元素,置换为 element
void clear()清空
boolean contains(Object o)判断 o 是否在线性表中
int indexOf(Object o)从左往右 返回第一个 o 的下标
int lastIndexOf(Object o)返回最后一个o的下标 (从右往左 返回第一个 o 的下标)
List subList(int fromIndex,int tolndex)"截取"部分list

add 功能

&ensp;

add index 的功能就简单了,因为 支撑它的方法 ,现在几乎都写好了

add 两种用法的效果图

remove 功能 - 删除删除遇到的第一个 指定元素

remove 功能 - 删除 index 位置元素

get - 获取指定下标位置元素

set - 将指定的下标的元素,置换为 指定的数据

clear - 清空

contains - 判断 指定元素 是否在线性表中

indexOf 和 lastIndexOf ,直接搬原码(注意indexOf 是前面写了的(只要把private改成public就行),直接搬lastIndexOf)

效果图

总结:

ArrayList 实践案例 - 扑克牌

扑克牌的特点

根据扑克牌的特点,抽象出一个类。

造一张牌

造一副牌

洗牌 -(试问这样的牌,炸金花,谁敢去?谁去谁死。)

发牌 / 揭牌 和 发牌

文章最后,附上扑克牌程序(get 和 set 没用到,可以不用写,我只是习惯性三连)

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Card{
    private int point;
    private String flowerColor;

    public Card(int point, String flowerColor) {
        this.point = point;
        this.flowerColor = flowerColor;
    }

    public int getPoint() {
        return point;
    }

    public void setPoint(int point) {
        this.point = point;
    }

    public String getFlowerColor() {
        return flowerColor;
    }

    public void setFlowerColor(String flowerColor) {
        this.flowerColor = flowerColor;
    }

    @Override
    public String toString() {
        return "{ " +flowerColor +" "+point+" }";
    }
}

public class PlayingCard {
    // 定义 扑克牌的花色
    private static final String[] flowerColors = {"♥","♠","♦","♣"};

    // 创建一副扑克
    public  static List<Card> newCard() {
        ArrayList<Card> cards = new ArrayList<>();
        for (int i = 0; i < 4; i++) {// 4种花色
            for (int j = 1; j <= 13; j++) {// 尖 到 k 一共13个点数
                cards.add(new Card(j,flowerColors[i]));
            }
        }
        return cards;
    }

    // 洗牌
    public static void shuffle(List<Card> list){
        // 牌数是52,数组下标就是51
        // 从最后一张牌开始,随机与 本身 或者 本身前面的任意一张牌 交换位置。
        // 这样的做交换性 比 从开头洗 的 打乱顺序的 效率 高。
        for (int i = list.size()-1; i >0 ; i--) {
            // Random 是一个生成随机数的类
            Random random = new Random();

            // 通过 Random的引用 random 去调用 nextInt() 方法。
            // random.nextInt() 方法,根据括号中的值,随机生成 0 ~ 括号中的值
            int rand = random.nextInt(i);

            // 将 第 i 张牌 , 与 自身 或者 自身前面的任意一张牌的下标 丢给 swap方法
            // 让它去交换位置
            swap(list,i,rand);
        }
    }
    // 交互式洗牌模式
    private static void swap(List<Card> list,int i,int j){
        // 我们现在是面向对象,ArrayList虽然底层是一个数组,但是需要使用方法,才能操作数组的元素
        // 并不能像数组一样,直接操作

        // Card tmp = list[i];
        Card tmp = list.get(i);// 获取 顺序表中,对应下标的元素

        // list[i] = list[j];
        list.set(i,list.get(j));// 将 j下标的元素,赋给 i 下标的元素,

        // list[j] = tmp;
        list.set(j,tmp);
    }

    public static void main(String[] args) {
        System.out.println("======一副买来拆的牌==========");
        List<Card> list = newCard();
        System.out.println(list);
        System.out.println("======== 洗牌 =========");
        shuffle(list);
        System.out.println(list);
        System.out.println("======== 发牌,3个人轮着发,每个人5张牌=========");

        ArrayList<ArrayList<Card>> player = new ArrayList<>();
        // 这行代码 就是 一个二维数组,
        // 首先我们有一个player, player 的每个元素 都是 ArrayList<Card> 类型。
        // 也就是说每个元素就是一个顺序表,也可以说是一个一维数组。
        // 你也可以这么理解 第一个 ArrayList 是用来记录有 玩家的方位/顺序表的地址/数组的地址
        // 第二个ArrayList 就是 每个玩家手上牌的情况/数组的元素情况/顺序表的底层数组元素情况。
        // 你可以 把 player 看作牌桌,等待三位玩家的入场。

        // 打牌三人组
        ArrayList<Card> playerOne = new ArrayList<>();
        ArrayList<Card> playerTwo = new ArrayList<>();
        ArrayList<Card> playerThree = new ArrayList<>();
        // 将三位玩家的信息,加载到 player 当中
        player.add(playerOne);
        player.add(playerTwo);
        player.add(playerThree);
        for (int i = 0; i < 5; i++) {// 发 5 轮牌
            for (int j = 0; j < 3; j++) {// 每个人 轮着发,最终每个人5张牌
                Card card = list.remove(0);
                player.get(j).add(card);
            }
        }

        // 打印每个人的手牌
        System.out.println("playerOne的手牌:"+ playerOne);
        System.out.println("playerTwo的手牌:"+playerTwo);
        System.out.println("playerThree的手牌:"+playerThree);
        System.out.println("list 剩余的牌:"+list);
    }

// public static void main1(String[] args) {
// Card card = new Card(3,"♠");
// System.out.println(card);
// }
}

相关文章

微信公众号

最新文章

更多

目录