[Java数据结构与算法]ArrayList详解与实际应用

木井巳

发布于 2025-12-16 09:32:02

880

一、ArrayList 简介

ArrayList是Java集合框架中的一个重要类，位于java.util包中。它实现了List接口，底层基于数组实现，可以根据需要动态扩容。

ArrayList的特点：

以泛型方式实现，类型安全
实现了RandomAccess接口，支持快速随机访问
实现了Cloneable接口，支持克隆操作
实现了Serializable接口，支持序列化
非线程安全，多线程环境下需要额外同步
底层使用动态数组，支持自动扩容

二、ArrayList的基本使用

2.1 构造方法

//1. 无参构造，默认初始容量为10
List<Integer> list1 = new ArrayList<>();

//2. 指定初始容量
List<Integer> list2 = new ArrayList<>(20);

//3. 通过其他集合构造
List<Integer> list3 = new ArrayList<>(list2);

2.2 常用方法

ArrayList提供了丰富的方法来操作元素：

方法	描述	时间复杂度
boolean add(E e)	尾插元素	O(1) 平均
void add(int index, E element)	在指定位置插入元素	O(n)
E remove(int index)	删除指定位置元素	O(n)
boolean remove(Object o)	删除首次出现的指定元素	O(n)
E get(int index)	获取指定位置元素	O(1)
E set(int index, E element)	设置指定位置元素	O(1)
int size()	返回元素个数	O(1)
boolean contains(Object obj)	判断是否包含指定元素	O(n)
int indexOf(Object obj)	返回指定元素首次出现的索引	O(n)
void clear()	清空所有元素	O(1)

使用示例：

List<String> list = new ArrayList<>();
list.add("JavaSE");
list.add("JavaWeb");
list.add("JavaEE");

// 获取元素
System.out.println(list.get(1)); // 输出: JavaWeb

// 修改元素
list.set(1, "JavaWEB");
System.out.println(list.get(1)); // 输出: JavaWEB

// 插入元素
list.add(1, "Java数据结构");
System.out.println(list); // 输出: [JavaSE, Java数据结构, JavaWEB, JavaEE]

// 删除元素
list.remove("JavaEE");
System.out.println(list); // 输出: [JavaSE, Java数据结构, JavaWEB]

// 检查包含
if(list.contains("JavaSE")) {
    System.out.println("包含JavaSE");
}

// 清空列表
list.clear();
System.out.println(list.size()); // 输出: 0

2.3 遍历方式

ArrayList支持三种遍历方式，分别是 for循环、foreach循环和迭代器 ：

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

// 1. for循环+下标
for(int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i) + " ");
}
System.out.println();

// 2. foreach循环
for(Integer num : list) {
    System.out.print(num + " ");
}
System.out.println();

// 3. 迭代器
Iterator<Integer> it = list.iterator();
while(it.hasNext()) {
    System.out.print(it.next() + " ");
}
System.out.println();

三、ArrayList的扩容机制

ArrayList的扩容机制是其最重要的特性之一。如果当前数组已满，ArrayList会自动创建一个更大的数组，并将原数组中的元素复制到新的数组中。

3.1 扩容流程源码分析

检查当前数组容量是否足够
如果容量不足，计算新的容量（通常是原容量的1.5倍）
创建新数组并复制元素
更新内部数组引用

// ArrayList扩容核心源码分析
public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 确保内部容量足够
    elementData[size] = e;
    size++;
    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++;
    
    if(minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容
    
    if(newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    if(newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

3.2 扩容性能分析

ArrayList得扩容操作需要创建新数组并复制所有元素，时间复杂度是O(n)。

因此，在已知大致容量的情况下，最好使用带初始容量的构造方法，减少扩容次数。

List<Integer> list = new ArrayList<>(1000);
for (int i = 0; i < 1000; i++) {
    list.add(i);
}

四、ArrayList的实践应用

4.1 杨辉三角

我们可以把杨辉三角看成一个下三角形，第一行只有一个元素1，其余行的第一个和最后一个元素都是1
我们可以用一个二维顺序表（相当于二维数组）来存储，第一行用一个顺序表存入1
然后利用循环填入剩下的元素
最后接入二维顺序表即可

public static List<List<Integer>> generatePascalTriangle(int numRows) {
    List<List<Integer>> list = new ArrayList<>();

    //第一行
    List<Integer> list0 = new ArrayList<>();
    list0.add(1);
    list.add(list0);
    
    for (int i = 0; i < numRows; i++) {
        //每一行第一个元素
        List<Integer> curRow = new ArrayList<>();
        curRow.add(1);
        
        //每一行中间的元素
        List<Integer> preRow = new ArrayList<>();
        for (int j = 1; j < i; j++) {
            int v1 = preRow.get(j);
            int v2 = preRow.get(j-1);
            curRow.add(v1+v2);
        }

        //每一行最后一个元素
        curRow.add(1);
        list.add(curRow);
    }
    return list;
}

4.2 扑克洗牌

首先我们把这个问题分成三个步骤：生成扑克牌、洗牌、发牌
生成扑克牌：我们可以利用循环嵌套来生成52张牌（除去大小王）并存入Poker类中
洗牌：利用随机数生成将顺序表中下标为i的元素改至下标为index（随机生成下标），如此一来就可以实现扑克牌的打乱
发牌：把所有人的手牌视作一个二维数组，则每个人的手牌就是一个一维数组，利用循环嵌套就可以将牌存入每个人的手牌中

class Poker {         //除去两张鬼牌剩余的52张手牌
    private String suit;                            //手牌的花色
    private int rank;                                //手牌的大小

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

    @Override
    public String toString() {
        return "{"+suit+rank+"} ";
    }
}

class PokerPrepare {
    public static final String[] suits = {"♠","♥","♣","♦"};     //四种花色

    //1.扑克牌的生成
    public List<Poker> pokerCards () {
        List<Poker> cardList = new ArrayList<>();
        for (int i = 1; i <= 13; i++) {     //控制牌面
            for (int j = 0; j < 4; j++) {   //控制花色
                int rank = i;
                String suit = suits[j];
                Poker card = new Poker(suit,rank);  //放入牌
                cardList.add(card);
            }
        }
        return cardList;
    }

    //2.洗牌
    public void shuffle (List<Poker> cardList) {
        Random r = new Random();
        for (int i = cardList.size()-1; i > 0; i--) {
            int index = r.nextInt(i);
            swap(cardList,i,index);
        }
    }
    private void swap (List<Poker> cardList,int i, int index) {
        Poker t = cardList.get(i);
        cardList.set(i,cardList.get(index));
        cardList.set(index,t);
    }

    //3.摸牌(三人,每人五张牌)
    public List<List<Poker>> getCards (List<Poker> cardList) {
        List<Poker> hand0 = new ArrayList<>();
        List<Poker> hand1 = new ArrayList<>();
        List<Poker> hand2 = new ArrayList<>();

        List<List<Poker>> hands = new ArrayList<>();

        hands.add(hand0);
        hands.add(hand1);
        hands.add(hand2);

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                Poker card = cardList.remove(0);  //相当于将牌堆最顶上的牌拿取
                hands.get(j).add(card);                  //第j个人手下的卡牌
            }
        }
        return hands;
    }
}

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

public class PokerGame {
    public static void main(String[] args) {
        PokerPrepare pokerPrepare = new PokerPrepare();

        //1.生成一副牌(购买一副牌)
        List<Poker> cardList = pokerPrepare.pokerCards();
        System.out.println(cardList);

        //2.洗牌
        pokerPrepare.shuffle(cardList);
        System.out.println(cardList);

        //3.摸牌
        List<List<Poker>> hands = pokerPrepare.getCards(cardList);
        for (int i = 0; i < cardList.size(); i++) {
            System.out.print("第"+ (i+1) +"个人的手牌："+ hands.get(i));
            System.out.println();
        }
    }
}

完

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-19，如有侵权请联系 cloudcommunity@tencent.com 删除

java