ArrayList与顺序表

ArrayList与顺序表

List

什么是List

在 Java 中，List 是集合框架（java.util 包）中的一个接口，它继承自 Collection 接口，用于存储有序、可重复的元素集合

List 的核心特点：
1.有序性：元素有明确的位置（索引），可以通过索引访问（类似数组）
2.可重复性：允许存储重复的元素（可以有多个相同的值）
3.动态大小：与数组不同，List 的大小可以动态增长或收缩

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型的元素的有限序列，在该序列上可以执行增删改查以及变量操作

常见方法介绍

List的使用

注意⚠️：List是一个接口，不可以实例化

如果要使用需要一个类来实现该接口，在集合框架中，ArrayList和LinkedList都实现了List接口

线性表

线性表是n个具有相同特性的元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表，链表，栈，队列等等。

线性表逻辑上是线性结构，也就是说是连续的一条直线，但是在物理意义上并不一定是连续的，线性表在物理意义上储存的时候，通常以数组和链式结构的形式储存

顺序表

顺序表是一段用物理地址连续的储存单元依次存储数据元素的线性结构，一般情况下采用数组储存。在数组上完成对数据的增删改查

接口相关方法

/**
 * 线性表接口，定义线性表的基本操作
 */
public interface LinearList<T> {
    /**
     * 判断线性表是否为空
     * @return 空返回true，否则返回false
     */
    boolean isEmpty();
    
    /**
     * 获取线性表长度
     * @return 线性表中元素的个数
     */
    int size();
    
    /**
     * 获取指定索引的元素
     * @param index 索引位置
     * @return 该位置的元素
     * @throws IndexOutOfBoundsException 索引越界时抛出
     */
    T get(int index);
    
    /**
     * 在指定位置插入元素
     * @param index 插入位置
     * @param element 要插入的元素
     * @throws IndexOutOfBoundsException 索引越界时抛出
     */
    void add(int index, T element);
    
    /**
     * 在表尾插入元素
     * @param element 要插入的元素
     */
    default void add(T element) {
        add(size(), element);
    }
    
    /**
     * 删除指定位置的元素
     * @param index 要删除元素的位置
     * @return 被删除的元素
     * @throws IndexOutOfBoundsException 索引越界时抛出
     */
    T remove(int index);
    
    /**
     * 查找元素首次出现的位置
     * @param element 要查找的元素
     * @return 元素首次出现的索引，不存在则返回-1
     */
    int indexOf(T element);
    
    /**
     * 清空线性表
     */
    void clear();
} 

ArrayList简介

说明：
1.ArrayList是以泛型方式实现的，使用时必须要先实例化
2.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3.ArrayList实现了Cloneable接口，表明ArrayList是可以克隆的
4.ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5.和Vector不同，ArrayList不是线程安全的，单线程的情况下可以使用，但是在多线程中可以选择Vector或者CopyOnWriteArrayList
6.ArrayList底层是一段连续的空间，可以动态扩容，是一个动态类型的顺序表

ArrayList使用

ArrayList构造

有以下三种构造方法：

//无参构造
ArrayList()

//指定初始容量
ArrayList(int initialCapacity)

//利用其他集合构造
ArrayList(Collection<? extends E> c)

具体构造事例：

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

public class ArrayListConstructorDemo {
    public static void main(String[] args) {
        // 1. 无参构造方法
        System.out.println("=== 无参构造方法示例 ===");
        List<String> fruits = new ArrayList<>();
        System.out.println("初始大小: " + fruits.size()); // 0
        // 添加元素会触发自动扩容
        fruits.add("苹果");
        fruits.add("香蕉");
        fruits.add("橙子");
        System.out.println("添加元素后: " + fruits);
        
        // 2. 指定初始容量的构造方法
        System.out.println("\n=== 指定初始容量的构造方法示例 ===");
        // 已知大概需要存储10个元素，指定初始容量避免频繁扩容
        List<Integer> numbers = new ArrayList<>(10);
        for (int i = 1; i <= 10; i++) {
            numbers.add(i);
        }
        System.out.println("存储的数字: " + numbers);
        System.out.println("当前大小: " + numbers.size());
        
        // 3. 基于已有集合的构造方法
        System.out.println("\n=== 基于已有集合的构造方法示例 ===");
        // 源集合
        List<String> sourceList = Arrays.asList("张三", "李四", "王五");
        System.out.println("源集合元素: " + sourceList);
        
        // 基于源集合创建新的ArrayList
        List<String> targetList = new ArrayList<>(sourceList);
        // 可以对新集合进行修改，不影响源集合
        targetList.add("赵六");
        System.out.println("新集合添加元素后: " + targetList);
        System.out.println("源集合未受影响: " + sourceList);
    }
}

ArrayList常见操作

以下是 ArrayList 中常用方法的汇总表格，按功能分类展示：

具体事例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

public class ArrayListMethodsDemo {
    public static void main(String[] args) {
        // 创建一个ArrayList实例
        List<String> list = new ArrayList<>();
        
        // ==================== 添加元素方法 ====================
        // 1. 添加元素到末尾
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");
        System.out.println("添加元素后: " + list); // [Apple, Banana, Cherry]
        
        // 2. 在指定索引插入元素
        list.add(1, "Date");
        System.out.println("插入元素后: " + list); // [Apple, Date, Banana, Cherry]
        
        // 3. 添加另一个集合的所有元素到末尾
        Collection<String> other = Arrays.asList("Elderberry", "Fig");
        list.addAll(other);
        System.out.println("添加集合后: " + list); // [Apple, Date, Banana, Cherry, Elderberry, Fig]
        
        // 4. 在指定索引插入另一个集合的所有元素
        Collection<String> more = Arrays.asList("Grape", "Honeydew");
        list.addAll(2, more);
        System.out.println("指定位置插入集合后: " + list); 
        // [Apple, Date, Grape, Honeydew, Banana, Cherry, Elderberry, Fig]
        
        
        // ==================== 删除元素方法 ====================
        // 1. 删除指定索引的元素
        String removed = list.remove(3);
        System.out.println("删除的元素: " + removed + "，结果: " + list); 
        // [Apple, Date, Grape, Banana, Cherry, Elderberry, Fig]
        
        // 2. 删除指定元素
        boolean isRemoved = list.remove("Date");
        System.out.println("是否删除成功: " + isRemoved + "，结果: " + list); 
        // [Apple, Grape, Banana, Cherry, Elderberry, Fig]
        
        // 3. 删除与指定集合的交集元素
        Collection<String> toRemove = Arrays.asList("Banana", "Fig");
        list.removeAll(toRemove);
        System.out.println("删除交集后: " + list); // [Apple, Grape, Cherry, Elderberry]
        
        // 4. 保留与指定集合的交集元素
        Collection<String> toRetain = Arrays.asList("Apple", "Grape", "Mango");
        list.retainAll(toRetain);
        System.out.println("保留交集后: " + list); // [Apple, Grape]
        
        
        // ==================== 修改元素方法 ====================
        // 替换指定索引的元素
        String oldElement = list.set(1, "Guava");
        System.out.println("被替换的元素: " + oldElement + "，结果: " + list); 
        // [Apple, Guava]
        
        
        // ==================== 查询元素方法 ====================
        // 1. 获取指定索引的元素
        String element = list.get(0);
        System.out.println("索引0的元素: " + element); // Apple
        
        // 2. 获取元素数量
        System.out.println("元素数量: " + list.size()); // 2
        
        // 3. 判断是否为空
        System.out.println("是否为空: " + list.isEmpty()); // false
        
        // 4. 判断是否包含指定元素
        System.out.println("是否包含Apple: " + list.contains("Apple")); // true
        
        // 5. 获取元素首次出现的索引
        System.out.println("Apple的索引: " + list.indexOf("Apple")); // 0
        
        // 6. 获取元素最后出现的索引
        list.add("Apple"); // 再添加一个Apple
        System.out.println("最后一个Apple的索引: " + list.lastIndexOf("Apple")); // 2
        
        
        // ==================== 其他常用方法 ====================
        // 1. 转换为Object数组
        Object[] objArray = list.toArray();
        System.out.println("Object数组长度: " + objArray.length); // 3
        
        // 2. 转换为指定类型的数组
        String[] strArray = list.toArray(new String[0]);
        System.out.println("String数组元素: " + Arrays.toString(strArray)); 
        // [Apple, Guava, Apple]
        
        // 3. 获取子列表（视图）
        List<String> subList = list.subList(1, 3);
        System.out.println("子列表: " + subList); // [Guava, Apple]
        
        // 4. 使用迭代器遍历
        System.out.print("迭代器遍历: ");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println(); // Apple Guava Apple
        
        // 5. 清空列表
        list.clear();
        System.out.println("清空后: " + list); // []
    }
}

ArrayList遍历

ArrayList 有多种遍历方式，每种方式适用于不同场景。以下是常见的遍历方法及示例代码：

以下是具体例子：

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

public class ArrayListTraversal {
    public static void main(String[] args) {
        // 创建并初始化ArrayList
        List<String> fruits = new ArrayList<>();
        fruits.add("苹果");
        fruits.add("香蕉");
        fruits.add("橙子");
        fruits.add("葡萄");
        
        System.out.println("=== 1. 普通for循环（索引遍历） ===");
        // 适合需要索引的场景，性能较好
        for (int i = 0; i < fruits.size(); i++) {
            System.out.println(fruits.get(i));
        }
        
        System.out.println("\n=== 2. 增强for循环（foreach） ===");
        // 代码简洁，适合仅遍历元素的场景，无法获取索引
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
        
        System.out.println("\n=== 3. 迭代器（Iterator） ===");
        // 适合需要在遍历中删除元素的场景
        Iterator<String> iterator = fruits.iterator();
        while (iterator.hasNext()) {
            String fruit = iterator.next();
            System.out.println(fruit);
            // 示例：删除"香蕉"
            if ("香蕉".equals(fruit)) {
                iterator.remove();
            }
        }
        System.out.println("删除后列表: " + fruits);
        
        System.out.println("\n=== 4. forEach()方法（Java 8+） ===");
        // 函数式编程风格，代码简洁
        fruits.forEach(fruit -> System.out.println(fruit));
        
        System.out.println("\n=== 5. 列表迭代器（ListIterator） ===");
        // 支持双向遍历和修改元素
        java.util.ListIterator<String> listIterator = fruits.listIterator();
        
        System.out.println("正向遍历:");
        while (listIterator.hasNext()) {
            System.out.println(listIterator.next());
        }
        
        System.out.println("反向遍历:");
        while (listIterator.hasPrevious()) {
            System.out.println(listIterator.previous());
        }
    }
}
    

ArrayList扩容机制

ArrayList 的扩容机制是其重要特性之一，它能够根据元素数量的动态变化自动调整内部数组的容量，避免了固定数组长度的限制。以下是其扩容机制的详细说明：

1.核心原理
ArrayList 内部通过一个动态数组（elementData）存储元素，当添加元素导致数组容量不足时，会创建一个更大的新数组，并将原数组元素复制到新数组中，这个过程称为 “扩容”

2.扩容触发时机
当调用 add() 等方法添加元素时，会先检查当前容量是否足够：
如果容量足够（size < elementData.length），直接添加元素
如果容量不足，触发扩容流程

3.扩容具体步骤

计算新容量：
无参构造初始化的列表，首次扩容时容量直接变为 10
非首次扩容时，新容量 = 旧容量 + 旧容量 / 2（即扩容 1.5 倍）

边界处理：
如果计算的新容量小于最小需求容量（需要容纳当前所有元素 + 新添加元素），则直接使用最小需求容量
如果新容量超过 Integer.MAX_VALUE - 8（数组最大理论容量），则使用 Integer.MAX_VALUE

数组复制：
通过 Arrays.copyOf() 方法创建新数组并复制原数组元素
原数组引用指向新数组，完成扩容

private void grow(int minCapacity) {
    // 获取旧容量
    int oldCapacity = elementData.length;
    
    // 计算新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 如果新容量仍小于最小需求，直接使用最小需求
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // 处理超大容量情况
    if (newCapacity - Integer.MAX_VALUE - 8 > 0)
        newCapacity = (minCapacity > Integer.MAX_VALUE - 8) ? 
            Integer.MAX_VALUE : Integer.MAX_VALUE - 8;
    
    // 复制元素到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

总结：
1.检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要扩容的大小
- 初步按照原容量1.5倍大小扩容；
- 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
- 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用copyOf进行扩容