算法与数据结构知识汇总（一、概念与数组）

1、数据结构

1、概念

    数据结构是计算机存储、组织数据的方式。
    数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
    通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
    数据结构往往同高效的检索算法和索引技术有关。

    数据结构有两种结构：逻辑结构和存储结构

2、逻辑结构

    集合结构、线性结构、树形结构、图形结构

3、存储结构

    表、堆栈、队列、数组、树、二叉树、图

2、算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，
算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

3、算法的研究课题

一个算法的好坏是通过空间复杂度和时间复杂度来衡量，那么算法的研究课题就是时间复杂度和控件复杂度。

空间复杂度：关键代码的存储空间的使用情况
时间复杂度：关键代码的执行次数

看下代码：

   for(int i = 0; i < n; i++) {
       for(int j = 0; j < n; j ++) {
       // dosomething;
       }   
   }

以上代码是双层for循环，一眼就看出，时间复杂度为O（n^2），因为时间复杂度是计算关键代码的执行次数。
但是，无法看出它的空间复杂度，现在，假设dosomething中有一句代码在堆内存中开辟了一个空间，那么它的空间复杂度就是O（n^2）。

4、数组

一片物理上连续的大小确定的存储空间。如：

int[] a = new int[10];

这里的数组 指一维数组，二维数组不做考虑。

我在网上截了一张一维数组的图片，如图：

图片.png
数据的元素都是有角标的，如图所示，数组的大小是n，元素角标从0开始，a[0]=a₁，a[1]=a₂，a[2]=a₃，a[3]=a₄，a[4]=a₅，a[5]=a₆，a[6]=a₇...等等。

数组元素的操作有四种，分别是：增、删、改、查。

查找： 查询比较简单，假如在一个长度为n的数组里查找数值为m的数，那么只能根据数组的角标顺序查找，它的时间复杂度为n，简称O(n)。
增加、删除： 由于数组的大小不变（物理上连续的存储空间），所以数据无法做到增加和删除操作。
修改： 修改就是更新某角标的数据，直接赋值即可，如：

a[i] = m;

为了解决数组不可增加、删除的问题，引入了顺序表

【顺序表】

顺序表就是我们常用的ArrayList，它是物理上连续、逻辑上连续、大小可以动态增加的数据结构。

ArrayList弥补了数组不能添加和删除元素的缺陷。

有关ArrayList增加和删除元素的代码如下：

    ArrayList<String> list = new ArrayList<>();
    //添加一个元素
    list.add("张三");
    //在角标为0的位置上插入一个元素
    list.add(0, "李四");
    //移除一个元素
    list.remove("张三");
    //在指定位置上移除一个元素
    list.remove(0);

我们来分析一下源码：

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

它的意思是，在顺序表的末尾增添一个新的元素，elementData是一个Object数组

transient Object[] elementData;

将新增的元素赋值到elementData[size++] 中

elementData[size++] = e;

但是，问题来了，elementData的长度是size，那么以上的赋值操作不是数组越界了吗？我们发现，在赋值之前，还有一句代码：

ensureCapacityInternal(size + 1);  // Increments modCount!!

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

最终走到了grow方法中，minCapacity为size+1，核心代码如下：

elementData = Arrays.copyOf(elementData, newCapacity);

它的意思是，使用Arrays.copyOf重新创建一个新的数组，新数组的大小是newCapacity，将原来数组elementData中的所有源码赋值到新的数组中。(重点)

我们再来分析一下以下源码：

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

其核心代码是：

System.arraycopy(elementData, index, elementData, index + 1, size - index);

和上面提到的Arrays.copyOf作用是一样的，它们的却别是：

Arrays.copyOf是新建一个大小为size +1的数组，并将原来的数组的数据复制到新的数组中；
System.arraycopy是新建一个大小为size+1的数组，将原有数组的[0~index]范围中的元素拷贝到新数组的[0~index]位置上，将原有数组剩余的元素全部拷贝到新数组的[index+1~size+1]位置上。

remove方法的源码就不说了，和add一样，使用了Arrays.copyOf和System.arraycopy这两个方法。

所以，我们得出的结论是，顺序表(ArrayList)本质上就是一个数组(int[])，它和数组一样，都是有角标的，所以查找的速度是非常快的，但是，缺点是：速度特别慢。

[完...]