• 【JAVA】顺序表与ArrayList

    顺序表与ArrayList

    顺序表与ArrayList

    坚持一定很酷！

    学习学习！！

    一、线性表

    1. 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
    2. 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构（内存上）上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
    3. 数据结构当中，每次插入数据的时候，一定要有一个前驱信息。
      不能跳着放置元素！！
    4. 增删查改：CURD

    二、顺序表

    • 顺序表是用一段物理地址连续（在内存上连续）的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

    接口的实现

    1. 相关实现：
    1. 判断数组是否已经放满：有效长度==实际数组长度。
      扩容：数组名 = Arrays.copyOf(数组名,扩容后的长度)
      一般情况下，扩容不会失败；但是如果扩容的数据太大，可能就会无法扩容，就会报负数异常：所以可以try…catch 再进行异常处理。
    2. 注意插入元素操作：
      把usedSize-1位置的元素向后挪，一直到想要插入的
      pos位置;（>=pos)的元素都向后挪，再把元素插入到
      pos位置
    3. add(int pos,int data):首先检查元素是否合法，然后
      再判断是否满以及扩容问题，最后进行插入操作
      add(int data):先判断是否满，然后进行扩容，然后再
      进行尾插（usedSize位置插入）
    4. 是否包含contains：for循环usedSize
    5. 基本上都要判断下标合法性
      remove():后一个覆盖前一个，然后最后一个元素置空
      则：for循环只到 (
    6. 删除等操作要进行手动置空（尤其是引用类型），简单类型可以不写
    7. 向右移>>1 :表示除以2
    8. 注意联动改变（子串与原来字符串)
    1. 代码模拟实现相关方法：
    • SeqList.java
    package arraysList;


import java.util.Arrays;

// 顺序表以数组形式进行存储
public class SeqList {
    // 首先创建必要的量：数组、有效数记录、默认数组长度
    public int[] array;
    public int usedSize;
    public static final int DEFAULT_SIZE = 5;

    // 构造方法进行初始化（初始化数组大小，为数组开辟空间）
    public SeqList() {
        array = new int[DEFAULT_SIZE];
    }

    // 不采用以下方法，采用报异常的方式！！
    /*// 检查下标的合法性：不能跳着进行存放
    public boolean isLegal(int pos) {
        if((pos<0)||(pos>usedSize)) {
            return false;
        } else {
            return true;
        }
    }*/

    // 检查下标的合法性：不能跳着进行存放
    // 抛出异常以及自定义异常
    public void isLegal(int pos) {
        if((pos<0)||(pos>usedSize)) {
            throw new PosIndexNotLegalException("下标不合法！");
        }
    }

    // 判断是否满
    public boolean isFull() {
        return (this.usedSize == array.length);
    }

    // 打印顺序表-打印有效位即可
    public void display() {
        /* // 使用for-each进行打印-no-因为会全部打印！！
        for (int x:array) {
            System.out.println(x);
        }*/

        // 尽量使用this！！！
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.array[i] + " ");
        }
        System.out.println();
    }

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        // 判断是否已满
        try {
            if(isFull()) {
                array = Arrays.copyOf(array,-1);
            }
        } catch (NegativeArraySizeException e) {
            e.printStackTrace();
            array = Arrays.copyOf(array,2*array.length); //扩容两倍
        }
        // 在usedSize位置进行元素存储，然后usedSize++
        array[usedSize++] = data;
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        // 检查pos是否合法--try...catch方式
        // 判断是否满以及扩容
        // 将pos以及之后的位置全部向后挪一位:注意应该从后往前挪！！
        try {
            isLegal(pos);
            if(isFull()) { // 满了就扩容，不需要进行异常抛出
                array = Arrays.copyOf(array,2*array.length);
            }
            for (int i = usedSize-1; i >= pos; i++) {
                array[i+1] =array[i];
            }
            array[pos] = data;
            usedSize++; // 更新有效数据个数
        } catch (PosIndexNotLegalException e) {
            e.printStackTrace();
        }
    }

    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        // 进行遍历
        for (int i = 0; i < usedSize; i++) {
            if(array[i] == toFind) {
                return true;
            }
        }
        return false;
    }

    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        // 进行遍历
        for (int i = 0; i < usedSize; i++) {
            if(array[i] == toFind) {
                return i;
            }
        }
        return -1; // 不存在就输出-1
    }

    // 获取 pos 位置的元素
    public int get(int pos) {
        // 首先判断pos是否合法
        // 合法且找到才输出元素
        try {
            isLegal(pos);
            return array[pos];
        } catch (PosIndexNotLegalException e) {
            e.printStackTrace();
        }
        return -1;
    }

    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        // 首先进行合法性判断，然后将pos位置的元素进行替换
        try {
            isLegal(pos);
            array[pos] = value;
        } catch (PosIndexNotLegalException e) {
            e.printStackTrace();
        }
    }

    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        // 遍历的方法不容易进行覆盖操作，则改用找该元素的首下标，找到就存在可以进行覆盖，否则不存在不用删除
        /*//遍历
        for (int i = 0; i < usedSize; i++) {
            if(array[i]==toRemove) {
                // 从该项开始进行覆盖，一直到usedSize-1

            }
        }*/

        // 改用找该元素的首下标，找到就存在可以进行覆盖，否则不存在不用删除
        int index = indexOf(toRemove);
        if(index == -1) {
            System.out.println("sorry 该关键字并不存在！");
            return;
        } else {
            // 从该项开始进行覆盖，一直到usedSize-1: 从前往后+usedSize--
            for (int i = index; i < usedSize-1; i++) {
                array[i] = array[i+1];
            }
        }
        // 有效元素--
        usedSize--;
    }

    // 获取顺序表长度：有效长度
    public int size() {
        return usedSize;
    }

    // 清空顺序表
    public void clear() {
        /*for (int i = 0; i < usedSize; i++) {
            array[i] = Integer.parseInt(null);
        }*/

        // 将有效个数置0就行
        usedSize = 0;
        System.out.println("清空成功！");
    }

}

    • 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
    • PosIndexNotLegalException.java
    package arraysList;

// 自定义下标不合法异常-非受查异常-运行时异常
public class PosIndexNotLegalException extends RuntimeException{
    public PosIndexNotLegalException() {
    }

    public PosIndexNotLegalException(String message) {
        super(message);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 测试代码可以自己写

    三、ArrayList简介

    1. 在集合框架中，ArrayList是一个普通的类，实现了List接口
    2. 说明：
    1. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
    2. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
    3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
    4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
    5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
    1. 小结ArrayList：
      支持随机访问、可克隆、支持序列化、非线程安全（单线程）、动态类型（底层连续、可动态扩容）。

    四、ArrayList使用

    1. ArrayList的构造

    ArrayList

    2. ArrayList的常见操作

    方法

    3. ArrayList的遍历

    1. ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器
    package ArrayListTravel;

// 掌握ArrayList的常用方法
// ArrayList的遍历：三种方式

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class Test {
    public static void main(String[] args) {
        //List list = new List<>();  //错误！List是接口，不能进行实例化！！但是可以对具体子类进行初始化

        List<Integer> list = new ArrayList<>();
        // 增加元素！
        list.add(12);
        list.add(34);
        list.add(2,56);
        list.add(78);
        list.add(4,90);

        // for循环+下标进行遍历:注意获取长度的方法
        System.out.println("使用for循环+下标进行遍历：");
        for (int i = 0; i < list.size(); i++) {
            // 注意获取下标对应元素的方法
            System.out.print(list.get(i)+" ");
        }
        System.out.println();

        // 使用for-each进行遍历：
        System.out.println("使用for-each进行遍历：");
        for (int x:list) {
            System.out.print(x+" ");
        }
        System.out.println();

        // 使用迭代器遍历
        // 使用ListIterator
        System.out.println("使用ListIterator迭代器遍历（调用List方法）：");
        ListIterator<Integer> listIterator = list.listIterator(); // 一定要注意该处的赋值内容是调用List的方法！！
        while(listIterator.hasNext()) {
            System.out.print(listIterator.next()+" ");
        }
        System.out.println();

        // 使用Iterator
        System.out.println("使用Iterator迭代器遍历（调用List方法）：");
        Iterator<Integer> iterator = list.iterator(); // 一定要注意该处的赋值内容是调用List的方法！！
        while(iterator.hasNext()) {
            System.out.print(iterator.next()+" ");
        }
        System.out.println();
    }
}

    • 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
    1. 迭代器遍历数组
    • Iterator<类型如：String> it = list.iterator();
      while(it.hasNext()) { sout(it.next());}
    • ListIterator<类型如：String> it = list.listIterator();
      while(it.hasNext()) { sout(it.next());}

    4. ArrayList的扩容机制

    1. ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。
    2. 根据ArrayList源码总结扩容方式：
    1. 检测是否真正需要扩容，如果是调用grow准备扩容
    2. 预估需要库容的大小
      初步预估按照1.5倍大小扩容
      如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
      真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
    3. 使用copyOf进行扩容
    • grow方法补充：
    // 扩容
private void grow(int minCapacity) {
    // 获取旧空间大小
    int oldCapacity = elementData.length;
    // 预计按照1.5倍方式扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 调用copyOf扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    五、使用实例

    1. 扑克牌

    1. 关键点
    1. 进行洗牌：
      随机数！！注意Random进行实例化的过程。
    2. 抓牌过程要注意双层循环的顺序：
      是先给每个人都发一张牌，而不是给一个人先发完五张牌
      so：
      顺序为：先进行5张牌循环，再进行3个人循环，这样才会
      使得先给三个人每人一张牌，即用牌去循环人
    1. 代码
    • Card.java
    package card;

// 首先准备一副牌的必要变量
public class Card {
    public int value;  // 牌面值
    public char flower; //花色

    // 构造方法进行初始化


    public Card(int value, char flower) {
        this.value = value;
        this.flower = flower;
    }

    // toString 方法进行重写
    @Override
    public String toString() {
        return "{" + value  + flower +
                "}";
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • CardDemo.java
    package card;

// static只有一份，要改变就全部改变！

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

// 具体牌以及洗牌、出牌
public class CardDemo {
    // 先给花色创建一个组-类似常数！！
    public static final char[] SUITS = {'♥','♠','♦','♣'};

    // 准备一副牌
    // 注意每一张牌都是由花色以及牌面值组成的，也就是一个Card类型--所以使用List，以Card类型作为参数！

   // List list = new ArrayList<>();// 注意该处进行修改，写为以下形式

    private static List<Card> preDesk() { // 直接写为一个方法，返回值类型是List（整副牌）
        List<Card> desk = new ArrayList<>(52);  // 容量52:52张牌
        // 进行牌的初始化
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13; j++) {
                Card card = new Card(j,SUITS[i]);
                // 每初始化一张牌就把牌存储添加到desk里面（这副牌）
                desk.add(card);
            }
        }
        return desk;
    }

    // 进行洗牌 的实际操作
    private static void washDeskWork(List<Card> deck,int i, int j) {
        // 随机洗牌
        Card fa = deck.get(j);
        deck.set(j, deck.get(i));
        deck.set(i,fa);
    }

    // 创建随机数 +洗牌
    private static void washDesk(List<Card> deck) {
        Random random = new Random(20220728); //种子数
        for (int j = 1; j < deck.size(); j++) { //通过的是下标去打乱顺序，所以注意下标取值！
            // 注意输入的j只能从1开始！！！
            int i = random.nextInt(j);
            // i代表随机下标  j代表该牌的实际位置下标
            // 每获得一次随机位置就进行一次洗牌
            washDeskWork(deck,i,j);
        }
    }

    // 进行抓牌
    private static List<List<Card>> hand(List<Card> deck) {
        // 假设有3个人，每个人5张牌
        // 3个人构成一个数组，而每个人受力的5张牌又是一个数组，
        // 每张牌的返回类型是Card，每一组牌/每个人的返回类型其实是List
        // 而这三个人和五张牌相当于二维数组--可以用List顺序表表示数组
        List<List<Card>> table = new ArrayList<>();

        table.add(new ArrayList<>());  // 二维数组中的其中一维进行第二维开辟开间
        table.add(new ArrayList<>());
        table.add(new ArrayList<>());

        for (int i = 0; i < 5; i++) { //牌给每人一张
            for (int j = 0; j < 3; j++) { // 人
                /*table.get(j).set(i, deck.remove(i)); //remove的下标是0 永远删除的都是第一个元素！*/

                // 是要将元素添加到table中，而不是设置修改元素，现在一个有效元素都没有！
                table.get(j).add(deck.remove(0)); //注意下标！
            }
        }
        return table;
    }

    public static void main(String[] args) {
        CardDemo cardDemo = new CardDemo();
        // 牌展示
        System.out.println("准备好的完整牌：");
        List<Card> desk = preDesk();
        for (Card x:desk) {
            System.out.print(x.toString() + " ");
        }
        System.out.println();

        System.out.println("洗牌后：");
        washDesk(desk);
        for (Card x:desk) {
            System.out.print(x.toString() + " ");
        }
        System.out.println();

        // 抓牌
        System.out.println("进行抓牌：");
        List<List<Card>> hands = hand(desk);

        // 余牌
        System.out.println("抓牌后的余牌为：");
        for (Card x:desk) {
            System.out.print(x.toString()+" ");
        }
        System.out.println();

        // 每个人的牌
        System.out.println("所抓的每个人的牌进行展示：");
        for (int i = 0; i < 3; i++) {
            System.out.println("第"+(i+1)+"个人的牌展示：");
            /*for (int j = 0; j < 5; j++) {
                System.out.print(hands.get(i).get(j) +" ");
            }
            System.out.println();*/

            System.out.println(hands.get(i)); //注意输出形式！！以一维数组形式进行输出
        }
    }
}

    • 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

    2. 杨辉三角

    杨辉三角

    • 代码：（按照链接来）
    public List<List<Integer>> generate(int numRows) {

        // List>：实际意义是一个二维数组，也就是两个一维数组，元素类型是int类型
        // 每行第一个元素以及最后一个元素都是1，其余元素是上面两个元素之和

        // 一定要注意二维数组要进行两次实例化new操作
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> ret = new ArrayList<>();

        ret.add(1);
        list.add(ret);// 第一行第一列搞定！

        // 从1一行开始是因为之前第一行已经搞定！
        for(int i=1; i<numRows; i++) {
            // 当前行-一维数组
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1); // 当前每行第一列为1 ok！

            /// 上一行
            //List preRow = new ArrayList<>(); // 错误，这样并未给其初始化！

            List<Integer> preRow = list.get(i-1); //注意！！

            // 从1开始是因为首列值已经确定，以及只有从1开始才能取到前一行的首列0列
            // 注意该处循环的次数！！
            //for(int j=1; j

            // 需要使用上一行最后一列，因为计算需要，但是每行总会比上一行多一列，最后一列为1，需要后面单独拎出来add1
            for(int j=1; j<i; j++) {
                curRow.add(preRow.get(j-1)+preRow.get(j));  //取之前行的两列相加之和！
            }

            curRow.add(1); // 每行最后一列为1
            // 此时当前行就是完整一行了！
            list.add(curRow); // 再将当前行传入到二维数组
        }
        return list;


        // 以下是错误代码
       /* for(int i=0; i());
            for(int j=1; j
    }

    • 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

    六、顺序表问题以及思考

    1. 顺序表中间/头部的插入删除，时间复杂度为O(N)
    2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
    3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
    4. 【问题小结】：
    • 顺序表的插入和删除，需要移动元素！
    • 扩容可能会造成空间浪费
    1. 基于以上问题：引出链表–将数据以链式的形式进行存储。
      顺序表是把元素以顺序进行存储的。

    THINK

    1. 顺序表的常用方法
    2. ArrayList的使用以及遍历
    3. List的new！！
    4. List的使用场景：变量是以类型进行传入的
    5. 顺序表的实例！！
    6. 链表：链式存储 顺序表：顺序存储
  • 相关阅读:
    Retrofit 在kotlin中使用及解析
    STC单片机14——利用51单片机测量信号的频率，高低频及转速显示
    Dynamics 365应用程序开发- 8.利用Dynamics 365中的Azure扩展
    C#/.NET/.NET Core优秀项目框架推荐
    solidity实战练习2--ERC20实现
    shiro反序列化漏洞的原理和复现
    Sentinel浅层介绍（上）
    【跨境电商】全渠道客户服务终极指南（一）：概念，重要性与优势
    品牌夜间低价数据如何监测
    它让你1小时精通RabbitMQ消息队列(新增死信处理)
  • 原文地址：https://blog.csdn.net/weixin_54150521/article/details/126027125