1. Toy模板网首页
  2. > Toy博客

【Java】顺序表ArrayList

9月前 作者：李 ~ 分类：Toy博客 阅读(44) 违法举报

这篇具有很好参考价值的文章主要介绍了【Java】顺序表ArrayList。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、顺序表

顺序表（Sequential List）是一种基本的数据结构，它由一组连续的存储空间（例如数组）来表示线性表的数据结构。顺序表中的元素在内存中是按照其逻辑顺序依次储存的。

顺序表具有以下特点：

  1. 元素在内存中的储存是连续的，可以通过下标直接访问和定位元素。

  2. 元素之间的逻辑关系通过元素在顺序表中的位置来表示。

  3. 顺序表的长度是固定的，即在创建时需要指定最大的容量，不能动态的增长或者缩小。

总的来说，顺序表的优点就能访问元素快速、定位方便，适合频繁访问和索引的场景。但是，由于顺序表的长度是固定的，插入和删除元素都可能会移动大量的元素，造成了效率低下的问题。因此如果需要频繁的进行插入和删除操作，就应该考虑其他数据结构，比如链表了。

二、ArrayList 的简介

ArrayList是Java集合框架中的一个类，它实现了List接口，提供了动态数组的功能。它是一个可变长度的数组，可以根据需要自动调整容量。

ArrayList的继承体系结构图如下：
【Java】顺序表ArrayList,Java基础,java,ArrayList,顺序表
ArrayList的继承和实现关系：

  • 类继承关系：

    • ArrayList类继承自AbstractList类。
    • AbstractList类继承自AbstractCollection类。
    • AbstractCollection类继承自Object类。

  • 接口实现关系：

    • ArrayList类实现了List接口。
    • List接口继承自Collection接口。
    • Collection接口继承自Iterable接口。
    • Iterable接口继承自java.lang.Iterable接口。

以下是每个类和接口的简要说明：

  • ArrayList类：实现了动态数组的功能，可以根据需要自动调整容量。
  • AbstractList类：提供了List接口的一些抽象方法的实现，为实现List接口的类提供了基本的功能。
  • AbstractCollection类：提供了Collection接口的一些抽象方法的实现，为实现Collection接口的类提供了基本的功能。
  • Object类：是Java中所有类的根类。
  • List接口：表示有序的元素集合，定义了基本的操作方法，如添加、删除、查找、获取等。
  • Collection接口：表示一组对象的集合，定义了基本的操作方法，如添加、删除、查找等。
  • Iterable接口：表示可迭代的对象，定义了迭代元素的方法，用于支持迭代操作。

这些类和接口的层次结构使得ArrayList具备了列表的功能，并可以与其他集合类和接口进行交互和使用。ArrayList作为Java集合框架中的一部分，提供了丰富的功能和灵活性，使得开发人员可以方便地处理和操作动态数组。

三、ArrayList 的使用

3.1 构造方法

ArrayList类提供了多个构造方法来创建对象。以下是ArrayList的常用构造方法及其示例：

  1. ArrayList()：创建一个空的ArrayList对象。
ArrayList<String> list = new ArrayList<>();
  1. ArrayList(int initialCapacity)：创建一个具有指定初始容量的ArrayList对象。
ArrayList<Integer> list = new ArrayList<>(10);
  1. ArrayList(Collection<? extends E> c)：创建一个包含指定集合元素的ArrayList对象。
ArrayList<String> list1 = new ArrayList<>(Arrays.asList("apple", "banana", "orange"));
ArrayList<String> list2 = new ArrayList<>(list1);

示例说明：

  • 在示例1中，创建了一个空的ArrayList对象，用于存储String类型的元素。
  • 在示例2中，创建了一个具有初始容量为10的ArrayList对象，用于存储Integer类型的元素。
  • 在示例3中，通过传入一个已有的集合，创建了一个包含集合元素的ArrayList对象。

注意：在示例3中，使用了Arrays.asList()方法将元素直接传递给ArrayList的构造方法，或者直接将另一个ArrayList对象传递给构造方法。这样做可以快速初始化ArrayList，并将已有的元素添加到新创建的ArrayList中。

3.2 常见操作

ArrayList类提供了一系列方法来操作和处理列表中的元素。以下是ArrayList的一些常用方法及其示例：

  1. 添加元素：
  • add(E element)：在列表末尾添加一个元素。
  • add(int index, E element)：在指定位置插入一个元素。
ArrayList<String> list = new ArrayList<>();

list.add("apple");
list.add("banana");
list.add(1, "orange");

System.out.println(list); // 输出：[apple, orange, banana]
  1. 获取元素：
  • get(int index)：获取指定位置的元素。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");

String fruit = list.get(1);
System.out.println(fruit); // 输出：banana
  1. 删除元素：
  • remove(int index)：删除指定位置的元素。
  • remove(Object element)：删除第一个匹配的元素。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("orange");
list.add("banana");

list.remove(1); // 删除位置为1的元素
System.out.println(list); // 输出：[apple, banana]

list.remove("banana"); // 删除元素为"banana"
System.out.println(list); // 输出：[apple]
  1. 修改元素：
  • set(int index, E element)：替换指定位置的元素。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");

list.set(1, "orange"); // 替换位置为1的元素
System.out.println(list); // 输出：[apple, orange]
  1. 元素数量和判断：
  • size()：返回列表中的元素数量。
  • isEmpty()：判断列表是否为空。
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");

System.out.println(list.size()); // 输出：2
System.out.println(list.isEmpty()); // 输出：false

3.3 遍历方法

在ArrayList中，有多种遍历方法可以访问和处理列表中的元素。以下是几种常用的ArrayList遍历方法：

  1. 使用for循环遍历：
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("orange");

for (int i = 0; i < list.size(); i++) {
    String fruit = list.get(i);
    System.out.println(fruit);
}
  1. 使用增强型for循环（foreach循环）遍历：
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("orange");

for (String fruit : list) {
    System.out.println(fruit);
}
  1. 使用迭代器（Iterator）遍历：
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("orange");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String fruit = iterator.next();
    System.out.println(fruit);
}

3.4 扩容机制

在Java中，ArrayList的扩容机制是在元素数量超过当前容量时自动进行扩容。扩容操作是为了保证ArrayList能够容纳更多的元素，并提高性能。

ArrayList的扩容机制如下：

  1. 当添加新元素时，ArrayList会检查当前元素数量是否已经达到了数组的容量。
  2. 如果元素数量已经达到了容量上限，ArrayList会根据一定的策略进行扩容。
  3. 扩容操作会创建一个新的更大容量的数组，并将原数组中的元素复制到新数组中。
  4. 扩容后，ArrayList的容量会增加，可以继续添加新的元素。

具体的扩容策略如下：

  1. 初始容量为10。当第一个元素被添加时，容量增加到10。
  2. 扩容时，新容量的大小为当前容量的1.5倍。
  3. 如果当前容量的1.5倍小于所需容量，则新容量的大小为所需容量。

需要注意的是，扩容操作会涉及到数组的拷贝，因此在大规模数据的插入时，可能会有一定的性能开销。为了避免频繁的扩容操作，可以在创建ArrayList时指定一个合适的初始容量，尽量接近预期的元素数量。

以下是一个示例，展示了ArrayList的扩容过程：

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

System.out.println("初始容量：" + list.size()); // 输出：初始容量：0

for (int i = 0; i < 20; i++) {
    list.add(i);
    System.out.println("元素数量：" + list.size() + "，容量：" + list.toArray().length);
}

/* 输出：
元素数量：1，容量：10
元素数量：2，容量：10
...
元素数量：11，容量：15
元素数量：12，容量：15
...
元素数量：20，容量：30
*/

从示例中可以看到，当元素数量超过当前容量时，ArrayList会按照扩容策略自动增加容量，并将元素复制到新的数组中。在扩容过程中，容量会逐步增加，以满足添加更多元素的需求。

四、ArrayList 的模拟实现

import java.util.Arrays;

public class MyArrayList {
    private int[] elem; // 数组
    private int usedSize; // 记录有效的数据个数
    private static final int DEFAULT_SIZE = 10; // 默认数组大小

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

    // 新增元素，默认在数组最后新增
    public void add(int data){
        // 1. 检查当前顺序表是否满了
        if(isFull()){
            // 2. 如果满了就进行扩容
            elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }

        this.elem[usedSize] = data;
        this.usedSize++;
    }

    public boolean isFull(){
        return size() >= elem.length;
    }


    // 在pos位置新增元素
    public void add(int pos, int data) throws PosErrorException{

        // 判断 pos 的合法性
        if(pos > this.size() || pos < 0){
            throw new PosErrorException("pos 不合法");
        }

        // 判断当前顺序表是否满了
        if(isFull()) {
            // 扩容
            elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }

        for (int i = size() - 1; i >= pos; i--) {
            elem[i + 1] = elem[i];
        }
        elem[pos] = data;
        usedSize++;
    }

    // 获取pos下标的元素
    public int get(int pos){
        if(pos < 0 || pos >= this.size()){
            throw new PosErrorException("pos 不合法");
        }
        return elem[pos];
    }

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

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

    // 给pos位置的元素设置为value
    public int setValue(int pos, int value){
        if(pos < 0 || pos >= this.size()){
            throw new PosErrorException("pos 不合法");
        }
        int tmp = elem[pos];
        elem[pos] = value;
        return tmp;
    }

    // 删除第一次出现的元素 key
    public boolean remove(int key){
        int index = indexOf(key);
        if (index == -1)
            return false;
        for (int i = index; i < size() - 1; i++) {
            elem[i] = elem[i + 1];
        }
        this.usedSize--;
        return true;
    }

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

    // 清空顺序表内容
    public void clear(){
        this.elem = new int[DEFAULT_SIZE];
        this.usedSize = 0;
    }

    // 打印数组中的元素
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }

    public boolean isEmpty(){
        return this.usedSize == 0;
    }
}

五、ArrayList 的使用案例

5.1 扑克牌案例

class Poker {
    private int rank; // 面值
    private String suit; // 花色

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

    public int getRank() {
        return rank;
    }

    public void setRank(int rank) {
        this.rank = rank;
    }

    public String getSuit() {
        return suit;
    }

    public void setSuit(String suit) {
        this.suit = suit;
    }

    @Override
    public String toString() {
        return "【" + suit + rank + "】"; // 【♠ 2】
    }
}


public class Pokers {
    private static final String[] SUITS = new String[]{"♥", "♠", "♣", "♦"};

    public ArrayList<Poker> buyPokers(){
        ArrayList<Poker> pokers = new ArrayList<>();
        for (int i = 0; i < 4; ++i){
            for(int j = 1; j <= 13; ++j){
                String suit = SUITS[i];
                pokers.add(new Poker(j, suit));
            }
        }
        return pokers;
    }

    private void swap(ArrayList<Poker> pokerList, int i, int j){
        Poker tmp = pokerList.get(i);
        pokerList.set(i, pokerList.get(j));
        pokerList.set(j, tmp);
    }

    public void shuffle(ArrayList<Poker> pokerList){
        Random random = new Random();
        for(int i = pokerList.size() - 1; i > 0; --i){
            int index = random.nextInt(i); // [0, i)
            swap(pokerList, i, index);
        }
    }

    public static void main(String[] args) {
        Pokers pokers = new Pokers();
        ArrayList<Poker> pokerList = pokers.buyPokers();
        System.out.println("刚买回来的牌：" + pokerList);
        System.out.println();

        pokers.shuffle(pokerList);
        System.out.println("洗过的牌：" + pokerList);

        ArrayList<Poker> hand1 = new ArrayList<>();
        ArrayList<Poker> hand2 = new ArrayList<>();
        ArrayList<Poker> hand3 = new ArrayList<>();

        ArrayList<ArrayList<Poker>> hands = new ArrayList<>();
        hands.add(hand1);
        hands.add(hand2);
        hands.add(hand3);


        // 三个人轮流摸五次牌
        for(int i = 0; i < 5; ++i){
            for(int j = 0; j < 3; ++j){
                ArrayList<Poker> tmpHand = hands.get(j);
                tmpHand.add(pokerList.remove(0));
            }
        }

        for (int i = 0; i < 3; ++i){
            System.out.println("第" + (i + 1) + "个人：" + hands.get(i));
        }

        System.out.println("剩余的牌：" + pokerList);
        System.out.println(pokerList.size());
    }
}

上述代码片段包含两个类：Poker和Pokers。

Poker类表示一张扑克牌，具有rank（面值）和suit（花色）属性，以及对应的访问方法和重写的toString()方法。

Pokers类包含了一些扑克牌游戏的操作方法。其中：

  • buyPokers()方法用于生成一副完整的扑克牌，并将它们放入一个ArrayList中。
  • swap()方法用于交换扑克牌列表中两张牌的位置。
  • shuffle()方法使用Fisher-Yates（Knuth洗牌算法）算法对扑克牌列表进行洗牌。
  • main()方法包含了一个简单的扑克牌游戏的示例逻辑。首先，生成一副扑克牌，并打印出初始顺序。然后，进行洗牌操作，并打印洗牌后的顺序。接下来，模拟三个人轮流摸牌的过程，并打印每个人手中的牌以及剩余的牌。

这个示例代码演示了如何使用Poker类和Pokers类来模拟扑克牌游戏的一些操作，包括生成扑克牌、洗牌和发牌等。运行代码可以看到相应的输出结果。

5.2 杨辉三角案例

下面是一个使用 ArrayList 实现的杨辉三角案例，根据输入的 n 生成 n 行的杨辉三角：

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

public class PascalTriangle {
    public List<List<Integer>> generatePascalTriangle(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();

            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    List<Integer> prevRow = triangle.get(i - 1);
                    int num = prevRow.get(j - 1) + prevRow.get(j);
                    row.add(num);
                }
            }

            triangle.add(row);
        }

        return triangle;
    }

    public static void main(String[] args) {
        int numRows = 5;

        PascalTriangle pascalTriangle = new PascalTriangle();
        List<List<Integer>> triangle = pascalTriangle.generatePascalTriangle(numRows);

        for (List<Integer> row : triangle) {
            System.out.println(row);
        }
    }
}

在上面的代码中，generatePascalTriangle 方法用于生成杨辉三角。它通过遍历每一行，然后遍历每一行的每个位置，根据杨辉三角的性质将相应的数字添加到列表中。最后，将每一行的列表添加到杨辉三角的二维列表中。

在 main 方法中，我们指定了要生成的杨辉三角的行数 numRows 为 5，并通过调用 generatePascalTriangle 方法生成杨辉三角。然后，我们逐行打印杨辉三角的结果。

运行示例代码会输出以下结果：

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]

六、ArrayList 存在的问题

关于 ArrayList 的一些常见限制和缺点：

  1. 顺序表中间/头部的插入删除，时间复杂度为 O(N)：ArrayList 的底层实现是基于数组，当需要在中间或头部插入或删除元素时，需要进行数据的搬移操作，这会导致时间复杂度为 O(N)，其中 N 是元素的个数。因此，在需要频繁进行中间或头部的插入删除操作时，ArrayList 的性能可能不如链表（LinkedList）等数据结构。

  2. 增容需要申请新空间，拷贝数据，释放旧空间：ArrayList 在容量不足时会自动进行扩容操作，一般是通过申请更大的数组空间，并将旧数据拷贝到新空间中，然后释放旧空间。这个过程需要耗费一定的时间和资源。因此，在频繁插入大量数据或需要快速扩容的场景下，ArrayList 可能会有一定的性能开销。

  3. 增容一般是呈2倍的增长，可能会有空间浪费：ArrayList 在进行扩容时，通常会将容量扩大一倍。这是为了避免频繁的扩容操作，提高性能。然而，当在容量不断增长的情况下，如果仅插入一小部分元素并停止插入，就会导致一定的空间浪费。例如，如果当前容量为 100，满了以后增容到 200，然后再插入了 5 个数据，那么就会浪费 95 个数据的空间。这种情况下，可以考虑在需要精细控制内存使用的场景下使用其他数据结构，如 LinkedList。

总结来说，ArrayList 在访问元素和尾部插入删除等操作上具有较好的性能，但在中间/头部的插入删除、频繁的扩容和大量数据插入情况下可能存在一些性能和空间方面的问题。在实际使用时，需要根据具体场景的需求进行选择合适的数据结构。文章来源地址https://www.toymoban.com/news/detail-526895.html

到了这里，关于【Java】顺序表ArrayList的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【JavaSE】Java基础语法(十二)：ArrayList

    【JavaSE】Java基础语法(十二)：ArrayList

    集合和数组的区别 : 共同点：都是存储数据的容器 不同点：数组的容量是固定的，集合的容量是可变的 ArrayList ： 可调整大小的数组实现 是一种特殊的数据类型，泛型。 怎么用呢 ? 在出现E的地方我们使用引用数据类型替换即可 举例：ArrayList, ArrayList 成员方法 : 案例需求

    2024年02月06日
    浏览(58)
  • java基础 -02java集合之 List，AbstractList，ArrayList介绍

    java基础 -02java集合之 List，AbstractList，ArrayList介绍

    在正式List之前，我们先了解我们补充上篇Collection接口的拓展实现，也就是说当我我们需要实现一个不可修改的Collection的时候，我们只需要拓展某个类，也就是AbstractCollection这个类，他是Collection接口的骨干实现，并以最大限度的实现了减少此接口所需要的工作; 如上两图进行

    2024年01月20日
    浏览(41)
  • java面试基础 -- ArrayList 和 LinkedList有什么区别, ArrayList和Vector呢?

    java面试基础 -- ArrayList 和 LinkedList有什么区别, ArrayList和Vector呢?

    目录 基本介绍 有什么不同?? ArrayList的扩容机制 ArrayLIst的基本使用 ArrayList和Vector 还记得我们的java集合框架吗, 我们来复习一下, 如图:          可以看出来 ArrayList和LinkedList 都是具体类, 他们都是接口List的实现类. 但是他们底层的逻辑是不同的, 相信学过这个的应该大概有个

    2024年02月12日
    浏览(37)
  • java面试基础 -- ArrayList 和 LinkedList有什么区别

    java面试基础 -- ArrayList 和 LinkedList有什么区别

    目录 基本介绍 有什么不同?? ArrayList的扩容机制 ArrayLIst的基本使用 ArrayList和Vector 还记得我们的java集合框架吗, 我们来复习一下, 如图:          可以看出来 ArrayList和LinkedList 都是具体类, 他们都是接口List的实现类. 但是他们底层的逻辑是不同的, 相信学过这个的应该大概有个

    2024年02月12日
    浏览(50)

  • java基础：初始化ArrayList时直接赋值的四种方式

    在Java中，初始化ArrayList时直接赋值有以下几种常见方式： 构造器传入集合 ： 或者在Java 9及以上版本中使用 List.of() 方法创建不可变列表： 使用匿名内部类 （不常用且可能引起混淆，实际编程中很少这样用）： 注意：这种方式利用了匿名内部类的实例初始化块，但不是标准

    2024年04月22日
    浏览(41)
  • 在两道多线程基础题“顺序打印”中对比一下Java中的wait()和join()

    在两道多线程基础题“顺序打印”中对比一下Java中的wait()和join()

    目录 一、基础 二、进阶 有三个线程，线程名称分别为：a，b，c，每个线程打印自己的名称。 需要让他们同时启动，并按 c，b，a的顺序打印。 这道题要求打印 cba，且只打印一次。如何保证线程 cba 的执行顺序？容易想到，只需要让这三个线程按一定顺序串行执行即可，采用

    2024年02月04日
    浏览(36)
  • Java ArrayList

    Java ArrayList

    ArrayList类示一个可以动态修改的数组，与普通数组的区别是它没有固定大小的限制，可以添加和删除元素。 适用情况： 频繁的访问列表中的某一元素 只需要在列表末尾进行添加和删除某些元素 ArrayList 是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。 Collec

    2024年02月09日
    浏览(31)

  • Java ArrayList类详解

    ArrayList 是 Java 中的一个动态数组数据结构，属于 Java 集合框架的一部分（ java.util 包中的类）。它提供了一个基于数组的可变长度列表，允许你在运行时添加、删除和访问元素，而不需要提前指定数组的大小。 简而言之：它是Java函数库中数百个类中的一个，可以将它直接当

    2024年02月09日
    浏览(37)
  • 详解java中ArrayList

    详解java中ArrayList

    目录 前言 一、ArrayList是什么  二、ArrayList使用 1、ArrayList的构造 2 、ArrayList常见操作 3、 ArrayList的遍历 4、 ArrayList的扩容机制 三、来个练习         当你看到这篇文章我觉得很好笑，因为我开始也不懂ArrayList现在轮到你了，嘻嘻嘻，但是没关系我教你，action!!! 通俗点讲A

    2024年01月23日
    浏览(36)
  • 详解Java ArrayList

    详解Java ArrayList

    ArrayList 是List接口的实现类，底层基于数组实现，容量可根据需要动态增加，相当于动态数组。 ArrayList 继承于 AbstractList ，并且还实现了 Cloneable 、 Serializable 、 RandomAccess 接口。 List ：表明是列表数据结构，可以通过下标对元素进行添加删除或查找。 Serializable ：表示可以进

    2024年02月06日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包