数组实现-(第二篇)

数组的实现

数组是应用最广泛的一种数据结构,常常被植入到编程语言中,作为基本数据类型使用,因此,在一些教材中,数组并没有被当做一种数据结构单独拿出来讲解(其实数组就是一段连续的内存,即使在物理内存中不是连续的,在逻辑上肯定是连续的)。其实没必要在概念上做纠缠,数组可以当做学习数据结构的敲门砖,以此为基础,了解数据结构的基本概念以及构建方法

数据结构不仅是数据的容器,还要提供对数据的操作方法,比如检索、插入、删除、排序等。

数组显然是线性结构,这里我们定义一个相关的List的接口实现。


/**
 * List接口
 *
 * @author : Administrator
 * @create 2018-10-31 20:59
 */
public interface List {

    int getSize();

    boolean isEmpty();

    boolean contains(E e);

    int indexOf(E e);

    E remove(int index);

    void removeElement(E e);

    void addLast(E o);

    void addFirst(E o);

    E get(int index);

    void replace(int i, E e);

    void insert(int index, E o);
}

数组中的成员变量实现,有两个分别为底层的数据结构、数组【】data和数组的容量size。

public class Array implements List {
    private E[] data;
    private int size;

在数组中实现插入操作:

    /**
     * 在index索引的位置插入一个新元素e
     *
     * @param index 索引
     * @param e     新元素e
     */
    @Override
    public void insert(int index, E e) {
        // 判断数组容量是否超出,否则自动扩容
        if (size == data.length) {
            resize(2 * data.length);
        }
        // 越界检测
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException("out of boundary");
        }
        // 将index索引以及之后的所有的元素后移一位,腾出空间
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

在数组中实现删除操作:

     /**
     * 删除元素的值
     * 
     * @param index  索引
     * @return       返回待删除元素的值
     */
    @Override
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
        }
        // 先保存需要删除的元素的值,然后将index索引后说有元素前移一位
        E ret = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null; // 原先最后的元素末尾指针指向null,使得其gc自动回收内存
        // 自动缩容操作
        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }
        return ret;
    }

根据传入的元素E删除元素。

    @Override
    public void removeElement(E e) {
        int index = indexOf(e);
        if (index != -1) {
            remove(index);
        }
    }

数组自动扩容的机制的实现:

    /**
     * 将数组空间的容量变成newCapacity大小
     *
     * @param newCapacity newCapacity
     */
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        // 经过其提供自动扩容的方法的实现
        E[] newData = (E[]) new Object[newCapacity];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[i];
        data = newData;
    }

完整实现见GitHUb

时间复杂度的分析

对于添加操作而言:在数组的尾部添加是是O(1)的时间复杂度、头部添加是O(n)的复杂度、我们计算时间复杂度是最坏的情况下计算的,所以其添加操作动态数组为O(n)的复杂度。

mark

对于删除操作而言:在数组的尾部删除是O(1)的时间复杂度、头部删除是O(n)的复杂度、我们计算时间复杂度是最坏的情况下计算的,所以其删除操作动态数组为O(n)的复杂度。

mark

mark

mark

mark

mark

mark

mark