模拟ArrayList（顺序表）的底层实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了模拟ArrayList（顺序表）的底层实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

模拟ArrayLIst的底层实现

package com.tedu.api04.list;

import java.util.Objects;

/**
 * @author LIGENSEN
 * Date: 2023/7/20 11:35
 */
public class ArrayListDemo {
    public static void main(String[] args) {
        ArrList<String> list=new ArrList<>(1);
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("f");
        list.add("c");

//        list.add(0,"d");
//        list.clear();
//        list.add(4,"e");
//        list.add(2,"f");
//        list.add(4,"e");
        System.out.println(list.indexOf("d"));
        System.out.println(list.contains("c"));
        System.out.println(list.get(2));
        System.out.println(list.isEmpty());
        System.out.println(list.lastIndexOf("c"));
        list.remove(3);
        list.remove("a");
        list.set(1,"cc");
        System.out.println(list.subList(0, 1));
        list.toArray();

        System.out.println(list);
    }
}

/**
 * 用数组来实现 ArrList
 * 集合里面可以用 Object[] 存任意的数据
 *
 * @param <E>
 */
//模拟:用数组来实现ArrayList
class ArrList<E>{
    //数组
    private Object[] arr;
    //数组元素个数
    private int size;
    //初始容量
    private int initialCapacity;

    public ArrList(){
        arr=new Object[10];
    }
    //指定容量
    public ArrList(int initialCapacity){
        // 初始容量必须 > 0
        if(initialCapacity < 0){
            throw  new IllegalArgumentException("非法参数异常");
        }
        this.initialCapacity=initialCapacity;
        arr=new Object[this.initialCapacity];
    }


    //添加元素
    public void add(E e){
        //判断是否需要扩容
        if(size == arr.length)grow();
        //向第size位置上添加元素
        arr[size++]=e;
    }

    //在指定的位置插入指定的元素
    public void add(int index,E e){
        //判断下标是否越界
        if(index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index:" + index +",Size" + size);
        //判断是否需要扩容
        if(size == arr.length) grow();
        //移动元素
        /*for (int i = size-1; i >= index ; i--) {
            arr[i+1]=arr[i];
        }*/
        System.arraycopy(arr,index,arr,index+1,size-index);
        arr[index]=e;
        size++;
    }

    //清空集合
    public void clear(){
        //清空每一个元素对应的引用
        for (int i = 0; i < size; i++) {
            arr[i]=null;
        }
        //重构数组
        arr=new Object[initialCapacity];
        //元素个数归零
        size=0;
    }

    //获取指定元素第一次出现的下标
    public int indexOf(E e){
        //遍历集合
        for (int i = 0; i < size; i++) {
            /**
             * 第一个 == 判断引用类型是够相等
             * arr[i].equals(e) 只能引用类型调用，判断的是值相等（重写Object 中的 equals之后）
             */
            //if(arr[i] == e || arr[i] != null && arr[i].equals(e))
            if(Objects.equals(arr[i],e))
                return i;
        }
        //如果整个循环结束,都没有return,说明没找到
        return -1;
    }
    //判断是否包含指定元素
    public boolean contains(E e){
        return indexOf(e) >= 0;
    }

    //判断越界
    private void outBounds(int index){
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index:"+index+",Size"+size);
    }

    //获取指定位置上的元素
    public E get(int index){
        //判断越界
        outBounds(index);
        //获取指定的元素
        return (E)arr[index];

    }

    //判断集合是否为空
    public boolean isEmpty(){
        return size<=0;
    }

    //获取指定元素最后一次出现的下标
    public int lastIndexOf(E e){
        for (int i = size-1; i >= 0 ; i--) {
            if (Objects.equals(arr[i],e))return i;
        }
        return  -1;
    }

    //删除指定下标上的元素
    public void remove(int index){
        //判断越界
        outBounds(index);
        //后边的元素覆盖前面的元素
        /*for (int i = index+1; i < size; i++) {
            arr[i-1]=arr[i];
        }*/
        System.arraycopy(arr,index+1,arr,index,size-(index+1));
        size--;
    }

    //删除指定元素
    public void remove(E e){
        //获取第一次出现的位置
        int index = indexOf(e);
        //判断是否存在
        if(index >= 0)remove(index);
    }

    //替换指定位置上的元素
    public void set(int index,E e){
        //越界
        outBounds(index);
        //替换
        arr[index]=e;
    }

    //获取元素个数
    public int size(){
        return  size;
    }

    //截取子列表
    public ArrList<E> subList(int fromIndex,int toIndex){
        //判断下标范围
        if(fromIndex < 0 || toIndex > size || fromIndex > toIndex)
            throw new IllegalArgumentException();
        //截取字列表
        ArrList<E> sub=new ArrList<>();
        for (int i = fromIndex; i < toIndex; i++) {
            sub.add((E)arr[i]);
        }
        return sub;
    }

    //转为数组
    public Object[] toArray(){
        //新建数组
        Object[] newArray=new Object[size];
        //赋值元素
        System.arraycopy(arr,0,newArray,0,size);
        return newArray;
    }

    //扩容
    private void grow(){
        //计算新数组的容量
        int capacity=size;
        if(size < 2)
            capacity +=1;
        else
            capacity=size + (size >> 1);
        //构建新的数组
        Object[] arr=new Object[capacity];
        //将原来数组中的元素赋值到新的数组中
        System.arraycopy(this.arr,0,arr,0,size);
        this.arr=arr;
    }

    //转为字符传
    @Override
    public String toString() {
        //判断集合是否为空
        if(size <= 0) return "[]";
        //拼接元素
        StringBuilder sb=new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            sb.append(arr[i]).append(", ");
        }
        //转为字符串
        String str = sb.toString();
        //去掉尾部的", "
        str=str.substring(0,str.length()-2);
        //返回
        return str += "]";
    }
}