开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> ArrayList与顺序表 -> 正文阅读

[数据结构与算法]ArrayList与顺序表

1.ArrayList的简介

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

在这里插入图片描述
【说明】：

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

由于ArrayList的底层是顺序表，所以在学习ArrayList之前先来了解一下顺序表

2.顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表属于线性表的一种，线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物
理上存储时，通常以数组和链式结构的形式存储。

要向对Java提供个我们的ArrayList使用自如，我们应该先简单模拟实现一个我们自己的顺序表

2.1 顺序表接口的实现

我们在上面提到：顺序表的底层是数组，可能有些同学就会有这样的疑问？？
既然底层是数组，为什么我们不直接取操作数组呢，而是要将顺序表写成一个类呢？
举一个简单的例子：

对于下面的顺序表：

我们如何知道这个数组中存储了多少个有效的数据呢？？这是就需要我们在顺序表这个类中定义一个变量，用来记录有效数据的个数

（1）顺序表中的字段及构造方法
??

public class MyArrayList {

    public int[] elem; //存储元素的数组
    public  int usedSize;//记录顺序表中的有效数据个数
    private static final  int DAFAULT_SIZE =10;//数组默认分配的大小
    
    public MyArrayList() {
        this.elem = new int[DAFAULT_SIZE];
    } //构造方法：在创建对象的时候，会创建一个能装有10个int类型元素大小的数组
 }

（2）打印顺序表函数
??

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

（3）新增元素,默认在数组最后新增
??

 private boolean isFull(){
        return this.usedSize==this.elem.length;
    }
    // 新增元素,默认在数组最后新增
    public void add(int data) {
    //1.判断是否满，如果满的，进行扩容
          if(isFull()){
          //扩容
             this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
          }
          //2.如果不满进行插入
          this.elem[usedSize]=data;
          this.usedSize++;
    }

【注意】：

在新增元素的时候先判断数组是否满，如果满需要扩容
对于判满函数，isFull封装成private，因为对于private函数只在add函数中使用

（4）在 pos 位置新增元素
??

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) {
     if(checkPosInAdd(pos)==false){
         throw  new MyArrayListIndexIllegal("添加方法的pos不合理");
     }
        if(isFull()){
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }
        for (int i = usedSize-1; i >=pos ; i--) {
             this.elem[i+1]=this.elem[i];
        }
        this.elem[pos]=data;
        this.usedSize++;
    }

【注意】：

在顺序表中插入元素时候，要插入的位置的前面一定要由元素

对于这个数组来说，此时是不可以在4位置插入元素的
pos位置不合法的异常时自定义的
🌀

public class MyArrayListIndexIllegal  extends RuntimeException{
    public MyArrayListIndexIllegal() {

    }

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

挪动数据时一定要从最后面的元素开始挪动
例如：

（5）判定是否包含某个元素
🌁 遍历一遍数组

public boolean contains(int toFind) {
        for (int i = 0; i <this.usedSize ; i++) {
            if(this.elem[i]==toFind){
                return true;
            }
        }
        return false;
         }

【注意】：
在这里插入图片描述

（6）查找某个元素对应的位置
🌊

public int indexOf(int toFind) {

        for (int i = 0; i <this.usedSize ; i++) {
            if(this.elem[i]==toFind){
                return i;
            }

        }
        return -1;
    }

（7）获取 pos 位置的元素

 private boolean checkPosInGet(int pos){
        if(pos<0||pos>=this.usedSize){
            System.out.println("pos位置不合法");
            return false;
        }
        return true;
    }
  // 获取 pos 位置的元素
    public int get(int pos) {

        if(checkPosInGet(pos)==false){
            throw new MyArrayListIndexIllegal("获取pos下标时，pos位置不合法");
        }
        if(isEmpty()){
            throw  new MyArraysEmptyException(" 空数组异常");
        }
        return this.elem[pos];
    }

【注意】：

判断pos位置合法性时，pos<0 | | pos>=usedSize 都是不合法的，usedSize的位置是没有元素的

（8）获取顺序表长度
🐶

   public int size() {
        return this.usedSize;
    }

（9）将 pos 位置的元素更新为 value
🐱

 public void set(int pos, int value) {
        if(!checkPosInGet(pos)){
            throw new MyArrayListIndexIllegal("更新pos位置元素时，位置不合法");
        }
        this.elem[pos]=value;
        
    }

【注意】：

更新pos位置元素的前提是pos位置一定要有元素，所以要先检验pos位置的合法性

（9）删除第一次出现的关键字key
🐺

 //删除第一次出现的关键字key
    public void remove(int toRemove) {
        if ( isEmpty()) {
            throw new MyArraysEmptyException("顺序表空异常");
        }          //1.判断顺序表是否为空
        int index=0;
        int i = 0;
        //2.遍历寻找要删除的元素，如果找到将元素下表存储在index中
        for (; i < this.usedSize; i++) {
            if(toRemove==this.elem[i]){
                index=i;
                break;
            }
        }
        //3.如果没找到，直接返回
        if(i==this.usedSize){
            System.out.println("toRemove不存在");
            return;
        }
        //4.将要删除的元素覆盖掉
        for (int j = index; j <this.usedSize-1 ; j++) {
            this.elem[j]=this.elem[j+1];
        }
         this.usedSize--;
        //this.elem[uedeSize]=null;   如果顺序表存储的是引用类型治理需要置为空
    }

【注意】：
在这里插入图片描述
（11）空顺序表
🐯

 // 清空顺序表
    public void clear() {
        this.usedSize=0;
        //如果放的是引用类型，需要遍历一遍顺序表，将每个元素都置为null，最后再将this.usedSize=0;
    }

3.ArrayList的使用

3.1ArrayList中的部分源码

几个重要的属性
在这里插入图片描述

3.2ArrayList的构造方法

1.无参构造方法
在这里插入图片描述
🐯

  public static void main(String[] args) {
        ArrayList<Integer> arrayList=new ArrayList<>(); //相当于创建好了一个顺序表
          arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.add(4);
        arrayList.add(5);
        System.out.println(arrayList);//将arraylist中的数据以字符串的形式输出
    }

执行结果：
在这里插入图片描述
【注意】：

 ArrayList<Integer> arrayList=new ArrayList<>();

当我们调用这个构造方法的时候，并没有为数组分配空间。

真正为数组分配空间的时候的调用是add函数的时候，当插入第一个元素的时候分配空间

java arrayList.add(1);

所以并不是ArrayList的默认大小是10，只有在添加第一个元素时候才变成了0

2.利用Collection 构建 ArrayList
在这里插入图片描述

🐯

  public static void main(String[] args) {
        ArrayList<Integer> arrayList=new ArrayList<>(); //相当于创建好了一个顺序表
          arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.add(4);
        arrayList.add(5);
        System.out.println(arrayList);//将arraylist中的数据以字符串的形式输出
        
        ArrayList<Integer> arrayList1=new ArrayList<>(arrayList);
    //ArrayList<String> arrayList1=new ArrayList<>(arrayList);
        //err  Integer不属于String类型的子类    
    }

在这里插入图片描述
ArrayList每次以1.5倍扩容，假设现在的数组中放有了10个元素，在往里放元素的时候，就会进行扩容

在这里插入图片描述

3.指定顺序表初始容量
在这里插入图片描述
🐷

 public static void main(String[] args) {
        ArrayList<Integer> arrayList2=new ArrayList<>(20);

    }

4.ArrayList常用方法

在这里插入图片描述
🐗

   public static void main(String[] args) {
        ArrayList<Integer> arrayList=new ArrayList<>(); //相当于创建好了一个顺序表
      arrayList.add(1);
       arrayList.add(1,99);   //在1下标的位置添加99
         arrayList.add(2,88); //在2下标的位置添加88
        System.out.println(arrayList);
        ArrayList<Integer> arrayList2=new ArrayList<>();
        arrayList2.addAll(arrayList);
        System.out.println(arrayList2);

        arrayList.remove(1);   //传入想删除元素对应的下标
        System.out.println(arrayList);
        arrayList.remove(Integer.valueOf(88));//如果想删除某个整形元素，不能直接传，需要惊奇转换成
        //引用类型，否则会被当成index
        System.out.println(arrayList);

    }

执行结果：
在这里插入图片描述
🐫

   public static void main(String[] args) {
        ArrayList<Integer> arrayList=new ArrayList<>(); //相当于创建好了一个顺序表
        arrayList.add(1);
        arrayList.add(1,99);   //在1下标的位置添加99
        arrayList.add(2,88); //在2下标的位置添加88
        arrayList.add(3,777);
        arrayList.add(4,666);
      List<Integer> list=arrayList.subList(0,4);
        System.out.println(list);
        list.set(0,88888);
        System.out.println(arrayList);
        System.out.println(list);
    }

执行结果：
在这里插入图片描述

【注意】：
调用subList，并不会返回新对象，只是会返回截取的首地址

5.ArrayList的遍历

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

for循环

🐍

public static void main(String[] args) {

        ArrayList<Integer> arrayList=new ArrayList<>(); //相当于创建好了一个顺序表
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.add(4);
        arrayList.add(5);
        arrayList.add(6);
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i) + " ");
        }
        System.out.println();

    }
    //执行结果：
    1 2 3 4 5 6

foreach

 public static void main(String[] args) {

        ArrayList<Integer> arrayList=new ArrayList<>(); //相当于创建好了一个顺序表
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.add(4);
        arrayList.add(5);
        arrayList.add(6);

        for (Integer integer : arrayList) {
            System.out.print(integer + " ");
        }
        System.out.println();
   }
    //执行结果：
    1 2 3 4 5 6

使用迭代器
🐦

  public static void main(String[] args) {

        ArrayList<Integer> arrayList=new ArrayList<>(); //相当于创建好了一个顺序表
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.add(4);
        arrayList.add(5);
        arrayList.add(6);


      Iterator<Integer> it= arrayList.iterator();

      while (it.hasNext()){
          System.out.print(it.next()+" ");
      }
        System.out.println();

只要这个类实现了Iterable接口都可以使用迭代器

直接使用System.out.println(arrayList);打印

 public static void main22222(String[] args) {
        ArrayList<Integer> arrayList=new ArrayList<>(); //相当于创建好了一个顺序表
        arrayList.add(1);
        arrayList.add(1,99);   //在1下标的位置添加99
        arrayList.add(2,88); //在2下标的位置添加88
        arrayList.add(3,777);
        arrayList.add(4,666);
      
        System.out.println(  arrayList);
   }

ArrayList类中并没有重写toString方法，但他的父类中重写了toString方法

6.ArrayList的使用

6.1 杨辉三角

🐝

    public static List<List<Integer>> main(String[] args) {
     List<List<Integer>> list=new ArrayList<>();
     List<Integer>  one=new ArrayList<>();
     one.add(1);

     list.add(one);
        for (int i = 1; i < list.size(); i++) {
            List<Integer> curRow=new ArrayList<>();
            curRow.add(1);
            for (int j = 1; j <i ; j++) {

                List<Integer>  preRow=list.get(i-1);
                int x=preRow.get(j-1)+preRow.get(j);
                curRow.add(x);

            }
            curRow.add(1);
            list.add(curRow);
        }
   return list;
    }

实现思路：

List<List< Integer >> list=new ArrayList<>();相当于创建了一个二维数组
List<List< Integer>> list=new ArrayList<>();存储第一行的元素
one.add(1); 第一行只有一个元素1，添加到里面
通过两个for循环遍历每行每列，对于每一行，第一个元素和最后一个元素都是1，中间元素等于[i][j]=[i-1][j]+[i-1][j-1]; 每遍历完一行都要添加到list中，通过list将每一行的组织起来

6.2字符串删除

例如：
给定字符串s1=you are beautiful
s2=are
去掉字符串1当中所有的字符串2中包含的字符

实现思路：
遍历s1这个字符串中的字符，如果不在s2中就将他放在list中

👀

 public 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> list=new ArrayList<>();
        for (int i = 0; i <s1.length() ; i++) {
            char ch=s1.charAt(i);
            if(!s2.contains(ch+" ")){
                 list.add(ch);
            }
        }
        return list;
    }

6.3扑克牌

💋

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 Test1 {

    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);
        }
    }

    //交换两张牌
    private 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个人  轮流揭牌5张 i=0就是第一次
        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);//这里使用add 不能是set
            }
        }

        System.out.println("第1个人的牌："+hand1);
        System.out.println("第2个人的牌："+hand2);
        System.out.println("第3个人的牌："+hand3);

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

    }

}