• 【顺序表ArrayList】

    文章目录

    顺序表

    含义：物理上连续，逻辑上也连续的线性结构。
    应用于对数组的数据进行增删查改。

    ArrayList说明

    ArrayList是一个普通的类，实现了List接口

    【说明】

    1. ArrayList是以泛型方式实现的，使用时必须要先实例化
    2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
    3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
    4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
    5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者
      CopyOnWriteArrayList
    6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

    ArrayList常见操作

    1. boolean add(E e) 尾插 e
    2. void add(int index, E element) 将 e 插入到 index 位置
    3. boolean addAll(Collection c) 尾插 c 中的元素
    4. E remove(int index) 删除 index 位置元素
    5. boolean remove(Object o) 删除遇到的第一个 o
    6. E get(int index) 获取下标 index 位置元素
    7. E set(int index, E element) 将下标 index 位置元素设置为 element
    8. void clear() 清空
    9. boolean contains(Object o) 判断 o 是否在线性表中
    10. int indexOf(Object o) 返回第一个 o 所在下标
    11. int lastIndexOf(Object o) 返回最后一个 o 的下标
    12. List subList(int fromIndex, int toIndex) 截取部分 list

    顺序表的优缺点

    缺点：
    1.插入数据必须要移动其他数据，最坏情况下，是插入到0位置，时间复杂度为O（N）。
    2.删除数据也需要移动数据，就坏情况下，是删除0位置，时间复杂度为O（N）。

    优点：
    在给定下标查找时，时间复杂度为O（1）。

    所以什么时候适合用顺序表？
    就是给定下表查找时的场景。

    ArrayList的扩容机制

    1. 按照1.5倍扩容
    2. 第一次Add时，会分配大小为10的内存

    1.练习 ：杨辉三角

    在这里插入图片描述

    代码如下

    class Solution {
    public List<List<Integer>> generate(int numRows) {
        //二维数组
        List<List<Integer>> ret= new ArrayList<>();
        //第一行
        ArrayList<Integer> list = new ArrayList<>();
        //第一行的第一个元素
        list.add(1);
        //把第一行的元素放到二维数组里
        ret.add(list);

        //第二行的每个元素由前一行所得
        for (int i = 1; i <numRows ; i++) {
            //实例化当前行
            List<Integer> curRow = new ArrayList<Integer>();
            //当前行第一个元素是1
            curRow.add(1);
            //获取一维数组中上一行的元素。get方法是获取pos位置的元素
            List<Integer> prevRow = ret.get(i - 1);
            //当前行的中间元素
            for (int j = 1; j < i; j++) {
                int val = prevRow.get(j) + prevRow.get(j - 1);
                curRow.add(val);
            }
            //当前行的最后一个数据
            curRow.add(1);
            //把当前行数组放到二维数组里
            ret.add(curRow);
        }
        return ret;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    2.顺序表的实现

    //定义一个接口
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
        //(修改pos位置上的值)
        public void set(int pos, int value);

        //删除第一次出现的关键字key
        public void remove(int toRemove) ;

        // 获取顺序表长度
        public int size() ;
        // 清空顺序表
        public void clear() ;
        // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
        public void display() ;
        public boolean isEmpty();
}
//类实现接口
public class MyArrayList implements IList {
    //定义一个数组
    public int[] elem;
    private int usedSize;
    public static final int DEFAUL_SIZE = 5;
    public MyArrayList() {
        //初始化数组
        this.elem = new int[DEFAUL_SIZE];
    }
    public MyArrayList(int capacity){
        this.elem = new int[capacity];

    }

    //遍历顺序表方法
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }

    //判断数组满了没有
    public boolean isFull(){
        if (usedSize == elem.length){
            return true;
        }
        return false;
    }

    @Override
    public void add(int data) {
        //判断满没满才能放
        cheakCapacity();
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }
    //扩容方法
    //private封装，只为当前类使用
    private  void cheakCapacity(){
        if (isFull()){
            //满了扩容
            elem = Arrays.copyOf(elem,elem.length*2);
        }
    }
    /*
    检查pos的合法性
     */
    private void cheakPosOnGetAndSet(int pos) throws  PosIllegality {
        if (pos < 0 || pos >usedSize){
            System.out.println("pos位置不合法!");
            //抛异常，以便能找到哪一行错误
            throw new PosIllegality("插入元素下标异常：" + pos);
        }

    }
    //指定位置放元素
    @Override
    public void add(int pos, int data) {

        try{
            cheakPosOnGetAndSet(pos);
        }catch(PosIllegality e){
            e.printStackTrace();
            return ;
        }
        cheakCapacity();
        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;

    }

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

    @Override
    public int get(int pos) throws MyArrayEmpty{
        cheakPosOnGetAndSet(pos);
       if (isEmpty()){
           throw new  MyArrayEmpty("获取顺序表下标位置时"+
                   "顺序表为空！");
       }
       return elem[pos];
    }

    @Override
    public void set(int pos, int value) {
        //先检查pos的合法性，
        cheakPosOnGetAndSet(pos);
        //修改pos上的值
        elem[pos] = value ;
    }

    @Override
    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--;
    }

    @Override
    public int size() {
        return this.usedSize;
    }

    @Override
    public void clear() {
        this.usedSize = 0;
        //如果是引用数据类型,可以用for循环一个一个置为null
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }
}
public class MyArrayEmpty extends RuntimeException {
    public MyArrayEmpty(String msg){
        super(msg);
    }
}

public class PosIllegality extends RuntimeException {
    //构造方法
    public  PosIllegality(String msg){
        super(msg);
    }
}

public class Test{
    public static void main1(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(1);//下标0
        myArrayList.add(2);//下标1
        myArrayList.add(199);//下标2
        myArrayList.display();
        //删除元素2
        myArrayList.remove(2);
        myArrayList.display();
    
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204

    3.简单的洗牌算法

    package card;

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

/**
52张牌 1-k
  J   Q   K
 11  12  13
 */
public class CardDemo {
    //定义花色
    private  final String[] suits = {"♥","♠","♦","♣"};
    //买的牌
    public  List<Card> buyCard(){
        //产生52张牌
        List<Card> 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;
    }

    //洗牌
    public void shuffle(List<Card> cardList){
        //生成随机数
        Random random = new Random();
        for (int i =cardList.size()-1; i >0; i--) {
            int index = random.nextInt(i);
            //交换
            swap(cardList,i,index);
        }
    }
    private void swap(List<Card> cardList,int a,int b) {
        //把a和b交换
        Card tmp = cardList.get(a);
        cardList.set(a, cardList.get(b));
        cardList.set(b, tmp);
    }
    public void  getCard(List<Card> cardList){
       List<Card> hand1 = new ArrayList<>();
       List<Card> hand2 = new ArrayList<>();
       List<Card> hand3 = new ArrayList<>();

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

       //每个人轮流抓5张牌
       for (int i = 0; i <5 ; i++) {

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

    }
}


package card;
import java.sql.SQLOutput;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        CardDemo cardDemo = new CardDemo();
        List<Card> cardList = cardDemo.buyCard();
        System.out.println("买的牌如下：");
        System.out.println(cardList);

        System.out.println("洗牌：");
        cardDemo.shuffle(cardList);
        System.out.println(cardList);

        System.out.println("揭牌：");
        cardDemo.getCard(cardList);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
  • 相关阅读:
    视频直播美颜SDK算法代码解析
    C语言指针
    数据库服务器CPU不能全部利用原因分析
    震裕科技-300953 三季报分析（20231108）
    Hive参数与性能调优-V2.0
    【问题处理小知识】jupyter notebook报错：500 internal server error的几种解决办法整理
    dc9靶机攻略
    AWS EKS 创建k8s生产环境实例
    分布式id生成方案有哪些
    火山引擎ByteHouse：4000字总结，Serverless在OLAP领域应用的五点思考
  • 原文地址：https://blog.csdn.net/2301_76496134/article/details/134451898