数据结构：ArrayList列表

目录

线性表

列表：一个动态扩容的数组

第一部分：定义elem数组，大小和内存

第二部分：遍历并添加元素

第三部分：找元素和更新元素

第四部分：删除元素+有的没的

ArrayList 深度剖析

ArrayList的应用

1.杨辉三角

（1）先处理第一行

（2）从第二行开始算，把数据一行一行塞到ret中，i代表行，j代表列

（3）观察杨辉三角的特点

（4）最后再把结果返回就行

（5）整个的代码

2.简单的洗牌算法

1.要买一副拍，也就是要生成一副扑克牌

2.洗牌

3.揭牌，每人轮流抓5张牌

---

线性表

线性表是n个具有相同特性的数据有限序列，包括顺序表，链表，栈，队列

ArrayList：一个动态扩容的数组

ArrayList底层是一个数组，可以进行随机访问O(1)，当使用随机访问进行读写的时候，速度是比较快的。

随机访问不是查找，随机访问是按照下标访问；而查找使用的是indexOf这样的方法按照元素的值进行查找，这个过程要遍历ArrayList，开销是O(N)

问题：这里面有多少个有效数据？怎么用程序去算？

按照数组的思想，就是一个for循环然后遍历到0停止。但是万一这里面就有一个0，那不是直接就漏掉了。所以单纯用一个数组去做肯定不行。所以我们要结合一个方法来做。

现在我们要来自己写一个顺序表底层逻辑和方法

第一部分：定义elem数组，大小和内存

设置一个usedSize，每次往数组加进去一个元素，usedSize就++

public class MyArrayList implements IList{
    public int[] elem;
    public int usedSize;//0
    //顺序表默认大小
     public static final int DEFAULT_SIZE = 10;
    //给数组分配内存
    public MyArrayList(){
        this.elem = new int[DEFAULT_SIZE];
    }
    //更灵活的构造方法
    public MyArrayList(int capacity){
        this.elem = new int[capacity];
    }

第一步的初始化完成了，接下来要思考顺序表中一存储的数据要怎么操作？没有数据的话要怎么加入数据？

我们设置一个接口IList，把可能用到的方法都放到接口中

//IList
public interface IList {
    // 新增元素,默认在数组最后新增
    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();
 
    boolean isFull();
}

接着在MyArrayList里面重写接口方法

---

第二部分：遍历并添加元素

    @Override
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

现在我们要添加元素，首先我们要判断顺序表里面元素是不是满的，所以我们添加多一个方法isFull()

    @Override
    public boolean isFull() {
//        if(usedSize == elem.length){
//            return true;
//        }
//        return false;
        return usedSize == elem.length;
    }

    @Override
    public void add(int data) {
        if(isFull()){
            //扩容
            elem = Arrays.copyOf(elem, elem.length*2);
        }
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }

copyOf就是把elem列表拷贝一份再进行长度的扩容 

 代码优化：

我们可以把检查容量的过程封装到一个方法里面，我们再上面的add方法使用就只需要调用这个封装方法就行

    private void checkCapacity(){
        if(isFull()){
            //扩容
            elem = Arrays.copyOf(elem, elem.length*2);
        }
    }

但为什么是private呢？ 因为这个检查容量的方法是我们在做功能的时候使用的，只服务与当前类，而不是提供给用户用的

---

现在顺序表能添加元素了，但是它还不知道要把这个元素加到哪里，我们搞了另一个add方法，传入两个参数pos和data

小问题：这里的pos可以放到5的位置上吗？

答案是不能。因为数据结构当中，每次存储数据的时候一定记住，必须要有一个前驱信息，如果4位置没有放置任何东西，5位置是肯定不能存东西的

所以要存放的pos∈[0, usedSize]

那我们可以封装一个方法来检查pos值得合法性

    private void checkPosOnAdd(int pos) throws PosIlleagaly{
        if(pos < 0|| pos > usedSize){
            System.out.println("不合法");
            //return;void要return点东西，我们可以抛一个异常
            throw new PosIlleagaly("插入元素下标异常"+pos);
        }
    }
//PosIlleagaly.java
package myList;
 
public class PosIlleagaly extends RuntimeException{
    public PosIlleagaly(String msg){
        super(msg);
    }
}

add方法里面也要加入异常语句

    @Override
    public void add(int pos, int data) {
        try{
            checkPosOnAdd(pos);
        }catch (PosIlleagaly e){
            e.printStackTrace();
        }
        checkCapacity();
 
    }

测试一下

处理完异常，我们看看怎么个插入法

定义一个i，从顺序表最末端元素的位置开始，把最后一个元素往后移elem[i+1] = elem[i]，然后让i往前面去遍历（i--），直到i找到pos也就是i

        for (int i = usedSize-1; i >= pos ; i--) {
            elem[i+1] = elem[i];
        }
        elem[pos] = data;
        usedSize++;
    }

测试效果： 

---

第三部分：找元素和更新元素

    @Override
    public boolean contains(int toFind) {
        if(isEmpty()){
            return false;
        }
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }

如果toFind是一个字符串，那就得用equals，然后重写方法

查找元素下标

    @Override
    public int indexOf(int toFind) {
        if(isEmpty()){
            return -1;
        }
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }

获取指定下标的元素

还是得判断pos有没有越界，这里0<=pos<=usedSize-1

    private void checkPosOnGetAndSet(int pos) throws PosIlleagaly{
        if(pos < 0|| pos >= usedSize){
            System.out.println("不合法");
            throw new PosIlleagaly("获取指定下标的元异常"+pos);
        }
    }
 
    @Override
    public int get(int pos) throws MyArrayListEmpty{
        checkPosOnGetAndSet(pos);
 
        if(isEmpty()){
            throw new MyArrayListEmpty("获取下标元素时"+"顺序表为空");
        }
        return elem[pos];
    }

//MyArrayListEmpty.java
public class MyArrayListEmpty extends RuntimeException {
    public  MyArrayListEmpty(String msg){
        super(msg);
    }
}

给pos位置的元素进行更新

    @Override
    public void set(int pos, int value) {
        checkPosOnGetAndSet(pos);
        elem[pos] = value;
    }

---

第四部分：删除元素+有的没的

删除元素

1.找到要修改的数字  2.挪动数据（添加元素的逆过程），挪到最后一个   3.修改size，删掉最后一个格子，也就直接把刚挪到最后一个位置的元素删除

    public void remove(int toRemove) {
        int index = indexOf(toRemove);
        if(index == -1){
            System.out.println("没有这个数字");
            return;
        }
        for (int i = index; i < usedSize-1; i++) {
            elem[i] = elem[i+1];
        }
        usedSize--;
    }

为什么要usedSize-1呢？

 假设i在4的位置，往后挪一位到5的位置，刚好就是usedSize-1 = 6-1

---

到clear就更简单了，直接把usedSize置为0就行了

@Override
public void clear() {
    this.usedSize = 0;
}

如果elem是Person类型，因为是引用数据类型，当我们把usedSize置为0的时候，引用的地址还不能被回收，这会造成内存泄漏

那JVM为什么不会自动回收对象呢？因为对象在被回收的时候有一个前提：对象没有被引用，而这里的0和1下标确确实实在引用那两个对象

那我们就要改一下代码（针对引用类型）

暴力方法：elem = null

温柔方法：

for (int i = 0; i < usedSize; i++) {
    this.elem[i] = null;
}

---

ArrayList 深度剖析

自己手搓了一个自己的顺序表代码后，我们不妨看看官方是怎么实现ArrayList的

整个ArrayList结构

看看代码（部分）：

默认容量

数组和大小

  

空数组 

 

 当等于0的时候就分配给它一个空的数组（EMPTY_ELEMNTDATA)

这个数组用来表示内存分配的 

 

当我们看到new那一行代码的时候，认为其实没有分配内存

那这些add怎么存储到ArrayList当中的呢？

从上面的分析可以得出结论1：第一次add的时候会分配10的内存 

10个放满之后才会调用这个grow 

oldCapacity>>1 相当于除以2，换句话说这里的扩容标准1+0.5=1.5倍

---

再来看另一个构造方法

？代表通配符，是E的子类或者E本身

举一反三：我们也可以用LinkedList，因为链表同样实现了collection接口

 

        LinkedList list1 = new LinkedList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
 
        ArrayList list12 = new ArrayList<>(list1);

 同理，只要实现了collection接口的，都可以传递

---

注意这里的第二个remove参数一定得是个对象，而不能光填数字

 

 细说一下subList

初始化一个列表

        ArrayList list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        System.out.println(list);

        List list1 = list.subList(1,3);
        System.out.println(list1);

分割下标1到2的元素（下标3取不到）

现在我要把list1的元素2改为99，用set方法后再打印

list1.set(0, 99);
System.out.println(list1);
System.out.println(list);

我们诧异地发现list的值也被改了？？！

理论来说截取出来后进行修改不会动到原来的列表啊

其实这里的截取不是产生一个新对象，list1只是截取了list从1位置开始的地址，换句话说，list1 0位置的地址和list 1位置的地址一样，改了一个地方的值另一个也会被改变

---

两种打印列表元素的方式：for each和迭代器方式

//for-each
        for(Integer x: list){
            System.out.print(x+"");
        }
        System.out.println();
//迭代器
        Iterator it= list.iterator();
        //看看有没有下一个
        while(it.hasNext()){
            System.out.println(it.next()+" ");
        }

---

ArrayList的应用

1.杨辉三角

118. 杨辉三角 - 力扣（LeetCode）

题目一开始使用嵌套调用说明这段代码是实现了List这个接口的

我们拿ArrayList来测试一下这个嵌套调用

        List> list3 = new ArrayList<>();
        list3.add(new ArrayList<>());
        list3.add(new ArrayList<>());

list3每次添加的元素都是列表

而杨辉三角的每一行都可以当作一个list，这就相当于一个二维数组了

（1）先处理第一行

        List> ret = new ArrayList<>();
        //每一行都是一个list
        List list = new ArrayList<>();
        list.add(1);
        //把第一行列表放到ret中
        ret.add(list);

（2）从第二行开始算，把数据一行一行塞到ret中，i代表行，j代表列

        //从第2行开始计算每个list中的数据
        for(int i = 1; i< numRows;i++){
            List curRow = new ArrayList<>();
            //每行第一个元素
            curRow.add(1);
 
            for(int j = 1; j< ; j++){
                
            }
        }

（3）观察杨辉三角的特点

           //上一行
            List perRow = ret.get(i-1);
            for(int j = 1; j < i; j++){
                int val = perRow.get(j) + perRow.get(j-1);
                curRow.add(val);
            }
            //每行最后一个元素
            curRow.add(1);
            //算好一行就放一行到ret中
            ret.add(curRow);

（4）最后再把结果返回就行

（5）整个的代码

class Solution {
    public List> generate(int numRows) {
        List> ret = new ArrayList<>();
        //每一行都是一个list
        List list = new ArrayList<>();
        list.add(1);
        //把第一行列表放到ret中
        ret.add(list);
        //从第2行开始计算每个list中的数据
        for(int i = 1; i< numRows;i++){
            List curRow = new ArrayList<>();
            //每行第一个元素
            curRow.add(1);
 
            //获取上一行
            List perRow = ret.get(i-1);
            for(int j = 1; j < i; j++){
                //处理当前行中间的数据
                int val = perRow.get(j) + perRow.get(j-1);
                curRow.add(val);
            }
            //每行最后一个元素
            curRow.add(1);
            //算好一行就放一行到ret中
            ret.add(curRow);
        }
        return ret;
 
    }
}

2.简单的洗牌算法

1.要买一副拍，也就是要生成一副扑克牌

//Card类定义属性：花色和数字
public class Card {
    public 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;
    }
 
    @Override
    public String toString() {
        return suit+":" + rank+" ";
    }
}
//cardDemo定义花色和牌列表的三个操作
import java.util.ArrayList;
import java.util.List;
 
public class CardDemo {
    /**
     * 52张牌从1到K，把大小鬼扔了
     * J  Q  K
     * 10 11 12
     */
    private final String[] suits = {"♥", "♣", "♠", "♦"};
    public List buyCard(){
        List cardList = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 13; j++) {
                Card card = new Card(suits[i], j);
                cardList.add(card);
            }
        }
        return cardList;
    }
}
//Test测试
import java.util.ArrayList;
import java.util.List;
 
public class CardDemo {
    /**
     * 52张牌从1到K，把大小鬼扔了
     * J  Q  K
     * 10 11 12
     */
    private static String[] suits = {"♥", "♣", "♠", "♦"};
    public List buyCard(){
        List cardList = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 13; j++) {
                Card card = new Card(suits[i], j);
                cardList.add(card);
            }
        }
        return cardList;
    }
}

 

2.洗牌

设置i从后往前遍历（从前往后可能要包含到自己，不方便洗牌），再生成随机坐标index，然后拿这两个交换就行了

    public void shuffle(List cardList) {
        Random random = new Random();
        for (int i = cardList.size()-1; i > 0; i--) {
            int index = random.nextInt(i);
            //index  i 交换
            swap(cardList,i,index);
        }
    }
    private void swap(List cardList,int a,int b) {
        Card tmp = cardList.get(a);
        cardList.set(a,cardList.get(b));
        cardList.set(b,tmp);
        /**
         * tmp = a
         * a = b
         * b = tmp
         */
    }

3.揭牌，每人轮流抓5张牌

每个人抓的牌组合在一起相当于一个列表

        //把牌放到每个人手中
        List hand1 = new ArrayList<>();
        List hand2 = new ArrayList<>();
        List hand3 = new ArrayList<>();

因为三个人的牌是没有关系的，所以三个人每个人相当于又一个列表的元素，也就是说三个人每人就是一行，每一行都有他们独立的牌，这就形成了一个二维数组

        List> hands = new ArrayList<>();
        hands.add(hand1);
        hands.add(hand2);
        hands.add(hand3);

3个人每人轮流抓5张牌，每次揭牌1张

        //i代表次数
        for (int i = 0; i < 5; i++) {
            //j代表人
            for (int j = 0; j < 3; j++) {
                Card card = cardList.remove(0);
                hands.get(j).add(card);
            }
        }
 
        System.out.println("第1个揭牌如下：");
        System.out.println(hand1);
        System.out.println("第2个揭牌如下：");
        System.out.println(hand2);
        System.out.println("第3个揭牌如下：");
        System.out.println(hand3);
 
        System.out.println("剩下的牌：");
        System.out.println(cardList);

测试效果