动态数组：数据结构与算法中的线性结构

1.算法： 是用于解决特定问题的一系列的执行步骤。

2.评价算法

如何评判一个算法的好坏，一般从以下维度进行评估算法的优劣：1.正确性、可读性、健壮性（对不合理的反应的解决能力）。2.时间复杂度：估算程序指令的执行次数（执行时间）。3.空间复杂度： 估算所需占用的存储空间。注：每日的数据结构与算法采用JAVA来进行实现与讲解。

3.时间复杂度

估算程序指令的执行次数：如：1.for(int i=0;i<n ; i++)       int  i =0  ；    执行一次    i< n ;              执行 n次    i++ ;               执行 n 次总的执行次数为 2n + 1    2. for(int i=0;i<n ; i++) {        for (int j = 0; j < n; j++) {            System.out.println("test");        }    }    总的执行次数为 3n^2+3n +1    3.  while((n=n/2)>0){       System.out.println("test");  }分析： 8 /2           4    4/ 2           2    2 / 2          1总的执行次数为 log2(n)。

4.大O表示法

大O表示法来描述复杂度  它表示是数据规模n对应的复杂度,仅仅只是一种粗略的分析模型。注：忽略常数、系数、低阶。9  >>  O(1)2n+3  >> O(n)n*n +2n+ 5  O(n*n)4n*n*n +3n*n + 22n +100  >> O(n*n*n)

5.数据结构

数据结构是计算机存储、组织数据的方式包括：线性结构：线性表 （数组、链表、栈、哈希表）          树形结构：二叉树、AVL树、红黑树、B树、堆、Tree、哈夫曼树          图形结构：邻接矩阵、邻接表          我们先从线性结构说起。          

6.线性表：具有n个相同类型元素的有限序列。（n>=0）

线性表图例

如上图所示：a1是首节点 ，an 是尾结点，a1是a2的前驱 ， a2是a1的后继。日常中有很多线性表的例子： 比如冰糖葫芦，排成一列的乒乓球等等。

7.数组

数组：是一种顺序存储的线性表，所有元素的内存地址是连续的。int[] array=new int[]{11,22,33}；  定义一个含有11 22 33 的数组。

数组栈堆内存空间图

数组存在一个致命的缺点：无法动态修改容量，而我们在实际开发中希望容量可以动态改变，所以                                         进行动态数组的创建，实现数据可以动态修改容量。

8.动态数组创建

创建一个动态数组实现的是可以向数组中进行增删改查，并且当增加值时数组内存地址可以保证够用，当数组内存地址不够用时，可以随时进行添加，所以一个动态数组需要包含：  1.指向堆空间一数组地址  2.数组的长度

动态数组包含属性

9.实现常用功能

动态数组基本常用功能（参考jdk源码 ArrayList源码） 这里数组中存储就以整数来进行举例。    int size(); //元素的数量    boolean isEmpty(); //是否为空    boolean contains(int element); // 是否包含某个元素    void add(int  element);  // 添加元素到最后面    int  get(int index); // 返回index位置对应的元素    int set(int index,int element); // 设置index位置添加元素    void add(int index,int element); // 往index位置添加元素    int remove(int index); // 删除index位置对应的元素    int indexOf(int element); //查看元素的位置    void clear(); // 清除所有的元素

10.动态数组初始化

public class DynamicArray implements PublicInterface {  publicInterface 是实现功能方法接口    /**     * 元素的数量     */    private int size;    /**     * 所有的元素     */    private int[] elements;//    数组默认长度  这里设置默认长度为10 可自行调整    private static final  int NOT_DATA_FIND =10 ; // 定义 传值的构造方法 如果传入的值大于 默认值 采用创建传入值的数组长度    public DynamicArray (int capacity){        capacity = (capacity < DEFAULT_CAPACITY ) ? DEFAULT_CAPACITY: capacity;        elements = new int[capacity];    }   // 默认创建为10 的数组    public DynamicArray (){        this(DEFAULT_CAPACITY);    }

11.元素数量、 是否为空等功能实现

    /**     *  元素的数量     */    @Override    public int size() {        return size;    // 直接返回size显示数组长度    }// 如果size 为 0  代表动态数组为空   /**     * 是否为空     * @return     */    @Override    public boolean isEmpty() {        return size == 0;    }/**     * 查看元素所在的位置     * @param element     * @return     */    @Override    public int indexOf(int element) {        for (int i=0 ; i < size ;i++){            if (elements[i] == element ) return i;        }        return NOT_DATA_FIND;  //  静态常量为-1    } /**     * 是否包含某个元素     * @param element     * @return     */    @Override    public boolean contains(int element) {        return indexOf(element) == NOT_DATA_FIND;  //  静态常量为-1    } /**     * 清除所有的元素     */    @Override    public void clear() {        size = 0 ; // 重复利用内存空间    }注： 这里情况数组直接设置size为0 即可：DynamicArray array = new DynamicArray();array.add(11); // add实现方法下面会进行讲解   当调用添加方法是 size ++ ，如果将size设置为0 调用获取数据或其他方法就不可以实现，从程序外部来看数据已经被清空了，因为这里数组存储的是整数，如果存储的是对象，需要遍历数组将每个对象设置为null，再设置size为0 ，防止内存一直占用。

12.元素位置 、元素添加等功能实现

 /**     * 返回index位置对应的元素     * @param index     * @return     */    @Override    public int get(int index) {        if(index < 0 || index >= size){          //   不符合条件抛出异常            throw  new IndexOutOfBoundsException("Index:" + index + " " +   "Size" + size);        }        return elements[index];    }    /**     * 设置index位置元素     * @param index     * @param element     * @return     */    @Override    public int set(int index, int element) {        if(index < 0 || index >= size){            throw  new IndexOutOfBoundsException("Index:" + index + " " +   "Size" + size);        }      // 获取以前位置元素        int old = elements[index];        elements[index] = element;        return old;    }  /**     * 往index位置添加元素     * @param index     * @param element     */    @Override    public void add(int index, int element) {    //  这里如果是在size位置上添加，所以可以包含size        if(index < 0 || index >  size){            throw  new IndexOutOfBoundsException("Index:" + index + " " +   "Size" + size);        }        for (int i = size - 1 ; i >= index ; i--){            elements[i + 1] =  elements[i];        }        elements[index] = element ;        size ++ ;    }  /**     * 添加元素到最后面     * @param element     */    @Override    public void add(int element) {       add(size , element);    }

插入元素原则按照size进行

错误添加覆盖顺序（从后往前）

13.动态数组元素删除实现

  /**     * 删除index位置对应的元素     * @param index     * @return     */    @Override    public int remove(int index) {        if(index < 0 || index >= size){            throw  new IndexOutOfBoundsException("Index:" + index + " " +   "Size" + size);        }        int old = elements[index];        for (int i = index + 1 ; i <= size -1 ; i++ ) {            elements[i - 1] = elements[i];        }        size -- ;        return old;    }

删除元素前移元素

14.扩容

当向动态数组中进行添加元素时，需要进行判断数组内存地址是否够用，不够用需要进行扩容。 // 不够用时新创建一个新的数组，是原有的1.5倍，再将数据元素迁移到新的数组地址。 private void Ensurecapacity(int capacity){        int oldCapacity = elements.length;        if(oldCapacity >= capacity) return;//        新容量为旧容量的1.5倍        int newCapacity = oldCapacity + (oldCapacity >> 1);        int[] newElements = new int[newCapacity];        for (int i = 0 ; i < size ; i++){            newElements[i] = elements[i];        }        elements = newElements;        System.out.println("扩容"+elements.length);    }在添加元素时调用检查。