数据结构---自定义动态数组

package cn.dragon.arithmetic.model;

import java.util.Arrays;
import java.util.NoSuchElementException;

//自定义动态数组
public class MyArrayList<T> {

    //底层存储的数组
    private T[] data;
    //记录的当前元素个数
    private int size;
    //默认初始容量
    private static final int INIT_CAP = 1;

    public MyArrayList() {
        this(INIT_CAP);
    }

    public MyArrayList(int initCapacity) {
        data = (T[]) new Object[initCapacity];
        size = 0;
    }

    public void addList(T d) {
        int cap = data.length;
        //检查数组容量
        if (size == cap) {
            resize(2 * cap);
        }
        //在尾部插入
        data[size] = d;
        size++;
    }

    public void add(int index, T d) {
        //检查索引越界
        checkPositionIndex(index);

        int cap = data.length;
        //检查data数组容量，需要时进行扩容
        if (size == cap) {
            resize(2 * cap);
        }

        //挪数据
        for (int i = size - 1; i >= index ; i--) {
            data[i + 1] = data[i];
        }
        //插入新元素
        data[index] = d;
        size++;
    }

    public void addFirst(T d) {
        add(0, d);
    }

    //删除最后一个
    public T removeLast() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
        int cap = data.length;
        //缩容
        if (size == cap / 4) {
            resize(cap / 2);
        }
        T deleteVal = data[size - 1];
        //删除最后一个元素
        data[size - 1] = null;
        size--;
        return deleteVal;
    }

    public T remove(int index) {
        //检查索引越界
        checkElementIndex(index);

        int cap = data.length;
        //缩容
        if (size == cap / 4) {
            resize(cap / 2);
        }
        T deleteVal = data[index];
        //把后面的数据往前挪
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        data[size - 1] = null;//去除最后一位
        size--;
        return deleteVal;
    }

    public T removeFirst() {
        return remove(0);
    }

    //获取数据
    public T get(int index) {
        checkElementIndex(index);
        return data[index];
    }

    //修改数据
    public T set(int index, T element) {
        //检测数组越界
        checkElementIndex(index);
        //修改数据
        T oldVal = data[index];
        data[index] = element;
        return oldVal;//返回旧数据
    }


    //存储的数组大小
    public int size() {
        return size;
    }

    //数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //数组扩容
    private void resize(int newCap) {
        T[] temp = (T[]) new Object[newCap];
        for (int i = 0; i < size; i++) {
            temp[i] = data[i];
        }
        data = temp;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException("index out of bounds, index: " + index);
        }
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index)) {
            throw new IndexOutOfBoundsException("index out of bounds, index: " + index);
        }
    }

    //检查索引位置是否可以存在元素
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    //检查索引位置是否可以添加元素
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private void display() {
        System.out.println("size = " + size + " cap = " + data.length);
        System.out.println(Arrays.toString(data));
    }

}

原文地址：https://blog.csdn.net/Dragonlongbo/article/details/143494232

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！