[数据结构] ArrayList 与 顺序表

一.线性表

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

线性表在逻辑上是 线性结构 (一条直线) ; 但是在物理结构上并不一定是连续的 , 线性表在物理上存储时 , 通常以数组和链式结构的形式存储

二.顺序表

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

1.模拟实现

①接口的实现

public interface IList /*<E>*/{// 新增元素,默认在数组最后新增public void add(int data);boolean isFull();// 在 pos 位置新增元素public void add(int pos, int data) ;// 判定是否包含某个元素public boolean contains(int toFind);// 查找某个元素对应的位置public int indexOf(int toFind);// 获取 pos 位置的元素public int get(int pos);// 给 pos 位置的元素设为 valuepublic void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove);// 获取顺序表长度public int size() ;// 清空顺序表public void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() ;
}

②功能实现

import java.util.Arrays;public class MyArrayList implements IList {public int[] array;public int usedSize;public int DEFAULT_CAPACITY = 10;public MyArrayList() {this.array = new int[DEFAULT_CAPACITY];}public void grow(){this.array = Arrays.copyOf(this.array,array.length*2);//扩容}public boolean isFull() {return this.usedSize == array.length;//判满}// 新增元素,默认在数组最后新增@Overridepublic void add(int data)  {if(isFull()){//判满,满了就扩容grow();}this.array[usedSize] = data;usedSize++;}public void Checkpos1 (int pos)throws posException{//判断下标是否在(0,pos)位置if(pos<0||pos>usedSize){throw new posException("下标异常");}}// 在 pos 位置新增元素@Overridepublic void add(int pos, int data) {try {if (isFull()) {//判满,满了就扩容grow();}Checkpos1(data);//①(0,pos)位置添加元素 , 需要挪开该下标的元素 , 再添加;②pos位置 , 同add(int data) , 在末尾插入for (int i = this.usedSize-1; i >= pos ; i--) {array[i+1] = array[i];}array[pos] = data;usedSize++;}catch (posException e){System.out.println("下标不合法");e.printStackTrace();}}// 判定是否包含某个元素@Overridepublic boolean contains(int toFind) {for (int i = 0; i < this.usedSize; i++) {//遍历this.array[i] = toFind;return true;//找到返回true}return false;}// 查找某个元素对应的位置@Overridepublic int indexOf(int toFind) {for (int i = 0; i < this.usedSize; i++) {//遍历this.array[i] = toFind;return i;//找到返回下标}return -1;}public void Checkpos2 (int pos)throws posException{if(pos<0||pos>=usedSize){throw new posException("下标异常");//和Checkpos1不同的是 , 查找的范围是(0,usedSize)并不包含usedSize}}public void isEpty()throws emptyException{//判断是否为空if(this.array.length == 0){throw new emptyException();}}// 获取 pos 位置的元素@Overridepublic int get(int pos) {try {Checkpos2(pos);//判断下标是否合法 ,和Checkpos1不同的是 , 查找的范围是(0,usedSize-1]并不包含usedSizeisEpty();//判断是否为空return array[pos];}catch (posException e) {System.out.println("下标不合法");e.printStackTrace();} catch (emptyException e) {System.out.println("数组为空数组");e.printStackTrace();}return -1;}// 给 pos 位置的元素设为 value ; 思路和get(int pos)类似@Overridepublic void set(int pos, int value) {try {Checkpos2(pos);//判断下标是否合法 ,和Checkpos1不同的是 , 查找的范围是(0,usedSize-1]并不包含usedSizeisEpty();//判断是否为空array[pos] = value;}catch (posException e) {System.out.println("下标不合法");e.printStackTrace();} catch (emptyException e) {System.out.println("数组为空数组");e.printStackTrace();}}//删除第一次出现的关键字key@Overridepublic void remove(int toRemove) {try{isEpty();//判断是否为空int pos = indexOf(toRemove);//用indexOf(int toFind)(在上面)来查找if(pos == -1) {//该情况是没有找到return;}for (int i = pos; i < this.usedSize; i++) {//补齐空缺的位置array[i] = array[i+1];}usedSize--;//下方代码思路一样
//            for(int pos = 0; pos < this.usedSize; pos++){//从0下标开始找toRemove
//                if(array[pos] == toRemove){
//                    for (int i = pos; i < this.usedSize; i++) {
//                        array[i] = array[i+1];
//                    }
//                }
//            }
//            usedSize--;}catch (emptyException e){System.out.println("数组为空");e.printStackTrace();}}// 获取顺序表长度@Overridepublic int size() {try {isEpty();return this.usedSize;//有效长度}catch (emptyException e){System.out.println("数组为空");e.printStackTrace();}return 0;}// 清空顺序表@Overridepublic void clear() {/* for (int i = 0; i < usedSize; i++) {array[i] = null;//将所有元素置为null}*/usedSize = 0;//将usedSize设置成0,下一次默认新增元素 则在0下标}// 打印顺序表@Overridepublic void display() {for (int i = 0; i < this.usedSize; i++) {System.out.print(array[i] + " ");}}
}

③异常

public class emptyException extends Exception{public emptyException() {}public emptyException(String message) {super(message);}
}

public class posException extends Exception {public posException() {}public posException(String message) {super(message);}
}

三.ArrayList简介

说明：

• ArrayList 是以泛型方式实现的，使用时必须要先实例化
• Arraylist 实现了Randomaccess接口，表明ArrayList支持随机访问
• ArrayList 实现了Cloneable接口，表明ArrayList是可以被clone的
• ArrayList 实现了Serializable接口，表明ArrayList是支持序列化的
• 和Vector不同，ArrayList 不是现成安全的，在单线程下可以使用，在多线程中 可以使用 Vector 或者 CopyOnWriteArrayList
• ArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

四.ArrayList使用

1.ArrayList 构造

代码演示 :

public static void main(String[] args) {//无参构造 构造一个空的列表List<Integer> list1 = new ArrayList<>();list1.add(1);list1.add(3);//构造一个具有10个容量的列表List<Integer> list2 = new ArrayList<>(10);list2.add(5);list2.add(6);//List3 中的内容与list2一致List<Integer> list3 = new ArrayList<>(list2);//list4类型未指定 任意元素都可存放List list4 = new ArrayList<>();list4.add("123");list4.add(123);}

2.ArrayList 常见操作

    public static void main(String[] args) {List<String> list = new ArrayList<>();//尾插元素list.add("JavaSE");list.add("JavaWeb");list.add("JavaEE");list.add("JVM");list.add("Test");System.out.println(list);//[JavaSE, JavaWeb, JavaEE, JVM, Test]//在 list 的 index 位置插入指定元素 , index 及后续元素向后移动一个位置list.add(1,"JJava");System.out.println(list);//[JavaSE, JJava, JavaWeb, JavaEE, JVM, Test]//获取 list 中有效元素的个数System.out.println(list.size());//6//获取和设置 index 位置上的元素 ; index 介于[0,size)System.out.println(list.get(1));//JJavalist.set(1,"abc");System.out.println(list.get(1));//abc//在 list 的 index 位置插入指定元素 , index 及后续元素向后移动一个位置list.add(1,"JJava");System.out.println(list);//[JavaSE, JJava, abc, JavaWeb, JavaEE, JVM, Test]//删除指定元素,找到就删除,并将该元素之后的元素统一向前移动一个位置list.remove("JVM");System.out.println(list);//[JavaSE, JJava, abc, JavaWeb, JavaEE, Test]//删除 list 中 index 位置的元素list.remove(list.size()-1);System.out.println(list);//[JavaSE, JJava, abc, JavaWeb, JavaEE]//检测 list 中是否包含指定元素 , 包含返回true , 否则返回falseif(!list.contains("Test")){list.add("Test");}//查找指定元素第一次出现的位置 ; indexOf从前往后找 , lastIndexOf从后往前找System.out.println(list.indexOf("Test"));//5System.out.println(list.lastIndexOf("Test"));//5//使用list 中[0,3)之间的元素构成一个新的 SubList 返回//但是 和 ArrayList 共用一个 elementData 数组;即不会产生新的对象,在原数组上直接截取List<String> ret = list.subList(0,3);System.out.println(ret);//[JavaSE, JJava, abc]}

3.ArrayList 的打印 (遍历)

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);//使用下标 + for遍历for(int i = 0;i<list.size();i++){System.out.println(list.get(i));}//for each遍历for (Integer integer:list) {System.out.println(integer+" ");}System.out.println(list);//使用迭代器输出Iterator<Integer> it = list.iterator();while (it.hasNext()){System.out.println(it.next()+" ");}}

• 使用下标+for遍历

        for(int i = 0;i<list.size();i++){System.out.println(list.get(i));}

• 借助foreach遍历

        for (Integer integer:list) {System.out.println(integer+" ");}

• 使用迭代器输出

        Iterator<Integer> it = list.iterator();while (it.hasNext()){System.out.println(it.next()+" ");}

五.ArrayList的扩容机制

• ArrayList 是基于动态数组实现的集合类，其核心特点是支持自动扩容以容纳更多元素。扩容机制的设计平衡了内存使用和性能效率，避免频繁申请内存空间带来的开销
  

1.初始容量与扩容触发条件

默认初始容量为 10（无参构造时）。当调用 add() 方法添加元素且当前容量不足时触发扩容。扩容条件通过 ensureCapacityInternal() 方法检测，最终调用 grow() 方法执行扩容操作

2.扩容具体步骤

• 扩容时，新容量计算遵循公式：newCapacity = oldCapacity + (oldCapacity >> 1)
• 即新容量为旧容量的 1.5 倍（位运算右移一位等效于除以 2）;例如原容量为 10，扩容后为 15
• 若计算的新容量仍小于最小需求容量（如一次性添加大量元素），则直接采用需求容量作为新容量。新容量超过 MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）时，会校验是否溢出并可能抛出 OutOfMemoryError

3.说明:

•  检测是否真正需要扩容 ，如果是调用 grow 准备扩容
•  预估需要库容的大小初步预估按照 1.5 倍大小扩容如果用户所需大小超过预估 1.5 倍大小 ， 则按照用户所需大小扩容真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
• 使用 copyOf 进行扩容

完