02_动态数组

什么是数据结构？

数据结构是计算机存储、组织数据的方式

Snip20200914_5.png

数组

数组是一种顺序存储的线性表，所有元素的内存地址是连续的

数组的接口设计

int size(){} // 元素的数量
boolean isEmpty(){} // 是否为空
void add(E element){} // 添加元素到最后面
void set(int index,E element){} // 设置index位置的元素
void add(int index,E element){} // 在index位置插入一个元素
void remove(int index){} // 删除index位置的元素
boolean contains(E element){} // 是否包含某个元素
E get(int index){} // 获取index位置的元素
int indexOf(E element){} // 查看元素的索引
void clear(){} // 清除所有元素

动态数组的缩容

如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作
比如剩余空间占总容量一半时，就进行缩容
如果扩容倍数、缩容时机设计不得当，有可能会导致复杂度震荡
比如，扩容倍数设置为原来容量的2倍，而缩容时机设置为当元素个数小于等于原容量1/2时
注意点：扩容倍数和缩容时机不要相乘等于1

代码实现

普通的动态数组

package ListArray;

public class LZArrayList <E>{

    /**
     * 元素的数量
     */
    private  int size;

    /**
     * 所有的元素
     */
    private  E[] elements;

    /**
     * 数组的初始容量
     */
    private  static final int DEFAULT_CAPACITY = 10;

    /**
     * 元素找不到
     */
    private  static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 构造函数
     */
    public LZArrayList(int capaticy){
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY:capaticy;
        elements = (E[]) new Object[capaticy];
    }

    /**
     * 构造函数
     */
    public LZArrayList(){
        this(DEFAULT_CAPACITY);
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        for (int i = 0;i<size;i++){
            elements[i] = null;
        }
        size = 0;
    }

    /**
     * 元素的数量
     * @return
     */
    public int size(){
        return size;
    }

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


    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        rangeCheck(index);
        return elements[index];
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     */
    public void set(int index,E element){
        rangeCheck(index);
        elements[index] = element;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index,E element){
        if (index<0 || index>size) {
            outOfBounds(index);
        }

        //扩容
        ensureCapacity();

        //插入数据
        for (int i = size;i>index;i--){
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }

    /**
     * 删除index位置的元素
     * @param index
     */
    public void remove(int index){
        rangeCheck(index);
        for (int i = index+1;i<size;i++){
            elements[i-1] = elements[i];
        }
        elements[--size] = null;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        if (element == null){
            for (int i = 0;i<size;i++){
                if (elements[i] == null) return i;
            }
        }
        for (int i = 0;i<size;i++){
            if (element.equals(elements[i])) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 动态扩容
     * 当数组的容量小于size + 1 时，扩容到原来容量的 1.5 倍
     */
    private void ensureCapacity(){
        int oldCapacity = elements.length;
        if (elements.length >= size + 1) return;
        int newCapacity = oldCapacity + (oldCapacity>>1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0;i<size;i++){
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

    /**
     * 检查下标越界
     * @param index
     * @return
     */
    private void rangeCheck(int index){
        if (index<0 || index >= size){
            outOfBounds(index);
        }
    }
    /**
     * 检查到下标越界，抛出异常
     * @param index
     * @return
     */
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("size = ").append(size).append("\n[");
        for (int i = 0;i<size;i++){
            if (i != 0){
                string.append(", ");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
}

环形动态数组 - 自动缩容

package ListArray;

public class LZCircleArrayList <E>{

    /**
     * 元素的数量
     */
    private  int size;

    /**
     * 所有的元素
     */
    private  E[] elements;

    /**
     * 第一个元素的下标
     */
    private int front;

    private  static final int DEFAULT_CAPACITY = 10;
    private  static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 构造函数
     */
    public LZCircleArrayList(int capaticy){
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY:capaticy;
        elements = (E[]) new Object[capaticy];
    }

    /**
     * 构造函数
     */
    public LZCircleArrayList(){
        this(DEFAULT_CAPACITY);
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        for (int i = 0;i<size;i++){
            elements[realIndex(i)] = null;
        }
        front = 0;
        size = 0;
        shrinkageCapacity();
    }

    /**
     * 元素的数量
     * @return
     */
    public int size(){
        return size;
    }

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


    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        rangeCheck(index);
        return elements[realIndex(index)];
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     */
    public void set(int index,E element){
        rangeCheck(index);
        elements[realIndex(index)] = element;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index,E element){
        if (index<0 || index>size) {
            outOfBounds(index);
        }

        //扩容
        ensureCapacity();

        //插入数据
        if (index>=(size>>1)){ //插入位置更接近数组尾部
            for (int i = size;i>index;i--){
                elements[realIndex(i)] = elements[realIndex(i - 1)];
            }
            elements[realIndex(index)] = element;
        }else { //插入位置更接近数组头部
            for (int i = -1;i<index;i++){
                elements[realIndex(i)] = elements[realIndex(i + 1)];
            }
            elements[realIndex(index)] = element;
            front = realIndex(-1);
        }
        size++;
    }

    /**
     * 删除index位置的元素
     * @param index
     */
    public void remove(int index){
        rangeCheck(index);

        //删除数据
        if (index>=(size>>1)){ //删除位置更接近数组尾部
            for (int i = index+1;i<size;i++){
                elements[realIndex(i-1)] = elements[realIndex(i)];
            }
            elements[realIndex(size-1)] = null;
        }else { //删除位置更接近数组头部
            for (int i = index;i>0;i--){
                elements[realIndex(i)] = elements[realIndex(i - 1)];
            }
            elements[realIndex(0)] = null;
            front = realIndex(1);
        }
        size--;
        //缩容
        shrinkageCapacity();
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        if (element == null){
            for (int i = 0;i<size;i++){
                if (elements[realIndex(i)] == null) return i;
            }
        }
        for (int i = 0;i<size;i++){
            if (element.equals(elements[realIndex(i)])) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 根据index求出真实索引
     * @param index
     * @return
     */
    private int realIndex(int index){
        index += front;
        if (index<0){
            return index + elements.length;
        }
        return index - (index>= elements.length?elements.length:0);
//        return (front + index) % elements.length;
    }

    /**
     * 动态扩容
     */
    private void ensureCapacity(){
        int oldCapacity = elements.length;
        //不需要扩容
        if (elements.length >= size + 1) return;
        int newCapacity = oldCapacity + (oldCapacity>>1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0;i<size;i++){
            newElements[i] = elements[realIndex(i)];
        }
        elements = newElements;
        front = 0;
    }

    /**
     * 动态缩容
     * 当元素个数小于数组容量的一半，并且大于默认初始容量时，进行缩容
     * 如果数组中没有元素或者数组容量小于初始容量的2倍，缩容为初始容量，否则缩容为容量的1/2
     */
    private void shrinkageCapacity(){
        int oldCapacity = elements.length;

        //不需要缩容
        if (size>=(oldCapacity>>1) || oldCapacity<=DEFAULT_CAPACITY) return;

        int newCapacity = (oldCapacity < DEFAULT_CAPACITY + DEFAULT_CAPACITY || size == 0)?DEFAULT_CAPACITY:(oldCapacity>>1);

        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0;i<size;i++){
            newElements[i] = elements[realIndex(i)];
        }
        elements = newElements;
        front = 0;
    }

    /**
     * 检查下标越界
     * @param index
     * @return
     */
    private void rangeCheck(int index){
        if (index<0 || index >= size){
            outOfBounds(index);
        }
    }
    /**
     * 检查到下标越界，抛出异常
     * @param index
     * @return
     */
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("front = ").append(front).append("\n");
        string.append("size = ").append(size).append("\n[");
        for (int i = 0;i<elements.length;i++){
            if (i != 0){
                string.append(", ");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }

}

时间复杂度分析

添加
最好：O(1) 最坏：O(n) 平均：O(n)
添加元素到结尾
最好：O(1) 最坏：O(1) 平均：O(1) 均摊：O(1)
删除
最好：O(1) 最坏：O(n) 平均：O(n)
设置index位置的值
最好：O(1) 最坏：O(1) 平均：O(1)
获取inde位置的值
最好：O(1) 最坏：O(1) 平均：O(1)