【数据结构】ArrayList和顺序表

1.线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是一种数据结构，一个线性表是n个具有相同特性的数据元素的有限序列。

常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部）

​

2.顺序表

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

要实现的功能

public class SeqList {
// 打印顺序表
public void display() { }
// 新增元素,默认在数组最后新增
public void add(int data) { }
// 在 pos 位置新增元素
public void add(int pos, int data) { }
// 判定是否包含某个元素
public boolean contains(int toFind) { return true; }
// 查找某个元素对应的位置
public int indexOf(int toFind) { return -1; }
// 获取 pos 位置的元素
public int get(int pos) { return -1; }
// 给 pos 位置的元素设为 value
public void set(int pos, int value) { }
//删除第一次出现的关键字key
public void remove(int toRemove) { }
// 获取顺序表长度
public int size() { return 0; }
// 清空顺序表
public void clear() { }
}

具体代码实现

​

**MyArrayList **

package sqlist;

import java.util.Arrays;

public class MyArrayList {
    public int[] elem;
    public int usedSize;
    private static final int DEFAULT_SIZE = 4 ;
    public MyArrayList(){
        this.elem = new int[DEFAULT_SIZE];
    }

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

    /**
     * 判断顺序表是否满了
     * @return 如果满了,返回true  没满,返回false
     */
    public boolean isFull(){
        return this.usedSize==this.elem.length;
    }
    // 新增元素,默认在数组最后新增
    public void add(int data) {
        //1.判断顺序表是否满了，如果满了就扩容为原来的两倍
        if(isFull()){
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        //2.没满就进行插入
        this.elem[usedSize]=data;
        usedSize++;
    }

    /**
     * 判断pos位置是否合法
     * @param pos  想插入的位置
     * @return 合法返回true  不合法返回false
     */
    private boolean checkPosInAdd(int pos){
        if(pos<0 || pos>this.usedSize){
            System.out.println("pos位置不合法");
            return false;
        }
        return true;
    }
    // 在 pos 位置新增元素  (插入到指定位置)
    public void add(int pos, int data) {
        //1.判断pos位置的合法性
        if(!checkPosInAdd(pos)){
            throw new MyArrayListIndexOutOfException("添加方法的pos不合理");
        }
        //2.判断是否满了
        if(isFull()){
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        //3.挪数据
        for (int i = this.usedSize-1; i >=pos ; i--) {
            this.elem[i+1]=this.elem[i];
        }
        //挪完了数据，插入
        this.elem[pos]=data;
        this.usedSize++;
    }
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i]==toFind){
                return i;
            }
        }
        return -1;
    }
    private boolean checkPosInGet(int pos){
        if(pos<0 || pos>=this.usedSize){
            System.out.println("pos位置不合法");
            return false;
        }
        return true;
    }
    private boolean isEmpty() {
        return this.usedSize == 0;
    }
    // 获取 pos 位置的元素
    public int get(int pos){
        if(!checkPosInAdd(pos)){
            throw new MyArrayListIndexOutOfException("获取pos下标时，位置不合法");
        }
        if(isEmpty()){
            throw new MyArrayListEmptyException("获取元素的时候，顺序表为空");
        }
        return this.elem[pos];
    }
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        //判断pos位置的合法性
        if(!checkPosInGet(pos)){
            throw new MyArrayListIndexOutOfException("更新pos下标的元素，位置不合法");
        }
        //如果合法，那么其实不用判断顺序表为空的状态了
        if(isEmpty()){
            throw new MyArrayListEmptyException("顺序表为空");
        }
        //其实顺序表为满的情况下也可以更新，也不必要判断顺序表是否满
        this.elem[pos] = value;

    }

    /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) {
        if(isEmpty()){
            throw new MyArrayListEmptyException("顺序表为空，不能删除！");
        }
        int index = indexOf(key);
        if(index == -1){
            System.out.println("不存在你要删除的数据");
            return ;
        }
        for (int i = index; i <this.usedSize-1 ; i++) {
                this.elem[i] = this.elem[i + 1];
        }
        //删除完成
        this.usedSize--;
        //this.elem[usedSize]=null;  如果是引用类型，这里需要置为空
    }
    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }
    // 清空顺序表
    public void clear(){
        this.usedSize = 0;
        /*
        如果是引用数据类型得一个一个置为空 这样做才是最合适的
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = null;
        }
         */
    }
}

**MyArrayListEmptyException **

package sqlist;

public class MyArrayListEmptyException extends RuntimeException{
    public MyArrayListEmptyException(){

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

MyArrayListIndexOutOfException

package sqlist;

public class MyArrayListIndexOutOfException extends RuntimeException{
    public MyArrayListIndexOutOfException() { }
    public MyArrayListIndexOutOfException(String message){
        super(message);
    }
}

分析：

**1.新增元素，默认在数组最后新增 **

​

如果是满的，那我们就需要扩容

​

我们是这样操作的，之后我们测试一下是否能达到我们的目的

​

2.在pos位置新增元素

​

那么我们的步骤就是

​

** **我们是如何判断pos位置的合法性的呢？

​

我们怎么挪动数据并且插入数据的呢？

​

最后我们测试一下是否可以达到我们的目的

​

​

3. 判断是否包含某个元素

​

4.删除某个元素

​

​

3.ArrayList

刚刚的顺序表是由我们自己实现的，而在Java中有它自己的顺序表，即我们接下来要介绍的

**ArrayList **

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

补充

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

源码的分析

​

问题：当调用不带参数的构造方法时，这个数组默认大小是多少？

  答案是0

第一个问题：既然数组的大小是0，那么是怎么Add元素的呢

我们得出结论：第一次调用 add 的时候，我们底层的数组才变成了10

第二个问题：扩容函数grow函数

ArrayList的构造

方法****解释ArrayList()无参构造ArrayList(Collection<? extends E> c)利用其他 Collection 构建 ArrayListArrayList(int initialCapacity)指定顺序表初始容量
我们先看一下源码

​

​

   public static void main(String[] args) {
        // ArrayList创建，推荐写法
// 构造一个空的列表
        List<Integer> list1 = new ArrayList<>();
// 构造一个具有10个容量的列表
        List<Integer> list2 = new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);
// list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素
// list3构造好之后，与list中的元素一致
        ArrayList<Integer> list3 = new ArrayList<>(list2);

注：我们要避免省略类型

// 避免省略类型，否则：任意类型的元素都可以存放，使用时将会出现很大的问题
        List list4 = new ArrayList();
        list4.add("111");
        list4.add(100);

ArrayList的常见操作

方法****解释boolean add(E e)尾插 evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection<? extends E> c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一个 oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 位置元素设置为 elementvoid clear()清空boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标List<E> subList(int fromIndex, int toIndex)截取部分 list

ArrayList遍历

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

        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.add(4);
        arrayList.add(5);
        // 使用下标+for遍历
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i)+" ");
        }
        System.out.println();

        // 借助 foreach 遍历
        for (Integer x : arrayList) {
            System.out.print(x+" ");
        }
        System.out.println();
        System.out.println("==========================");

        //使用迭代器
        Iterator<Integer> it = arrayList.iterator();
        while(it.hasNext()){
            System.out.print(it.next()+" ");
        }

ArrayList的扩容机制

1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要库容的大小，初步预估按照1.5倍大小扩容，如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容，真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用copyOf进行扩容

4.杨辉三角

力扣

​
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> one = new ArrayList<>();
        one.add(1);
        ret.add(one);
        //i 代表每一行
        for (int i = 1; i < numRows; i++) {
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1);//这一行开始的 1
            //j 代表这一行的每个元素
            for (int j = 1; j < i ; j++) {
                //curRow[i][j] = 前一行[i-1][j] + 前一行[i-1][j-1]
                List<Integer> preRow = ret.get(i-1);//前一行
                int x = preRow.get(j) + preRow.get(j-1);
                curRow.add(x);
            }
            // j==i  这一行最后的 1
            curRow.add(1);
            ret.add(curRow);
        }
        return ret;
    }
}

​

5.去掉第一个字符串当中与第二个字符串相同的内容

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

public class TestDemo {
    public static List<Character> func(String s1,String s2){
        if( s1==null || s2==null){
            return null;
        }
        if( s1.length()==0 || s2.length()==0 ){
            return null;
        }
        List<Character> ret = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            char ch = s1.charAt(i);
            if(!s2.contains(ch+"")){
                ret.add(ch);
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        String s1 = "welcome to china";
        String s2 = "come";
        List<Character> ret = func(s1,s2);
        for (char ch : ret) {
            System.out.print(ch);
        }
    }
}

6.扑克牌

package demo1;

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

class Card {
    private 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+"]";
    }
}
public class TestCard {
    public static final String[]suits={"♥","♠","♣","♦"};
    public static List<Card> buyCard(){
        List<Card> desk = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13 ; j++) {
                String suit = suits[i];
                Card card = new Card(suit,j);
                desk.add(card);
            }
        }
        return desk;
    }

    /**
     *
     * @param cardList
     */
    public static void shuffle(List<Card> cardList) {
        for (int i = cardList.size()-1 ; i >0 ; i--) {
            Random random = new Random();
            int index = random.nextInt(i);
            swap(cardList,i,index);
        }
    }
    public static void swap(List<Card>cardList,int i,int j){
        Card tmp = cardList.get(i);
        cardList.set(i,cardList.get(j));
        cardList.set(j,tmp);
    }
    public static void main(String[] args) {
        List<Card> cardList = buyCard();
        System.out.println("买牌"+cardList);
        shuffle(cardList);
        System.out.println("洗牌"+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++) {
                //每次揭牌都去获取 cardList的 0下标的数据【删除】
                Card card = cardList.remove(0);
                List<Card> hand = hands.get(j);
                hand.add(i,card);
            }
        }
        System.out.println("第1个人的牌："+hand1);
        System.out.println("第2个人的牌："+hand2);
        System.out.println("第3个人的牌："+hand3);

        System.out.println("剩余的牌"+cardList);

    }
}