动态数组是指在声明时没有确定数组大小的数组，即忽略圆括号中的下标；当要用它时，可随时用ReDim语句重新指出数组的大小。使用动态数组的优点是可以根据用户需要，有效利用存储空间。

数据结构

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

数据的逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
线性结构：数据结构中的元素存在一对一的相互关系；
树形结构：数据结构中的元素存在一对多的相互关系；
图形结构：数据结构中的元素存在多对多的相互关系。

线性结构包括：线性表、数组、链表、栈、队列和哈希表。
树形结构包括：二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树和并查集。
图形结构包括：邻接矩阵和邻接表。

常用的数据结构：

动态数组01

线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

动态数组03
a1 是首节点（首元素），an 是为节点（尾元素）。
a1 是 a2 的前驱，a2 是 a1 的后继。

ps：什么是线性表

数组

数组是一种顺序存储的线性表，所有元素的内存地址是连续的。一维数组是最简单的数组，其逻辑结构是线性表。

1	int[] array = new int[]{11, 22, 33};

动态数组04

在很多编程语言中，数组都有个致命的缺点，无法动态修改容量。怎么实现一个容量可以动态修改的数组呢？👇

ps：什么是数组

动态数组

接口设计

public class ArrayList<E> {
	
	/**
	 * 清除所有元素
	 */
	public void clear() {}
	/**
	 * 元素的数量
	 * @return
	 */
	public int size() {}
	/**
	 * 是否为空
	 * @return
	 */
	public boolean isEmpty() {}
	/**
	 * 是否包含某个元素
	 * @param element
	 * @return
	 */
	public boolean contains(E element) {}
	/**
	 * 添加元素到尾部
	 * @param element
	 */
	public void add(E element) {} 
	/**
	 * 获取index位置的元素
	 * @param index
	 * @return
	 */
	public E get(int index) {}
	/**
	 * 设置index位置的元素
	 * @param index
	 * @param element
	 * @return 原来的元素ֵ
	 */
	public E set(int index, E element) {}
	/**
	 * 在index位置插入一个元素
	 * @param index
	 * @param element
	 */
	public void add(int index, E element) {}
	/**
	 * 删除index位置的元素
	 * @param index
	 * @return
	 */
	public E remove(int index) {}
	/**
	 * 查看元素的索引
	 * @param element
	 * @return
	 */
	public int indexOf(E element) {}
}

实现方案

动态数组05

定义 size 记录数组的大小，定义 elements 存储元素。

public class ArrayList<E> {
	/*
	 * 元素的数量
	 */
	private int size;
	
    /*
	 * 所有的元素
	 */
	private E[] elements;
	
    /*
	 * 默认容量
	 */
	private static final int DEFAULT_CAPACITY = 10;
	
    /*
	 * 构造方法
	 */
	public ArrayList(int capacity) {
		capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
		elements = (E[]) new Object[capacity];
	}
	
    /*
	 * 构造方法
	 */
	public ArrayList() {
		this(DEFAULT_CAPACITY);
	}
}

添加元素

动态数组06
添加新元素，就是在 size 处添加新元素，代码实现：

1
2
3

public void add(int element) {
    elements[size++] = element;
}

删除元素

size 等于 7，index 等于 3：
动态数组07
从 index + 1 处开始依次向前移动，最后一个元素不做处理（因为执行了 size--，所以最后一个元素不会被外界访问到）：

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

插入元素

size 等于 5，index 等于 2：
动态数组08
从 size - 1 处开始依次向后移动，最后覆盖 index 处的元素：

public void add(int index, int element) {
	for (int i = size; i > index; i--) {
		elements[i] = elements[i - 1];
	}
	elements[index] = element;
	size++;
}

扩容

动态数组09
创建新的数组，新数组的容量为旧数组容量的1.5倍（iOS 1.6倍, java 1.5倍）。

private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;
    
    int newCapacity = oldCapacity + (oldCapacity >> 1); // >> 表示除以2
    int[] newElements = new int[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
}

缩容

如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作。比如剩余空间占总容量的一半时，就进行缩容。

private void trim() {
    int oldCapacity = elements.length;
    int newCapacity = oldCapacity >> 1;
    // 剩余空间小于一半 || 空间大小 <= 默认空间
    if (size >= newCapacity || oldCapacity <= DEFAULT_CAPACITY) return;
    
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
}

如果扩容倍数、缩容时机设计不得当，有可能会导致复杂度震荡。比如缩容时机改为 size > newCapacity，此时容量等于数组的一半时，新增加元素需要扩容，删除元素需要缩容，那么复杂度就一直是 O(n)。

在 clear() 和 remove() 方法里进行缩容：

public void clear() {
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    size = 0;
    
    // 缩容
    if (elements != null && elements.length > DEFAULT_CAPACITY) {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
}
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;
    
    // 缩容
    trim();
    
    return old;
}

泛型

使用泛型技术可以让动态数组更加通用，可以存放任何数据类型。
E 表示泛型：

public class ArrayList<E> {
    private int size;
    private E[] elements;
}

使用 Object 创建的数组可以存放所有对象类型，因为所有的类都继承自Object。

1	elements = (E[]) new Object[capacity];

示例：

ArrayList<Integer> ints = new ArrayList<>();
ints.add(10);
ArrayList<Object> objs = new ArrayList<>();
objs.add(10);
objs.add(new Person(10, "Tom"));

对象数组

数组中存放的是对象地址。
动态数组10

删除元素

删除元素时，需要将数组对应的位置设为 null：

/**
* 清除所有元素
*/
public void clear() {
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    size = 0;
}
/**
* 删除index位置的元素
* @param index
* @return
*/
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;
}

在调用 clear() 方法时，Java 的垃圾回收机制不会立即执行，可以通过 System.gc() 让垃圾回收机制立即启动：

1
2
3

persons.clear();
// 提示JVM进行垃圾回收
System.gc();

查找元素

如果数组支持 null，需要修改 indexOf() 方法：

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 (elements[i] == element) return i; // == 比较内存地址
            if (elements[i].equals(element)) return i; // 重写 equals()。Integer 调用 equals()，内部比较的是数值
        }
    }
    return ELEMENT_NOT_FOUND;
}

判等

Person 类里实现 equals() 方法（age 相等 -> 两个 Person 对象相等）：

public boolean equals(Object obj) {
	if (obj == null) return false;
	if (obj instanceof Person) {
		Person person = (Person)obj;
		return this.age == person.age;
	}
	return false;
}

源码分析

ArrayList

JDK中内置了一个动态数组类：java.util.ArrayList。

方式一：
如果 Eclipse 里没有加载这个包，可以手动导入：
动态数组11

按住 command 点击 ArrayList：

public class Main {
	public static void main(String[] args) {
		java.util.ArrayList<E>
	}
}

方式二：
动态数组12

代码

变量

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access
/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

构造方法

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

数组大小

//**
 * Returns the number of elements in this list.
 *
 * @return the number of elements in this list
 */
public int size() {
    return size;
}

判空

/**
 * Returns {@code true} if this list contains no elements.
 *
 * @return {@code true} if this list contains no elements
 */
public boolean isEmpty() {
    return size == 0;
}

查找

/**
 * Returns {@code true} if this list contains the specified element.
 * More formally, returns {@code true} if and only if this list contains
 * at least one element {@code e} such that
 * {@code Objects.equals(o, e)}.
 *
 * @param o element whose presence in this list is to be tested
 * @return {@code true} if this list contains the specified element
 */
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
/**
 * Returns the index of the first occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the lowest index {@code i} such that
 * {@code Objects.equals(o, get(i))},
 * or -1 if there is no such index.
 */
public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

获取

/**
 * Returns the element at the specified position in this list.
 *
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

修改

/**
 * Replaces the element at the specified position in this list with
 * the specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

添加

/**
 * This helper method split out from add(E) to keep method
 * bytecode size under 35 (the -XX:MaxInlineSize default value),
 * which helps when add(E) is called in a C1-compiled loop.
 */
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}
/**
 * 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) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

删除

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);
    return oldValue;
}

清空

/**
 * Removes all of the elements from this list.  The list will
 * be empty after this call returns.
 */
public void clear() {
    modCount++;
    final Object[] es = elementData;
    for (int to = size, i = size = 0; i < to; i++)
        es[i] = null;
}

扩容

**
 * Increases the capacity of this {@code ArrayList} instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        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
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}
private Object[] grow() {
    return grow(size + 1);
}

测试

使用 Asserts（断言）进行测试：
动态数组13

复杂度分析

ps：自定义ArrayList（代码）