• 【JAVA数据结构系列】13_ArrayList

    文章目录

    一、List

    List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

    在集合框架中， List是一个接口，继承自Collection。
    在这里插入图片描述

    • Collection也是一个接口，该接口中规范了后序容器中常用的一些方法。
    • Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的。

    【面试题】Collection中有那些方法？

    在这里插入图片描述

    1、List常见接口介绍

    方法解释
    boolean add(E e)尾插 e
    void add(int index, E element)将 e 插入到 index 位置
    boolean addAll(Collection 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 subList(int fromIndex, int toIndex)截取部分 list

    注意： List是个接口，并不能直接用来实例化。
    如果要使用，必须去实例化List的实现类。在集合框架中， ArrayList和LinkedList都实现了List接口。

    二、ArrayList与顺序表

    线性表 (linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…

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

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

    既然顺序表就是数组，那为什么还有有顺序表呢，直接使用数组不行吗？
    原因:单单是数组还不够，还需要有一些方法支持。
    1、想统计有多少个有效数据
    2、对数组进行CURD需要提供一些方法。

    放元素的时候一定要从下标为0的地方开始放元素吗？
    一定，因为数据结构当中每次插入数据的时候，一定要有一个前驱信息。

    ArrayList方法：

    方法解释
    boolean add(E e)尾插 e
    void add(int index, E element)将 e 插入到 index 位置
    boolean addAll(Collection 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 subList(int fromIndex, int toIndex)截取部分 list

    在这里插入图片描述

    1、打印顺序表

        // 打印顺序表,只需要打印到usedSize下标就可以了
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    2、新增元素

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

    public boolean isFull() {
        //这里usedSize 必须和 elem.length
        return usedSize == elem.length;
    }

    /**
     * 检查add元素的时候，pos位置是否合法
     * @param pos
     */
    private void checkAddPos(int pos) {
        if(pos < 0 || pos > usedSize) {
            throw new PosIndexNotLegalException("pos位置不合法");
        }
    }
    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        try {
            checkAddPos(pos);
            if(isFull()) {
                //System.out.println("扩容");
                elem = Arrays.copyOf(elem,2*elem.length);
            }
            for (int i = usedSize-1; i >= pos ; i--) {
                elem[i+1] = elem[i];
            }
            elem[pos] = data;
            usedSize++;
        }catch (PosIndexNotLegalException e) {
            e.printStackTrace();
        }
    }

    • 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

    3、是否包含某个元素

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    4、查找元素下标

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    5、获取对应位置的元素

       /**
     * 获取pos位置的数据 检查合法性
     * @param pos
     */
    private void checkGetPos(int pos) {
        if(pos < 0 || pos >= usedSize) {
            throw new PosIndexNotLegalException("pos位置不合法");
        }
    }

    // 获取 pos 位置的元素
    public int get(int pos) {
        checkGetPos(pos);
        return elem[pos];
    }

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

    6、更新元素

        // 给 pos 位置的元素设为 value 更新
    public void set(int pos, int value) {
        checkGetPos(pos);
        elem[pos] = value;
    }

    • 1
    • 2
    • 3
    • 4
    • 5

    7、删除第一次出现的元素

       //删除第一次出现的关键字key
    public void remove(int key) {
        int index = indexOf(key);
        if(index == -1) {
            System.out.println("没有你要删除的数字！");
            return;
        }
        for (int i = index; i < usedSize-1; i++) {
            elem[i] = elem[i+1];
        }
        //elem[i] = null;//如果是引用数据类型则需要置空
        usedSize--;
    }

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

    8、获取顺序表长度

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

    • 1
    • 2
    • 3
    • 4

    9、清空顺序表

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    10、框架

    在集合框架中， ArrayList是一个普通的类，实现了List接口，具体框架图如下：
    在这里插入图片描述

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

    11、ArrayList构造

    方法解释
    ArrayList()无参构造
    ArrayList(Collection c)利用其他 Collection 构建 ArrayList
    ArrayList(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已经限定了 ，list2中只能存储整形元素
	// list3构造好之后 ，与list中的元素一致
	ArrayList<Integer> list3 = new ArrayList<>(list2);
	// 避免省略类型 ，否则：任意类型的元素都可以存放 ，使用时将是一场灾难
	List list4 = new ArrayList();
	list4.add("111");
	list4.add(100);
}

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

    12、subList方法

    用法：从list当中截取一段内容，左闭右开，
    在这里插入图片描述

    public class Test07 {
    public static void main(String[] args) {
        List<String> list=new ArrayList<>();
        list.add("JavaSE");
        list.add("JavaEE");
        list.add("JavaWeb");
        list.add("JVM");
        list.add("123");
        System.out.println(list);
        List<String> ret=list.subList(1,3);//只包含下标是1和2的
        System.out.println(ret);
    }
}

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

    在这里插入图片描述
    存在的问题：由于截取是直接取数组当中的原下标的地址，因此当更新截取后的list时，原来的元素也会被更改。

            System.out.println(list);
        List<String> ret=list.subList(1,3);
        System.out.println(ret);
        System.out.println("===更新===");
        ret.set(0,"更新后");
        System.out.println(list);
        System.out.println(ret);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    在这里插入图片描述

    13、ArrayList遍历

            List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

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

    // 使用下标+for遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();

    • 1
    • 2
    • 3
    • 4
    • 5
    // 借助foreach遍历
        for (Integer integer : list) {
            System.out.print(integer + " ");
        }
        System.out.println();

    • 1
    • 2
    • 3
    • 4
    • 5
            Iterator<Integer> it = list.listIterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        }
        System.out.println();

    • 1
    • 2
    • 3
    • 4
    • 5

    14、扩容

    ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容

        Object[] elementData;  // 存放元素的空间
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间是0
private static final int DEFAULT_CAPACITY = 10; // 默认容量大小
public boolean add(E e) {
        ensureCapacityInternal(size + 1); // Increments modCount!!
        elementData[size++] = e;
        return true;
        }

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
        }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

// overflow-conscious code
        if (minCapacity - elementData.length > 0)
        grow(minCapacity);
        }

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//可分配的最大空间为整数的最大值-8
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);
        }

private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0 ，抛出OutOfMemoryError异常
        if (minCapacity < 0)
        throw new OutOfMemoryError();

        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

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

    三、ArrayList的应用

    1、打牌

    public class Card {
	public int rank;   // 牌面值
	public String suit; // 花色
	@Override
	public String toString() {
		return String.format("[%s %d]", suit, rank);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    import java.util.List;
        import java.util.ArrayList;
        import java.util.Random;

public class CardDemo {
    public static final String[] SUITS = {"♠", "v", "♣", "♦"};
    // 买一副牌
    private static List<Card> buyDeck() {
        List<Card> deck = new ArrayList<>(52);
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13; j++) {
	                String suit = SUITS[i];
	                int rank = j;
                    Card card = new Card();
					card.rank = rank;
			        card.suit = suit;
			        deck.add(card);
		        }
        }

        return deck;
        }

private static void swap(List<Card> deck, int i, int j) {
        Card t = deck.get(i);
        deck.set(i, deck.get(j));
        deck.set(j, t);
        }

private static void shuffle(List<Card> deck) {
        Random random = new Random(20190905);
        for (int i = deck.size() - 1; i > 0; i--) {
        int r = random.nextInt(i);
        swap(deck, i, r);
        }
        }

public static void main(String[] args) {
        List<Card> deck = buyDeck();
        System.out.println("刚买回来的牌:");
        System.out.println(deck);
        shuffle(deck);
        System.out.println("洗过的牌:");
        System.out.println(deck);
// 三个人 ，每个人轮流抓 5 张牌
        List<List<Card>> hands = new ArrayList<>();
        hands.add(new ArrayList<>());
        hands.add(new ArrayList<>());
        hands.add(new ArrayList<>());

        for (int i = 0; i < 5; i++) {
	        for (int j = 0; j < 3; j++) {
	//	        hands.get(j).add(deck.remove(0));
	            Card card=cards.remove(0);//每次都把0下标的牌给分配出去，因为0下标的牌会改变
                hands.get(j).add(card);
	        }
        }
        System.out.println("剩余的牌:");
        System.out.println(deck);
        System.out.println("A 手中的牌:");
        System.out.println(hands.get(0));
        System.out.println("B 手中的牌:");
        System.out.println(hands.get(1));
        System.out.println("C 手中的牌:");
        System.out.println(hands.get(2));

        }
}        

    • 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

    2、杨辉三角

    题目》》

    class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret=new ArrayList<>();
        List<Integer> list=new ArrayList<>();
        list.add(1);
        ret.add(list);
        for(int i=1;i<numRows;i++){
            List<Integer> curRow=new ArrayList<>();
            List<Integer> preRow=ret.get(i-1);
            curRow.add(1);
            for(int j=1;j<i;j++){
                int tmp=preRow.get(j-1)+preRow.get(j);
                curRow.add(tmp);
            }
            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

    四、顺序表的问题及思考

    1. 顺序表中间/头部的插入删除，时间复杂度为O(N)
    2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
    3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

    思考： 如何解决以上问题呢？需要使用链表LinkedList。

  • 相关阅读:
    因密封件故障导致接头泄漏的原因有哪些
    EXPLAIN的使用
    【Lilishop商城】No2-4.确定软件架构搭建三（本篇包括ES检索）
    【图像处理】:Otsu算法最大类间方差法（大津算法：附源码）
    【漏洞复现】短视频矩阵营销系统 ajax_uplaod接口处存在任意文件上传
    【无标题】
    Go | 闭包的使用
    力扣刷题-字符串-替换分隔符_空格
    Python学习小组课程P4-Python办公（1）Excel保存
    【右击打开cmd】
  • 原文地址：https://blog.csdn.net/wxfighting/article/details/126084578