一、数组是什么？
数组是一种顺序存储的线性表，所有元素的内存地址是连续的
int[] array = new int[]{11,22,33}
数组的缺点就是无法修改其容量，但是在实际开发过程中往往需要动态修改容量的。
二、对象数组
Object[] objects = new Object[7];
在这里我引入了对象数组，是因为这里会设计到一些内存管理上的细节问题。
在清除所有元素的时候，代码如下：
public void clear() { for (int i = 0; i < size; i++) { elements[i] = null; } size = 0; }
在这里我们要知道，如果Objects指向的地址丢失了，那么数组和对象谁先消失呢？
因为对象是依赖于地址的，所以一定是对象最后才被清除消失。因为JVM的垃圾回收机制一般不会马上进行清除，那么此时就会造成大量空间的浪费，而且再次放元素还要进行频繁的空间创建，这样就会开销很大。所以我们在进行元素清除的时候只需要进行把地址的位置置为null即可。
同样，我们在删除元素的时候也是这样置为null，如下：
public E remove(int index) { rangeCheck(index); E old = elements[index]; for (int i = index + 1; i < size; i++) { elements[i - 1] = elements[i]; } elements[--size] = null; return old; }
三、动态数组的设计
1.泛型
使用泛型技术可以让动态数组更加通用，可以存放任何数据类型。
另外一个重要的点是任何类的父类，我们都可以认为是Object的子类。
还提供了有参和无参两个构造方法！！！
public class ArrayList { private int size; private E[] elements; private static final int DEFAULT_CAPACITY = 10; //设置初始数组的容量为10 private static final int ELEMENT_NOT_FOUND = -1; //把查找不到的时候返回值统一设为默认值 public ArrayList(int capaticy) { capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy; elements = (E[]) new Object[capaticy]; } public ArrayList() { this(DEFAULT_CAPACITY); } }
2.清除所有元素
public void clear() { for (int i = 0; i < size; i++) { elements[i] = null; } size = 0; }
3.元素的数量
public int size() { return size; }
4.判断是否为空
public boolean isEmpty() { return size == 0; }
5.是否包含某个元素
public boolean contains(E element) { return indexOf(element) != ELEMENT_NOT_FOUND; }
6.添加元素到尾部
public void add(E element) { add(size, element); }
7.获取index位置的元素
public E get(int index) { rangeCheck(index); return elements[index]; }
8.设置index位置的元素
public E set(int index, E element) { rangeCheck(index); E old = elements[index]; elements[index] = element; return old; }
9.在index位置插入一个元素
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacity(size + 1); for (int i = size; i > index; i--) { elements[i] = elements[i - 1]; } elements[index] = element; size++; }
10.删除index位置的元素
public E remove(int index) { rangeCheck(index); E old = elements[index]; for (int i = index + 1; i < size; i++) { elements[i - 1] = elements[i]; } elements[--size] = null; return old; }
11.查看元素的索引
public int indexOf(E element) { if (element == null) { for (int i = 0; i < size; i++) { if (elements[i] == null) return i; } } else { for (int i = 0; i < size; i++) { if (element.equals(elements[i])) return i; // n } } return ELEMENT_NOT_FOUND; }
12.保证要有capacity的容量
private void ensureCapacity(int capacity) { int oldCapacity = elements.length; if (oldCapacity >= capacity) return; // 新容量为旧容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } elements = newElements; }
13.溢出抛异常
private void outOfBounds(int index) { throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); }
14.一般索引检查
private void rangeCheck(int index) { if (index < 0 || index >= size) { outOfBounds(index); } }
15.添加元素时索引检查（在尾部可以添加，所以可以等于Size）
private void rangeCheckForAdd(int index) { if (index < 0 || index > size) { outOfBounds(index); } }
16.打印
public String toString() { StringBuilder string = new StringBuilder(); string.append("size=").append(size).append(", ["); for (int i = 0; i < size; i++) { if (i != 0) { string.append(", "); } string.append(elements[i]); } string.append("]"); return string.toString();
四、动态数组复杂度分析
数组的随机访问是非常快的，因为可以直接根据下标索引计算出地址的偏移量，访问很快，而且访问效率与数组元素的个数无关。
动态数组
最好 |
最坏 |
平均 |
|
add(intindex,Eelement) |
O(1) |
O(n) |
O(n) |
最好
最坏
平均
add(intindex,Eelement)
O(1)
O(n)
O(n)
remove(intindex)
O(1)
O(n)
O(n)
set(intindex,Eelement)
O(1) O(1) O(1)
get(intindex)
O(1) O(1) O(1)
