顺序表 ArrayList

一、集合框架
二、线性表
三、顺序表
- 3.1 常用方法的实现
四、ArrayList简介
五、ArrayList使用
六、使用示例

一、集合框架

Java 集合框架 Java Collection Framework ，又被称为容器 container ，是定义在 java.util 包下的一组接口 interfaces和其实现类 classes 。
其主要表现为将多个元素 element 置于一个单元中，用于对这些元素进行快速、便捷的存储 store 、检索 retrieve 、管理 manipulate ，即平时我们俗称的增删查改 CRUD 。
例如，一副扑克牌(一组牌的集合)、一个邮箱(一组邮件的集合)、一个通讯录(一组姓名和电话的映射关系)等等。
类和接口总览

二、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

三、顺序表

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

3.1 常用方法的实现

public class MyArraylist {
    public int[] elem;
    public int usedSize;//0
    //默认容量
    private static final int DEFAULT_SIZE = 10;

    public MyArraylist() {
        this.elem = new int[DEFAULT_SIZE];
    }

    /**
     * 打印顺序表:
     * 根据usedSize判断即可
     */
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }

    /**
     * 判断当前的顺序表是不是满的！
     *
     * @return true:满   false代表空
     */
    public boolean isFull() {
        if (size() >= this.elem.length) {
            return true;
        }
        return false;
    }
    
    /**
     * 在 pos 位置新增元素
     * 如果pos下标不合法，那么就会抛出一个 PosWrongfulException
     *
     * @throws PosWrongfulException
     */
    public void add(int pos, int data) throws PosWrongfulException {
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }
        if (pos < 0 || pos > this.usedSize) {
            throw new PosWrongfulException("Pos位置不合法!");
        }
        // 走到这里，pos一定是合法的，开始挪动数据
        for (int i = size() - 1; i >= pos; i--) {
            this.elem[i + 1] = this.elem[i];
        }
        // 插入数据
        this.elem[pos] = data;
        // usedSize++;
        this.usedSize++;
    }

    // 判定是否包含某个元素
    public boolean contains(int toFind){
        for (int i = 0; i < size(); i++) {
            if(this.elem[i] == toFind){
                return true;
            }
        }
        return false;
    }

    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < size(); i++) {
            if(this.elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }

    // 获取 pos 位置的元素
    public int get(int pos) throws PosWrongfulException{
        if(isEmpty()){
            throw new EmptyException("当前顺序表为空!");
        }
        if(pos < 0 || pos >= this.usedSize){
            throw new PosWrongfulException("get获取元素的时候，pos位置不合法!");
        }
        return this.elem[pos];
    }

    private boolean isEmpty() {
        return size() == 0;
    }

    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, int value) {
        if(isEmpty()){
            throw new EmptyException("当前顺序表为空!");
        }
        if(pos < 0 || pos >= size()){
            throw new PosWrongfulException("set修改元素的时候，pos位置不合法!");
        }
        this.elem[pos] = value;
    }

    /**
     * 删除第一次出现的关键字key
     *
     * @param key
     */
    public void remove(int key) {
        if(isEmpty()){
            throw new EmptyException("当前顺序表为空!");
        }
        int index = indexOf(key);
        // 可能找不到！！！！！
        if(index == -1){
            System.out.println("没有这个数字!");
            return;
        }
        for (int i = index+1; i < size(); i++) {
            this.elem[i-1] = this.elem[i];
        }
        this.usedSize--;
    }

    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }

    // 清空顺序表
    public void clear() {
        usedSize = 0;
    }
}

public class EmptyException extends RuntimeException{
    public EmptyException() {
    }

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

public class PosWrongfulException extends RuntimeException{
    public PosWrongfulException(){

    }

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

public class TestMyArraylist {
    public static void main(String[] args) {

        MyArraylist myArraylist = new MyArraylist();
        myArraylist.add(1);
        myArraylist.add(2);
        myArraylist.add(3);
        myArraylist.display();
        try {
            myArraylist.add(1,10);
        }catch (PosWrongfulException e){
            e.printStackTrace();
        }
        myArraylist.display();
        System.out.println("================================");
        System.out.println(myArraylist.contains(2));
        System.out.println(myArraylist.contains(20));
        System.out.println(myArraylist.indexOf(2));
        System.out.println(myArraylist.indexOf(20));
        try{
            System.out.println(myArraylist.get(1));
        }catch (PosWrongfulException e){
            e.printStackTrace();
        }catch (EmptyException e){
            e.printStackTrace();
        }
        System.out.println("===================================");
        myArraylist.set(0,9);
        myArraylist.display();
        System.out.println("===================================");
        myArraylist.remove(3);
        myArraylist.display();
        System.out.println("===================================");
        myArraylist.clear();
        myArraylist.display();
    }
}

四、ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：

【说明】

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

五、ArrayList使用

5.1 ArrayList的构造

方法	解释
ArrayList()	无参构造
ArrayList(Collection<? extends E> c)	利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)	指定顺序表初始容量

第一种：第一个add()之后，分配大小为10的内存；
第二种：只能传实现了Collection接口的类，且类型形参必须为元素类型或其子类；
第三种：可以设置内存。

接下来我们分析源码：

5.2 ArrayList常见操作

ArrayList虽然提供的方法比较多，但是常用方法如下所示，需要用到其他方法时，同学们自行查看ArrayList的帮助文档

方法	解释
int size()	返回此列表中的元素数
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, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List`<E>` subList(int fromIndex, int toIndex)	截取部分 list 注意是拿地址！

5.3 ArrayList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器。

迭代器：
(起始位置是在所有数据的前面）
（listIterator是专门为list相关数据类型提供的）

5.4 ArrayList的扩容机制

【总结】

检测是否真正需要扩容，如果是调用grow准备扩容
预估需要库容的大小

初步预估按照1.5倍大小扩容
如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

使用copyOf进行扩容

注意：若 new 时没给容量，第一次 add() 时，分配大小为10的空间。

六、使用示例

例一：
三年二班有若干(3个)学生，这些学生的信息有：姓名，年龄，分数(小数)，考试结束后，每个学生都有分数等信息。已知每个学生对象都在ArrayList当中存放，请输出每个学生的信息并排序?
提示：

我们可以指定存放自定义的类型
我们可以对集合进行排序。Collections.sort()
Collections.sort()源码：

代码实现：

import java.util.ArrayList;
import java.util.Collections;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 95439
 * Date: 2022-10-13
 * Time: 19:22
 */
class Student implements Comparable<Student>{
    private int age;
    private String name;
    private double score;

    public Student(int age, String name, double score) {
        this.age = age;
        this.name = name;
        this.score = score;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getScore() {
        return score;
    }

    public void setScore(double score) {
        this.score = score;
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                ", score=" + score +
                '}';
    }

    @Override
    public int compareTo(Student o) {
        return (int)(this.score - o.score);
    }
}

public class Test {
    public static void main(String[] args) {
        ArrayList<Student> arrayList = new ArrayList<>();
        arrayList.add(new Student(18,"小王",19.2));
        arrayList.add(new Student(19,"小红",17.8));
        arrayList.add(new Student(18,"小明",21.3));
        Collections.sort(arrayList);
        for (Student student:
             arrayList) {
            System.out.println(student);
        }
    }
}

例二：
给你两个字符串：str1:“welcome to bit”； str2:” come” 请删除第一个字符串当中，出现的第二个字符串当中的字符。结果: “wl t bit”
要求：
请用方法来实现，且请使用集合ArrayList来完成。
提示：
1.

2.
String类中的contains函数：

而

所以传参时不能传递字符，但可以传递字符串：(ch+"")。
代码实现：

public static ArrayList<Character> func(String str1,String str2){
    ArrayList<Character> arrayList = new ArrayList<>();
    for (int i = 0; i < str1.length(); i++) {
        char ch = str1.charAt(i);
        if(!str2.contains(ch+"")){
            arrayList.add(ch);
        }
    }
    return arrayList;
}

public static void main(String[] args) {
    ArrayList<Character> ret = func("welcome to bit","come");
    // System.out.println(ret);
    for (int i = 0; i < ret.size(); i++) {
        System.out.print(ret.get(i));
    }
    System.out.println();
}

注意：
有的同学会使用List接口去接收，这样做有一个明显的坏处：
在调用方法时只能调用List接口里的方法（ArrayList重写的）！！！

例三：
扑克牌。
需求:
1.买一副扑克牌出来52张牌4个花色
2.洗牌
3.起牌

代码实现：

public class Poker {
    public static final String[] SUITS = {"♠","♥","♦","♣"};
    private String suit;
    private int rank;

    public Poker(String suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }

    @Override
    public String toString() {
        return suit + 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;
    }
}

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

public class Pokers {

    // 买一副扑克牌
    public static List<Poker> buyPokers(){
        List<Poker> pokers = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13; j++) {
                pokers.add(new Poker(Poker.SUITS[i],j));
            }
        }
        return pokers;
    }

    // 洗牌
    public static void shuffle(List<Poker> pokerList){
        int n = pokerList.size();
        Random random = new Random();
        // 生成随机数时不能传入0
        for (int i = n-1; i > 0; i--) {
            int index = random.nextInt(i);
            swap(pokerList,i,index);
        }
    }

    public static void swap(List<Poker> pokerList,int i,int j){
        Poker tmp = pokerList.get(i);
        // pokerList.get(i) = pokerList.get(j); 切记要用set函数！！！
        pokerList.set(i,pokerList.get(j));
        pokerList.set(j,tmp);
    }
    
    /**
     * 起牌：
     * @param pokerList 一副经过洗牌的扑克牌
     * @param personNum 玩牌的人数
     * @param cardNum 每个人起几张牌
     */
    public static List<List<Poker>> getPoker(List<Poker> pokerList,int personNum,int cardNum){
        List<List<Poker>> hands = new ArrayList<>();
        for (int i = 0; i < personNum; i++) {
            List<Poker> handi = new ArrayList<>();
            hands.add(handi);
        }
        for (int i = 0; i < cardNum; i++) {
            for (int j = 0; j < personNum; j++) {
                List<Poker> handTmp = hands.get(j);
                handTmp.add(pokerList.remove(0));
            }
        }
        return hands;
    }
}

import java.util.List;

public class Test {
    public static void main(String[] args) {
        List<Poker> pokerList = Pokers.buyPokers();
        System.out.println("买牌： " + pokerList);
        Pokers.shuffle(pokerList);
        System.out.println("洗牌： " + pokerList);
        List<List<Poker>> hands = Pokers.getPoker(pokerList,3,5);
        for (int i = 0; i < hands.size(); i++) {
            System.out.println("第" + (i+1) + "个人的牌：" + hands.get(i));
        }
        System.out.println("剩余的牌： " + pokerList);
    }
}

例四：
杨辉三角。LeetCode链接
提示：

代码实现：

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        // 第一行：
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        ret.add(list1);
        // 从第二行开始：
        for(int i = 1; i < numRows; i++){
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1);
			// 中间需要计算的部分：[i][j] = [i-1][j-1] + [i-1][j];
            List<Integer> prevRow = ret.get(i-1);   // 前一行
            for(int j = 1 ;j < i; j++){
                int num = prevRow.get(j-1) + prevRow.get(j);
                curRow.add(num);
            }
            curRow.add(1);
            ret.add(curRow);
        }
        return ret;
    }
}