Java 集合框架之线性表（List）实现技术笔记

一、核心概念

• 线性表：有序数据结构，支持元素的增删改查、排序、比较等操作，核心实现方式为数组实现和链表实现。
• 泛型（E）：定义线性表存储的数据类型，使用时指定具体类型（如 String、Integer），避免类型转换错误。
• 接口与实现：List 接口定义统一方法规范，ZArrayList 类基于数组实现该接口，遵循“接口定义规范、实现类完成具体逻辑”的设计思路。

二、List 接口核心方法（按功能分类）

1. 基础查询

• size() ：返回元素个数
• isEmpty() ：判断线性表是否为空
• get(int index) ：根据下标获取元素
• contains(E e) ：判断元素是否存在
• indexOf(E e) / lastIndexOf(E e) ：获取元素首次/末次出现下标（不存在返回 -1）

2. 元素添加

• 单个添加： add(E e) （尾部添加）、 insert(int index, E e) （指定下标插入）
• 批量添加： addAll(E[] es) / addAll(List list) （尾部合并）、 insertAll(int index, E[] es) / insertAll(int index, List list) （指定下标批量插入）

3. 元素删除

• 单个删除： remove(int index) （按下标删除，返回被删元素）
• 批量删除： removeByElement(E e) （按元素删除，返回删除数量）、 removeRange(int fromIndex, int toIndex) （按区间删除）、 removeByList(List list) （按集合删除）

4. 元素替换与排序

• 替换： replace(int index, E e) （按下标替换）、 replaceByElement(E e1, E e2) （按元素替换）、 replaceAll(List list) （按集合替换）
• 比较： equals(List list) （判断两个集合是否相同）

5. 其他功能

• clear() ：清空线性表，恢复初始容量
• subList(int fromIndex) / subList(int fromIndex, int toIndex) ：截取元素（切片）
• toArray() ：将线性表转为新数组返回

三、ZArrayList 实现关键细节

1. 核心属性

privateintsize;// 实际元素个数privateintlength;// 数组容量privateObject[]values;// 存储元素的数组privatestaticfinalintDEFAULT_CAPACITY=10;// 默认初始容量

2. 构造方法

• 无参构造：默认初始化容量为 10， values = new Object[DEFAULT_CAPACITY]
• 有参构造：指定初始容量（若≤2则使用默认值10）

3. 扩容机制（核心亮点）

• 触发条件：当实际元素个数 size == 数组容量 length 时触发扩容
• 扩容规则：新容量 = 旧容量 + 旧容量右移1位（即 newLength = oldLength + (oldLength >> 1) ，等价于1.5倍扩容）
• 实现逻辑：创建新数组 → 迁移旧数组元素 → 替换引用并更新容量

4. 关键方法实现要点

• add(E e) ：先检查是否需要扩容，再通过 values[size++] = e 尾部添加（size++ 先赋值后自增）
• insert(int index, E e) ：先校验下标合法性（0≤index≤size），扩容后迁移index后的元素，空出位置插入新元素
• get(int index) ：校验下标合法性（0≤index<size），通过 (E) values[index] 强转返回元素（泛型适配）

四、注意事项与易错点

1. 下标合法性：所有涉及下标的操作（get、insert、remove等）需校验 index ≥ 0 且 index ≤ size （插入时允许index=size，即尾部插入）
2. size与length区别：size是实际元素个数，length是数组容量，扩容只更新length，不改变当前size
3. 泛型强转：Object数组存储元素后，通过 (E) 强转为泛型类型，需确保使用时类型一致
4. size++与++size： add(E e) 中使用 values[size++] = e ，先将元素存入size位置，再让size自增（若用++size会跳过0下标）

五、总结

ZArrayList 基于数组实现线性表，核心优势是随机访问效率高（通过下标直接获取元素），扩容机制采用1.5倍增长平衡空间利用率与性能。需重点掌握接口方法规范、扩容逻辑、下标校验三大核心点，后续可补充未实现方法（如 contains、removeByElement），并对比链表实现的差异（如插入效率、空间占用）。