第四章动态数组

什么是数据结构？
线性表
数组（Array）
动态数组（Dynamic Array）

什么是数据结构？

数据结构是计算机存储、组织数据的方式。
数据结构：考虑如何去组织计算机中一定量的数据。
数据结构连接时空，用空间换时间。
数据处理：了解问题，，明确数据操作方法，设计出更加高效的数据结构类型

找到需要处理的数据，计算结果，再把结果保存下来
- 把结果存到新的内存空间中
- 把结果存到已使用的内存空间中
基本操作只要三个：增、删、查
- 增和删可以细分为数据结构的中间以及最后的增和删
- 查找可以细分为按照位置条件查找和数据数值特征查找
- 所以数据的处理都是这些操作的组合或叠加
只有字典类型数据结构能在O(1) 时间复杂度内完成查找
回归问题本源，明确数据被处理动作，来解决数据结构的问题

哈希表是使用单链表实现的。

线性表

线性表是具有n个 相同类型（或者相同特性）元素的有限序列（n >= 0）。

除了首位元素外，其它数据元素都是首位相接的
- 这句话只适用大多数线性表，而不是全部，比如循环链表的尾指针指向头节点
一般线性表，可以自由的删除和添加结点。
受限线性表：受限线性表最简单直白的理解就是在操作线性表的时候，会有一定程度的限制，不能随心所欲的进行操作。栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。
a是首节点（首元素）、a是尾节点（尾元素）
a1是a2的前驱，a2是a1的后继

数组（Array）

数组是一种顺序存储的线性表，所有元素的内存地址是连续的（也就是采用一段连续的存储单元存储数据的）。

动态数组（Dynamic Array）

Jdk 中的 ArrayList就是动态数组啊。

接口设计

int size();//返回元素的数量
boolean isEmpty();//返回容器是否为空
boolean contains(E element);//返回是否包含指定元素
void add(E element);//在容器尾部添加元素
void add(int index,E element);//在指定位置添加元素
E set(int index,E element);//在指定位置设置元素，返回原来的元素
E get(int index);//查找指定位置的元素
E remove(int index);//删除指定位置的元素
int indexOf(E element); //返回指定元素的第一次索引位置
void clear();//清空容器内所有元素

成员变量设计

int size;

Object [] elements;

泛型

public class DynamicArray<E> {
  /**
   * 容器存放所有元素
   */
  private Object[] elements;
}

对象数组

查询

//查找指定位置的元素O(1)
public E get(int index) {
      rangCheck(index);
      return (E) elements[index];
}

增加

```java private void enlarge(int minCapacity) {

  //容器当前实际容量
  int oldCapacity = elements.length;
  if (oldCapacity <= minCapacity) {
      //扩容 2倍
      Object[] newElements = new Object[(oldCapacity << 1)];
      for (int i = 0; i < size; i++) {
          newElements[i] = elements[i];
      }
      elements = newElements;
      System.out.println("扩容了，新容量：" + elements.length);
  }

}

//在容器尾部添加元素 O(1) public void add(E element) { enlarge(size + 1); elements[size++] = element; } /**

 * 在指定位置添加元素，此位置及后面所有元素位置向后面移动一个
 * 最好O(1)，最后一个位置添加
 * 最坏O(n)，第一个元素位置添加
 * 平均O(n)
 * @param index
 * @param element
 */

public void add(int index, E element) { rangCheckForAdd(index); if (index == size) { add(element); } else { enlarge(size + 1); for (int i = size - 1; i >= index; i—) { elements[i + 1] = elements[i]; } elements[index] = element; size++; } }

<a name="RMxiO"></a>
### 删除
```java
/**
     * 删除指定位置的元素
     * 最好O(1)，删除最后一个元素
     * 最坏O(n)，删除第一个元素
     * 平均O(n)
     * @param index
     * @return
     */
public E remove(int index) {
        rangCheck(index);
        E old = (E) elements[index];
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        elements[--size] = null;
        return old;
}

设置

// 在指定位置设置元素，覆盖原来的元素，返回原来的元素O(1)
public E set(int index, E element) {
        rangCheck(index);
        E old = (E) elements[index];
        elements[index] = element;
        return old;
}

内存管理细节

  void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

E remove(int index) {
        rangCheck(index);
        E old = (E) elements[index];
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        elements[--size] = null;
        return old;
    }

第四章 动态数组