数据结构与算法 - 数组的实现

1. 数组
   线性有序的数据结构，所以是一块连续的内存空间

2. 数组的结构：如图
   

3. 代码实现

package dataStructure;
public class MyArray<E> {
    private final static int DEFAULT_LENGTH = 10;
    private E[] data;
    private int length;
    private int index = 0;

    public MyArray(int length) {
        this.data = (E[]) new Object[length];
        this.length = length;
    }
    public MyArray() {
        this.data = (E[]) new Object[DEFAULT_LENGTH];
        this.length = DEFAULT_LENGTH;
    }

    //获取元素
    public E getE(int location) {
        return data[location];
    }

    //插入元素
    public void insert(E e) {
        if (index < length) {
            data[index] = e;
            index ++;
        } else {
            expandLength();
            insert(e);
        }
    }

    //插入元素
    public void insert(int location, E e) {
        //入参校验
        validateIndex(location);

        //是否需要扩容校验
        if (index < length) {
            //后移
            for (int i = length -1 ; i > location ; i--) {
                data[i] = data[i-1];
            }
            index ++;
            data[location] = e;
        } else {//扩容
            expandLength();
            insert(location,e);
        }
    }

    //删除元素
    public void delete(int location, E t) {
        validateIndex(location);
        for (int i = location; i < length -1 ; i++) {
            if (i != length -1 ) {
                data[i] = data[i+1];
            } else {
                data[i] = null;
            }
        }
        index --;
    }

    //更新元素
    public void update(int location, E e) {
        validateIndex(location);
        data[location] = e;
    }

    //获取数组长度
    public int size() {
       return index;
    }

    //扩容
    private void expandLength() {
        length = length*2;
        E[] newArray = (E[]) new Object[length];
        for (int i = 0; i < data.length; i++) {
            newArray[i] = data[i];
        }
        data = newArray;
    }

    //入参下标校验
    private void validateIndex(int location){
        if (location < 0 || location > index) {
            throw new IllegalArgumentException("不合法参数");
        }
    }

    public static void main(String[] args) throws InterruptedException {
        MyArray<Integer> array = new MyArray(3);
        array.insert(0,20);
        array.insert(1,18);
        array.insert(2,42);
        array.insert(1,58);
        array.update(1,76);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array.getE(i));
        }
        System.out.println(array.size());

        //java.lang.IllegalArgumentException: 不合法参数
        //由于下标超过了数据长度,如果这种情况是允许的话，数据的内存地址就不连续的，且会出现null,造成已开辟的空间资源浪费
        array.update(6,76);
    }
}

数据结构与算法 - 数组的实现

原文：https://www.cnblogs.com/zjd-world/p/14645049.html