[数据结构] ArrayList 与顺序表-EW帮帮网

一.线性表

线性表是 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 位置的元素设为 value
    public void set(int pos, int value);
    //删除第一次出现的关键字key
    public 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;//判满
    }

    // 新增元素,默认在数组最后新增
    @Override
    public 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 位置新增元素
    @Override
    public 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();
        }
    }

    // 判定是否包含某个元素
    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {//遍历
            this.array[i] = toFind;
            return true;//找到返回true
        }
        return false;
    }

    // 查找某个元素对应的位置
    @Override
    public 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 位置的元素
    @Override
    public int get(int pos) {
        try {
            Checkpos2(pos);//判断下标是否合法 ,和Checkpos1不同的是 , 查找的范围是(0,usedSize-1]并不包含usedSize
            isEpty();//判断是否为空
            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)类似
    @Override
    public void set(int pos, int value) {
        try {
            Checkpos2(pos);//判断下标是否合法 ,和Checkpos1不同的是 , 查找的范围是(0,usedSize-1]并不包含usedSize
            isEpty();//判断是否为空
            array[pos] = value;
        }catch (posException e) {
            System.out.println("下标不合法");
            e.printStackTrace();
        } catch (emptyException e) {
            System.out.println("数组为空数组");
            e.printStackTrace();
        }
    }

    //删除第一次出现的关键字key
    @Override
    public 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();
        }
    }

    // 获取顺序表长度
    @Override
    public int size() {
        try {
            isEpty();
            return this.usedSize;//有效长度
        }catch (emptyException e){
            System.out.println("数组为空");
            e.printStackTrace();
        }
        return 0;
    }

    // 清空顺序表
    @Override
    public void clear() {
        /* for (int i = 0; i < usedSize; i++) {
            array[i] = null;//将所有元素置为null
        }*/
        usedSize = 0;//将usedSize设置成0,下一次默认新增元素 则在0下标
    }

    // 打印顺序表
    @Override
    public 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 常见操作

方法	解释
boolean add(E e)	尾插 e
void add(int index , E element)	将 e 插入index 位置
boolean addAll(Collection<? extendsE>c)	尾插 c 中的元素
E remove (int index)	删除 index 位置的元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int indxt)	获取下标 index 位置的元素
E set(int index , E element)	将 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List <E> subList(int fromIndex, int toIndex)	截取部分 list

    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));//JJava
        list.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 , 否则返回false
        if(!list.contains("Test")){
            list.add("Test");
        }

        //查找指定元素第一次出现的位置 ; indexOf从前往后找 , lastIndexOf从后往前找
        System.out.println(list.indexOf("Test"));//5
        System.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 进行扩容

[数据结构] ArrayList 与顺序表

一.线性表

二.顺序表

1.模拟实现

①接口的实现

②功能实现

③异常

三.ArrayList简介

说明：

四.ArrayList使用

1.ArrayList 构造

2.ArrayList 常见操作

3.ArrayList 的打印 (遍历)

五.ArrayList的扩容机制

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

2.扩容具体步骤

`3.说明:`

完

网站公告

今日签到

热门文章

最新发布

[数据结构] ArrayList 与 顺序表

一.线性表

二.顺序表

1.模拟实现

①接口的实现

②功能实现

③异常

三.ArrayList简介

说明：

四.ArrayList使用

1.ArrayList 构造

2.ArrayList 常见操作

3.ArrayList 的打印 (遍历)

五.ArrayList的扩容机制

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

2.扩容具体步骤

3.说明:

完

网站公告

今日签到

热门文章

最新发布

[数据结构] ArrayList 与顺序表

`3.说明:`