目录一、引言二、List接口三、顺序表四、总结一、引言顺序表是我们数据结构的一种底层是以数组来实现的并结合动态扩容机制以支持灵活的数据操作是线性表的一种线性表顾名思义就是一条直线一样是连续的但要注意在逻辑上是连续的但是在物理结构上不一定是连续的。顺序表物理连续链表物理不连续。二、List接口那么在讲顺序表之前我们我们先介绍一下ListList是一个接口继承自CollectionCollection也是一个接口该接口中规范了后序容器中常用的一些方法如下所示List官方文档 这里也提供了官方文档可以点击查看。List是一个接口不能直接实例化如果要使用必须去实例化List的实现类。在集合框架中ArrayList和LinkedList都实现了List接口。ArrayList就是我们要讲的顺序表。三、顺序表Array List是一个泛型类使用前必须实例化底层是一段连续的空间并且支持动态扩容而且ArrayList实现了Cloneable接口表明ArrayList是可以clone的。它的里面也是有许多方法方法功能说明常用场景boolean add(E e)在列表尾部添加单个元素普通添加元素void add(int index, E element)在指定索引位置插入元素后续元素后移指定位置插入元素boolean addAll(Collection? extends E c)添加另一个集合的所有元素到尾部批量添加元素boolean addAll(int index, Collection? extends E c)在指定索引插入另一个集合的所有元素批量插入到指定位置E get(int index)获取指定索引位置的元素随机访问元素ArrayList 优势E set(int index, E element)替换指定索引位置的元素返回被替换的旧元素修改指定位置的元素E remove(int index)删除指定索引的元素返回被删除的元素后续元素前移删除指定位置的元素boolean remove(Object o)删除第一个匹配的指定元素成功返回 true删除指定值的元素void clear()清空列表中所有元素重置集合int size()返回列表中元素的个数判断元素数量、循环遍历boolean isEmpty()判断列表是否为空size0空值校验boolean contains(Object o)判断列表是否包含指定元素元素存在性校验int indexOf(Object o)返回第一个匹配元素的索引不存在返回 -1查找元素位置int lastIndexOf(Object o)返回最后一个匹配元素的索引不存在返回 -1查找重复元素的最后位置ListE subList(int fromIndex, int toIndex)返回从 fromIndex包含到 toIndex不包含的子列表截取部分列表注意子列表关联原列表Object[] toArray()将列表转换为 Object 类型数组数组转换T T[] toArray(T[] a)将列表转换为指定类型的数组类型安全的数组转换IteratorE iterator()返回迭代器用于遍历列表遍历元素通用方式在使用这些方法之前我们先来模拟实现一下常见的方法import java.util.Arrays; public class SeqList { private int[] array; private int size; // 默认构造方法初始化容量为10 SeqList() { this.array new int[10]; this.size 0; } // 将顺序表的底层容量设置为initcapacity SeqList(int initcapacity) { if (initcapacity 0) { throw new IllegalArgumentException(初始化容量不能为负数: initcapacity); } this.array new int[initcapacity]; this.size 0; } // 新增元素,默认在数组最后新增 public void add(int data) { // 扩容检查使用Arrays.copyOf实现1.5倍扩容 if (size array.length) { int newCapacity (int) (array.length * 1.5); array Arrays.copyOf(array, newCapacity); // 一步完成数组扩容数据复制 } array[size] data; size; } // 在 pos 位置新增元素 public void add(int pos, int data) { // 校验pos合法性 if (pos 0 || pos size) { throw new IndexOutOfBoundsException(插入位置非法: pos); } // 扩容检查 if (size array.length) { int newCapacity (int) (array.length * 1.5); array Arrays.copyOf(array, newCapacity); } // 元素后移 for (int i size; i pos; i--) { array[i] array[i - 1]; } array[pos] data; size; } // 判定是否包含某个元素 public boolean contains(int toFind) { for (int i 0; i size; i) { if (array[i] toFind) { return true; } } return false; } // 查找某个元素对应的位置 public int indexOf(int toFind) { for (int i 0; i size; i) { if (array[i] toFind) { return i; } } return -1; } // 获取 pos 位置的元素 public int get(int pos) { if (pos 0 || pos size) { throw new IndexOutOfBoundsException(索引越界: pos); } return array[pos]; } // 给 pos 位置的元素设为 value public void set(int pos, int value) { if (pos 0 || pos size) { throw new IndexOutOfBoundsException(索引越界: pos); } array[pos] value; } // 删除第一次出现的关键字key public void remove(int toRemove) { int index indexOf(toRemove); if (index -1) { return; // 元素不存在直接返回 } // 元素前移 for (int i index; i size - 1; i) { array[i] array[i 1]; } size--; } // 获取顺序表长度 public int size() { return this.size; } // 清空顺序表 public void clear() { this.size 0; // 仅重置有效元素个数数组空间保留 } }在实际的实现当中并不是int类型的而是泛型类在实现过程中我们一定要注意避免数组越界插入位置pos的合法性这里我们去可以自定义一个异常去处理pos是否合法这里因为不好展现就没有去自定义一个异常了。下面来演示一下Array List要怎么去使用import java.util.ArrayList; public class ArrayListExample { public static void main(String[] args) { // 创建ArrayList ArrayListString fruits new ArrayList(); // 添加元素 fruits.add(Apple); fruits.add(Banana); fruits.add(Orange); // 访问元素 System.out.println(First fruit: fruits.get(0)); // 修改元素 fruits.set(1, Mango); // 删除元素 fruits.remove(Orange); // 遍历元素 for (String fruit : fruits) { System.out.println(fruit); } } }值得注意的是我们在使用add的时候并没有分配内存但还是可以添加这是因为在我们调用的时候里面就初始化好了一个内存空间。我们如果要指定空间的话可以这样子ArrayListString fruits new ArrayList(20);注意事项1、ArrayList允许存储null值。2、动态扩容特性使其适合频繁增删的场景但随机访问效率高于链表LinkedList。3、初始容量可通过构造函数调整如new ArrayList(20)以减少扩容开销。4、增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。5、ArrayList底层使用连续的空间任意位置插入或删除元素时需要将该位置后序元素整体往前或者往后搬 移故时间复杂度为O(N)四、总结和LinkedList相比Array List随机访问是更快的但是插入 / 删除慢指定位置插入 / 删除需要移动元素时间复杂度 O (n)所以在这方面Array List是不如Linked List的因此顺序表适用于需要频繁随机访问的场景例如数值计算、数据缓存等。但其插入和删除效率较低若需高频增删操作建议使用链表结构。