模擬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 += "]";
    }
}

運行結果如下：