侧边栏壁纸
博主头像
快乐江湖的博客博主等级

更多内容请点击CSDN关注“快乐江湖”

  • 累计撰写 127 篇文章
  • 累计创建 33 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录
Java基础教程

第十四章第一节：Java集合框架之ArrayList

快乐江湖
快乐江湖
2023-03-23 / 0 评论 / 0 点赞 / 13 阅读 / 15631 字

一：关于List

（1）从Java实现角度看待List

List：在Java集合框架中，List是一个接口，继承自Collection

  • 接口会规定自己子类的一些公用方法

下图分别是Iterable和Collection接口中的常用方法，由于List继承自它们，所以这些方法在List中也有，同时List会根据自身特点拓展出一些新的方法

（2）从数据结构视角看待

List：从数据结构视角来看，List就是一个线性表，即$n$个具有相同类型元素的有限序列。线性表又分别对应

  • 顺序表：即ArrayList
  • 链表：即LinkedList

（3）注意

List作为接口，自然是不能实例化对象的，但是它可以去引用其他对象，例如引用ArrayList或LinkedList。所以在实例化对象时就会有如下两种不同的方法，他们区别如下

  • 方法一：所有对象只能使用List接口中存在的方法
  • 方法二：所有对象不仅可以使用List接口中存在的方法，而且还可以使用各自的方法
 //方法一
 List<Integer> list1 = new ArrayList<>();
 List<Integer> list2 = new LinkedList<>();
 List<Integer> list3 = new Stack<>();

 //方法二
 ArrayList<Integer> list11 = new ArrayList<>();
 LinkedList<Integer> list22 = new LinkedList<>();
 Stack<Integer> list33 = new Stack<>();

这两种方式不存在谁优谁劣的问题，只是适用情况有所不同。比如方法一看起来局限很大，但是在做形参时却很有用

  • func1(List<Integer> list)：只要实现了List接口，就可以引用
  • func2(ArrayList<Integer> arraylist)：只能接受ArrayList对象

二：线性表和顺序表概念

（1）线性表

线性表(Linear List)：零个或多个数据元素的有限序列

  • 元素之间是有顺序的
  • 若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他元素都有且只有一个前驱和后继
  • 线性表强调有限，因此像“所有的整数按递增次序排列”这样的论述很明显就不是线性表

线性表可以表示为
$$L=(a{1},a{1},…,a{i+1},…,a{n})$$

  • $a_{i}$是线性表第$i$个元素线性表中的 位序
  • $a{1}$是表头元素，$a{n}$是表尾元素
  • 位序是从1开始，而不是从0开始的
  • 线性表的个数$n$($n>=0$) 定义为线性表长度，当n=0时，称为空表

（2）顺序表

A：顺序表定义

顺序表：也叫做线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素

  • 注意：虽然顺序表和数组很相似，但是他们不是一个东西。单纯的数组虽然也能达到存取元素的目的，但是其安全性和可用性并不强，而顺序表是在数组的基础上建立起来的一个完整的类，对其数据存取、增删查改做出了严格的规定，所以十分完善和健壮

B：顺序表实现

import javafx.geometry.Pos;

import java.awt.font.TextMeasurer;
import java.util.Arrays;

public class MyArrayList {
    public int[] elem;//核心数组
    public int usedSize;//记录有效数据个数
    public static final int DefaultCapacity = 2;//默认顺序表容量

    //构造函数
    public MyArrayList(){
        this.elem = new int[DefaultCapacity];
    }

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

    //新增元素（默认新增在最后）
    public void add(int data){
        //如果数组已经满了，那么进行扩容（2倍）
        if(isFull()){
            elem = Arrays.copyOf(elem, 2*elem.length);//可查看Arrays用法
        }
        elem[usedSize] = data;
        usedSize++;
    }

    //新增元素（在pos位置新增）
    public void add(int pos, int data){
        try{
            //检查位置是否合法
            checkAddPos(pos-1);
            //如果数组已经满了，那么进行扩容（2倍）
            if(isFull()){
                elem = Arrays.copyOf(elem, 2*elem.length);//可查看Arrays用法
            }
            //如果合法则继续执行
            for(int i = usedSize-1; i>=pos-1; i--){
                elem[i+1] = elem[i];
            }
            elem[pos-1] = data;
            usedSize++;
        }catch (PosIndexNotLegalException e){
            //如果非法抛出异常后捕获
            e.printStackTrace();
        }

    }

    //判断顺序表是否满
    public boolean isFull(){
        return usedSize == elem.length;
    }

    //检查add元素时，pos位置是否合法？
    private void checkAddPos(int pos){
        if(pos < 0 || pos > usedSize){
            throw  new PosIndexNotLegalException("所给位置非法");//抛出异常
        }
    }

    //检查get元素时，pos位置是否合法？（注意区别上面，因为add元素时，pos位置是可以等于usedSize的）
    private void checkGetPos(int pos){
        if(pos < 0 || pos >= usedSize)
            throw new PosIndexNotLegalException("所给位置非法");
    }

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

    //返回某个元素对应位置，如果返回-1，表示该元素不存在
    public int indexOf(int data){
        for(int i = 0; i < usedSize; i++){
            if(elem[i] == data)
                return i;
        }
        return -1;
    }

    //获取pos位置的元素
    public int get(int pos){
        int retVal = -1;
        try{
            checkGetPos(pos-1);
            retVal = elem[pos-1];
        }catch (PosIndexNotLegalException e) {
            e.printStackTrace();
        }
        return retVal;
    }

    //将pos位置处的元素设置为data
    public void set(int pos, int data){
        checkGetPos(pos-1);
        elem[pos-1] = data;
    }

    //删除第一次出现的data
    public void del(int data){
        //首先检查此元素是否存在
        int index = indexOf(data);
        if(index == -1){
            System.out.println("此元素不存在");
            return;
        }
        for(int i = index; i <usedSize-1; i++){
            elem[i] = elem[i+1];
        }
        usedSize--;
    }

    //销毁顺序表
    public void clear(){
        usedSize = 0;
    }
}

三：ArrayList

（1）介绍

ArrayList：Java集合框架中，ArrayList就是顺序表（可动态扩容），它是一个普通的类，实现了List接口

  • 实现了RandomAccess接口表明ArrayList可以随机访问
  • 实现了Cloneable接口表明ArrayList可以clone
  • 实现了Serializable接口表明ArrayList是支持序列化的
  • ArrayList线程不安全，适用于单线程。在多线程下选择Vector

（2）使用

A：构造方法

ArrayList 构造方法：如下

  • ArrayList()：无参构造
  • ArrayList(Collection <? extends E> c)：利用其它Collection构建ArrayList
  • ArrayList(int intialCapacity)：指定顺序表初始容量
List<String> list = new ArrayList<String>

其他构造方式如下

public class TestDemo {
    public static void main(String[] args) {
        ArrayList <String> arrayList_String = new ArrayList<>(); //无参构造
        ArrayList <Double> arrayList_Double = new ArrayList<>(10);//指定容量为10
        List<Integer> list = new ArrayList<>(); //利用List接口引用
        ArrayList <Double> arrayList_Double2 = new ArrayList<>(arrayList_Double);//也可以这样
    }
}

B：常见操作

ArrayList常见操作：ArrayList提供了很多方法，其中常用方法如下

  • 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

下面是一个测试例子，涵盖上面的方法

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

public class TestDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("JavaSE");
        list.add("JavaWeb");
        list.add("JavaEE");
        list.add("JVM");
        list.add("软件测试");
        System.out.println(list);
        System.out.println("获取list中有效元素个数：" + list.size());

        System.out.println("获取索引为2上的元素：" + list.get(2));

        list.set(2, "Javaee");
        System.out.println("设置索引为2上的元素为Javaee：" + list);

        list.add(2, "java数据结构");
        System.out.println("在list的索引为2处插入Java数据结构：" + list);

        list.remove("JVM");
        System.out.println("删除list中的JVM：" + list);

        list.remove(1);
        System.out.println("删除list中索引为1处的元素：" + list);

        System.out.println("坚持list中是否存在数据库这个元素？" + list.contains("数据库"));

        System.out.println("从后往前查找Javaee第一次出现的位置：" + list.indexOf("Javaee"));

        List<String> ret = list.subList(1, 3);
        System.out.println("使list中[1,3)之间的元素构成一个新的List返回：" + ret);

        list.clear();
        System.out.println("清空list并打印其大小：" + list.size());
    }
}

C：ArrayList遍历

①：使用for循环

public class TestDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(23);
        list.add(68);
        list.add(91);
        list.add(53);
        list.add(44);

        for(int i = 0; i < list.size(); i++){
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
    }
}

②：使用foreach遍历循环

public class TestDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(23);
        list.add(68);
        list.add(91);
        list.add(53);
        list.add(44);

        for(Integer integer : list){
            System.out.print(integer + " ");
        }
        System.out.println();
    }
}

③：使用迭代器

public class TestDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(23);
        list.add(68);
        list.add(91);
        list.add(53);
        list.add(44);

        Iterator<Integer> iter = list.iterator();
        while(iter.hasNext()){
            System.out.print(iter.next() + " ");
        }
        System.out.println();
    }
}

D：ArrayList扩容

ArrayList扩容：扩容规则如下

①：检测是否真正需要扩容，如果是调用grow准备扩容

②：预估需要扩容的大小

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

③：使用copyOf进行扩容

四：ArrayList经典应用

（1）扑克牌

使用Java中的ArrayList构造一副扑克牌，并完成洗牌操作

Poker.java

package card;


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

//描述一张牌
class Card{
    public int cardFaceSize;//牌面大小
    public String cardDecor;//花色

    public Card(int cardFaceSize, String cardDecor) {
        this.cardFaceSize = cardFaceSize;
        this.cardDecor = cardDecor;
    }

    @Override
    public String toString() {
        return "【" + cardDecor + " " + cardFaceSize + "】";
    }
}

public class Poker {
    public static final String[]cardDecors = {"♥", "♠", "♣", "♦"};//花色数组

    //买来一副扑克
    public List<Card> buyPoker(){
        List<Card> poker = new ArrayList<>();//用于存放所有牌
        //有4种花色的牌，每种花色的牌有13张
        for(int i = 0; i < 4; i++){
            for(int j = 1; j <= 13; j++){
                Card card = new Card(j, cardDecors[i]);
                poker.add(card);
            }
        }
        return poker;
    }

    //交换牌，便于完成洗牌操作
    private static void swap(List<Card> poker, int i, int j){
        Card temp = poker.get(i);
        poker.set(i, poker.get(j));
        poker.set(j, temp);
    }

    //洗牌
    public static void shuffle(List<Card> poker){
        for(int i = poker.size()-1; i > 0; i--){
            Random random = new Random();
            int index = random.nextInt(i); // 产生一个[0, i)的随机整数
            swap(poker, index, i);//将这两个牌交换
        }
    }
}

TestDemo.java

package card;

import java.security.Policy;
import java.util.List;

public class TestDemo {
    public static void main(String[] args) {
        //买牌
        Poker poker = new Poker();
        List<Card> ret = poker.buyPoker();
        System.out.println(ret);

        //洗牌
        Poker.shuffle(ret);
        System.out.println(ret);
    }
}

（2）杨辉三角

LeetCode链接 

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for(int i = 0; i < numRows; i++){
            List<Integer> temp = new ArrayList<Integer>();
            for(int j = 0 ; j <= i; j++){
                if(j==0 || j==i){
                    temp.add(1);
                }else{
                    temp.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
                }
            }
            ret.add(temp);
        }
        return ret;
    }
}

0
Java 集合框架
版权归属： 快乐江湖
本文链接： https://blog.zxdemo.top/archives/Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6%E4%B9%8BArrayList
许可协议： 本文使用《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》协议授权

评论区