• 最基础的线性数据结构：数组
• 最基础的动态数据结构：链表
• 操作受限的线性结构：栈和队列

一、静态数组

1. 数组的随机读写性能

数组：用一组连续的内存空间，来存储一组具有相同类型的数据。

int[] data = new int[5]; // 此时，每个元素的默认值是0

内存.png

若将index = 3 的元素的值设置为4：（1）先找到 index = 3 的元素所在的内存地址。此时时间为 O(1)。 （2）将内存地址为1012指向的内存设置为4。此时时间为 O(1)。所以随机修改数组中任意元素的时间复杂度是：O(1)。

• 结论：数组的随机读写性能非常好 (๑•̀ㅂ•́)و✧

2. 随机新增、删除元素

• 新增：需要申请一块新的内存空间，大小是原来数组内存+1

  空间复杂度： O(n)； 时间复杂度： O(n)

• 删除：需要申请一块新的内存空间，大小是原来数组内存 -1

  空间复杂度： O(n)； 时间复杂度： O(n)

• 结论：相对于数组的随机读写，数组的随机删除和新增的性能不是很好。

二、二次封装静态数组

首先可以了解一下Java内置数组的缺点：1. 没有新增元素的方法。 2. 没有删除元素的方法。 3. 没有判空方法。4. 没有获取真实存储元素个数的方法。 5. 没有判断是否存在指定目标值得方法。

package com.douma;

public class ArrayList<E> {
    private E[] data; // 数组data用于存储
    private int capacity; // 容量
    private int size;

    public ArrayList(int capacity) {
        this.data = (E[])new Object[capacity];
        this.capacity = capacity;
        this.size = 0;
    }
    // 再定义无参构造函数
    public ArrayList() {
        // 如果没有传参数，默认长度为15
        this(15);
    }
    // 判断数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    public int getCapacity() {
        return capacity;
    }

    public int getSize() {
        return size;
    }

    /**
     * 新增操作
     * */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add failed, require index>=0 " +
                    "&& index <= size");
        }
        // 扩容
        if (size == data.length) {
            resize(data.length * 2);
        }
        // 移动元素
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        // 注意：要增加size！！
        size++;
    }

    private void resize(int newCapacity) {
        // 1. 创建一个容量为newCapacity 的临时数组
        E[] newData = (E[])new Object[newCapacity];
        // 2. 将原来数组中的元素拷贝到新数组中
        for (int i = 0; i <size; i++) {
            newData[i] = data[i];
        }
        // 3. 将新数组覆盖老数组
        data = newData;
        // 4. 这里一定要注意！！！ 将容量设置为新容量值
        capacity = newCapacity;
    }

    // 时间复杂度 O(n)
    public void addFirst(E e) {
        add(0, e);
    }

    // 时间复杂度 O(1)
    public void addLast(E e) {
        add(size, e);
    }

    /**
     * 查询操作
     * */
    // 时间复杂度 O(1)
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get failed, require index >= 0 && index < size");
        }
        return data[index];
    }

    public E getLast() {
        return get(size - 1);
    }

    public E getFirst() {
        return get(0);
    }

    // 时间复杂度 O(n)
    public boolean contains(E target) {
        for (E num : data) {
            if (target.equals(num)) return true;
        }
        return false;
    }
    //查找数组元素 e 所在的索引，如果不存在的元素 e，则返回 -1
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 修改操作
     * */
    // 时间复杂度 O(1)
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("set failed, require index >= 0 && index < size");
        }
        data[index] = e;
    }

    /**
     * 删除操作
     * 返回删除的元素
     * */
    // 删除指定索引位置的元素
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove failed, require index >= 0 && index < size");
        }
        E res = data[index];
        for (int i = index; i< size; i++) {
            data[i-1] = data[i];
        }
        size--;
        // 注意：清除不用的对象
        data[size] = null;
        // 如果size 等于总容量的一半，则进行缩容
        // // 因为 data.length 有可能不断的减少，所以有可能小于 2 了，所以需要判断下
        if (size == data.length / 2 && data.length / 2 != 0) {
            resize(data.length / 2);
        }
        return res;
    }

    // 时间复杂度 O(n)
    public E removeFirst() {
        return remove(0);
    }

    // 时间复杂度 O(1)
    public E removeLast() {
        return remove(size - 1);
    }

    // 删除指定的元素
    public void removeElement(E e) {
        int index = find(e);
        if (index != -1) {
            remove(index);
        }
    }

    public E[] getData() {
        return data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i != size - 1) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

上面是关于对数组的增删改查。