【Java】顺序表ArrayList

news/2024/5/20 9:06:52 标签: java, ArrayList, 顺序表

文章目录

一、顺序表

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

顺序表具有以下特点：

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

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

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

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

ArrayList__19">二、ArrayList 的简介

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

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__50">三、ArrayList 的使用

3.1 构造方法

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

  1. ArrayList()：创建一个空的ArrayList对象。
java">ArrayList<String> list = new ArrayList<>();
  1. ArrayList(int initialCapacity)：创建一个具有指定初始容量的ArrayList对象。
java">ArrayList<Integer> list = new ArrayList<>(10);
  1. ArrayList(Collection<? extends E> c)：创建一个包含指定集合元素的ArrayList对象。
java">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)：在指定位置插入一个元素。
java">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)：获取指定位置的元素。
java">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)：删除第一个匹配的元素。
java">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)：替换指定位置的元素。
java">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()：判断列表是否为空。
java">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循环遍历：
java">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循环）遍历：
java">ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("orange");

for (String fruit : list) {
    System.out.println(fruit);
}
  1. 使用迭代器（Iterator）遍历：
java">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的扩容过程：

java">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__233">四、ArrayList 的模拟实现

java">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__361">五、ArrayList 的使用案例

5.1 扑克牌案例

java">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 行的杨辉三角：

java">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 方法生成杨辉三角。然后，我们逐行打印杨辉三角的结果。

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

java">[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]

ArrayList__529">六、ArrayList 存在的问题

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

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

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

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

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


http://www.niftyadmin.cn/n/1010077.html

相关文章

Selenium--做任何你想做的事情

Selenium--做任何你想做的事情

大家好&#xff0c;今天为大家介绍Selenium自动化浏览器。就是这样&#xff01;你可以通过这种力量做任何你想做的事情。 “getDevTools() 方法返回新的 Chrome DevTools 对象&#xff0c;允许您使用 send() 方法发送针对 CDP 的内置 Selenium 命令。这些命令是包装方法&#x…
阅读更多...
CopyOnWriteArrayList源码阅读-- java bug 6260652

CopyOnWriteArrayList源码阅读-- java bug 6260652

文章目录 背景如何查看jdk bugbug原因是谁的问题拓展 背景 在看CopyOnWriteArrayList源码时发现里边有一段注释&#xff0c;说明有bug并进行了修改&#xff0c;6260652是bugid public CopyOnWriteArrayList(Collection<? extends E> c) {Object[] elements;if (c.getC…
阅读更多...
＜Oracle＞《（史上最完整）Linux 下安装Oracle数据库 - Oracle 19C By CentOS 8 》

＜Oracle＞《（史上最完整）Linux 下安装Oracle数据库 - Oracle 19C By CentOS 8 》

《Linux 下安装Oracle数据库 - Oracle 19C By CentOS 8 》 1 说明1.1 前言1.2 资源下载 2 安装步骤2.1 上传安装包2.2 下载数据库预安装包2.3 安装数据库预安装包2.4 安装Oracle数据库2.4.1 第一次安装报错2.4.2 解决安装报错第一步&#xff1a;安装libnsl.so.1第二步&#xff…
阅读更多...
day 34 贪心算法

day 34 贪心算法

1005.K次取反后最大化的数组和 第一步&#xff1a;将数组按照绝对值大小从大到小排序&#xff0c;注意要按照绝对值的大小 第二步&#xff1a;从前向后遍历&#xff0c;遇到负数将其变为正数&#xff0c;同时K– 第三步&#xff1a;如果K还大于0&#xff0c;那么反复转变数值最…
阅读更多...
清华青年AI自强作业hw5：基于CNN实现CIFAR10分类任务

清华青年AI自强作业hw5：基于CNN实现CIFAR10分类任务

清华青年AI自强作业hw5&#xff1a;基于CNN实现CIFAR10分类任务 简述作业实现遇到的问题相关链接 一起学AI系列博客&#xff1a;目录索引 简述 hw5作业为利用深度卷积神经网络实现CIFAR_10数据集十分类问题&#xff0c;帮助理解CNN的前向传播结构。 CIFAR-10是一个常用的彩色图…
阅读更多...
Spring Boot 整合视图层技术 Thymeleaf

Spring Boot 整合视图层技术 Thymeleaf

大家好&#xff01;我是今越。简单记录一下在 Spring Boot 框架中如何整合 Thymeleaf 及使用。 Thymeleaf 简介 Thymeleaf 是新一代 Java 模板引擎&#xff0c;它类似于 Velocity、FreeMarker 等传统 Java 模板引擎&#xff0c;但是与传统 Java 模板引擎不同的是&#xff0c;T…
阅读更多...
CSE RPC流程分析

CSE RPC流程分析

1 使用方法 1.1 Provider 使用示例如下&#xff1a; RpcSchema(schemaId "hello") //RpcSchema public class HelloImpl implements Hello {Overridepublic String sayHi(String name) {return "Hello " name;}Overridepublic String sayHello(Person…
阅读更多...
密码找回安全总结-业务安全测试实操(29)

密码找回安全总结-业务安全测试实操(29)

密码重置凭证与用户账户关联不严 有些信息系统在密码找回功能的校验逻辑上存在缺陷，只校验了密码重置凭证是否在 数据库中存在，但未严格校验该重置凭证和用户账号之间的绑定关系。这种密码重置凭证 与用户账户关联不严的逻辑漏洞就让攻击者可以通过在数据包中修改用户账号达…
阅读更多...
最新文章

Copyright @ 2022~2023