线性表——动态数组

引言

数据结构是计算机存储、组织数据的方式。常见的数据结构有：

（1）线性结构

如：线性表（包括：数组、链表、栈、队列、哈希表）。

（2）树形结构

如：二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集。

（3）图形结构

如：邻接矩阵、邻接表。

注：在实际应用中，要根据使用场景选择最合适的数据结构。

线性表

（1）线性表是具有n（n>=0）个相同类型元素的有限序列。 如下图所示：

• 每个元素都对应一个索引，可以通过索引找到相应的元素。

• $a_1$是首节点（首元素），$a_n$是尾节点（尾元素）。

• $a_1$是$a_2$的前驱，$a_2$是$a_1$的后继。

（2）常见的线性表有： 数组、链表、栈、队列、哈希表（又称“散列表”）。

线性表——“动态数组”

1、数组（Array）

数组 是一种顺序存储 的线性表，所有元素的内存地址是连续的。

例：使用Java新建一个名称为array的数组。

public static void main(String[] args) {
	int[] array = new int[] {11,22,33};
}

该代码在内存中表现为：局部变量array存在栈中，new出来的数组元素顺序存储在堆中。 如下图所示：

在很多编程语言中，数组都有一个致命的缺点：无法动态修改容量。

实际开发中，我们往往希望数组的容量是动态改变的。为了解决这个问题，我们一般的做法就是自己封装一个动态数组。

2、动态数组的设计（Dynamic Array）

（1）类的结构设计

在编程之前，我们需要先对动态数组类（ArrayList）的结构进行设计。如下图所示：

动态数组类需要的成员主要包括：

• 数组存放元素的数量。 //private int size;

size = 元素（Element）数目 = 数组长度 ≤ 数组容量（capacity）。

• 用来存放数组的变量。 //private int[] elements;

• 构造函数（有形参、无形参）

通过构造函数，我们可以在新建动态数组时对其容量（capacity）进行初始化。一方面，我们要构建一个带形参的构造函数，让用户自定义动态数组的容量；另一方面，我们还要构建一个无形参的构造函数，用来处理用户未定义动态数组的容量时的情况。

• 析构函数（Java语言没有）

• 接口函数

（2）接口设计

• int size(); //元素的数量
• boolean isEmpty(); //是否为空
• boolean contains(E element); //是否包含某元素
• E get(int index); //获取index位置对应的元素
• E set(int index, E element); //设置index位置的元素（覆盖）
• void add(E element); //添加元素到尾部
• void add(int index, E element); //在index位置添加元素
• E remove(int index); //删除index位置对应的元素
• int indexOf(E element); //查看元素的位置
• void clear(); //清除所有元素

注：接口是供别人在外部通过对象调用的，所以要设计成公有（public）成员。

3、动态数组的实现

3.1 编程实现

新建一个项目，在其中：

1. 先新建一个名称为ArrayList（包名为：com.atangbiji）的类，用来自己实现动态数组；

2. 再新建一个名称为Main（包名为：com.atangbiji）的类，用来调用（测试）自己封装的动态数组。

注： 其实Java中已经为我们封装好了ArrayList类。当我们调用ArrayList时会提示有两个ArrayList类，如下图所示。为了测试自己写的数据结构，此时我们应该选择包名为com.atangbiji的那个。

3. 我们先考虑数组元素均为整数的情况。 （后面在此基础上逐步完善）

（1）定义私有成员变量

ArrayList.java文件：

private int size;	//数组存放元素的数量
private int[] elements;	//用来存放数组的变量

（2）创建构造函数

ArrayList.java文件：

private static final int DEFAULT_CAPACITY =  10; //默认容量
/*
 * 构造函数
 * @param capacity初始容量
 * @return
 * */
public ArrayList(int capacity) {
	capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;//边界条件处理
	elements = new int[capacity]; //创建动态数组
}
public ArrayList() {
	this(DEFAULT_CAPACITY);//调用有形参的构造函数
}

在构造函数中创建动态数组。 当用户自定义动态数组的容量时，调用带形参的构造函数，系统创建容量为capacity的数组；当用户未定义动态数组的容量时，调用无形参的构造函数，系统创建容量为默认值的数组。

注：
a. 我们将默认容量设置为私有静态常量DEFAULT_CAPACITY。其中：

• static为静态，保证变量的值只有一份；

• final为常量，类似于C++中的const。

b. Java中构造函数间的相互调用使用this对象完成。

c. 若用户自定义容量小于默认值，我们这里仍然创建一个默认容量的数组。

（3）实现“size()”接口

ArrayList.java文件：

/*
 *  元素的数量
 * @param
 * @return 
 * */
public int size() {
	return size;	//直接返回size成员变量即可
}

（4）实现“isEmpty()”接口

ArrayList.java文件：

/*
 *  是否为空
 * @param
 * @return 
 * */
public boolean isEmpty() {
	return size == 0;	//size为0为空，否则不为空
}

（5）实现“get(int index)”接口

该功能只需根据索引从成员变量elements中获取对应的元素即可。需要注意的是： 获取元素之前，我们要对index的边界条件进行处理。为了使程序更加友善，我们这里采取的是：如果index越界，那么就抛出一个异常。

动态数组获取元素的速度极快，时间复杂度为O(1)。

ArrayList.java文件：

/*
 *  获取index位置对应的元素
 * @param: index
 * @return 
 * */
public int get(int index) {
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);	//抛出异常
	}
	return elements[index];
}

（6）实现“set(int index, int element)”接口

ArrayList.java文件：

/*
 *  设置index位置的元素（覆盖）
 * @param: index
 * @param: element
 * @return: 原来的元素
 * */
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;
}

（7）实现“indexOf(int element)”接口

遍历数组，判断数组中是否存在该元素即可。若存在，返回索引。若不存在，返回-1。

ArrayList.java文件：

private static final int ELEMENT_NOT_FOUND = -1; //未找到
/*
 *  查看元素的位置
 * @param: element
 * @return: 元素的位置
 * */
public int indexOf(int element) {
	//遍历数组
	for (int i = 0; i < size; i++) {
		if(elements[i] == element)
		{
			return i;
		}
	}
	return ELEMENT_NOT_FOUND;
}

（8）实现“contains(int element)”接口

在数组中查找该元素，若返回不为-1，则说明该元素存在。

ArrayList.java文件：

/*
 *  是否包含某元素
 * @param: element
 * @return 
 * */
public boolean contains(int element) {
	return indexOf(element) != ELEMENT_NOT_FOUND;
}

（9）实现“clear()”接口

其实，清空数组并不需要将内存释放，只需令size = 0即可。此时，为该数组分配的内存还在，以后该数组对象还可以重复利用该内存。

**注：**频繁地申请和释放内存空间反而是很浪费时间（性能）的。

ArrayList.java文件：

/*
 * 清除所有元素
 * @param
 * @return
 * */
public void clear() {
	size = 0;	//并不需要释放数组内存
}

（10）实现“remove(int index)”接口

思路： 若要删除index对应的元素，则只需要将后续元素从前往后 依次前移一位即可。即：将index+1对应的元素挪到index处，以此类推。

ArrayList.java文件：

/*
 *  删除index位置对应的元素
 * @param: index
 * @return: 被删除的元素
 * */
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; i++) {
		elements[i - 1] = elements[i];
	}
	size --;
	
	return old;
}

（11）★实现“add(int index,int element)”接口

1. 当size < capacity时

思路： 若要在index处添加元素，则只需要从后往前 依次将后续元素向后移一位，直到index位置空出，再添加新元素即可。

注： 移动顺序不能弄反。

ArrayList.java文件：

/*
 *  在index位置添加元素
 * @param: index
 * @param: element
 * @return
 * */
public void add(int index,int element) {
	//判断是否合法
	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++;
}

动态扩容

2. 当size = capacity时——扩容

当size=capacity（数组空间用完）时，如果我们需要再添加新的元素，那么就必须先对数组进行扩容。 由于内存是在新建对象的时候就已经明确了的，我们是不能直接在原有数组的后面任意拼接一块新内存用来放新元素的。

此时我们的做法是：

①重新开辟一块更大的（如：1.5倍）内存空间；②将之前的数组元素逐一移到新的内存；③让用来存放数组的成员elements指向新的内存空间；④将之前的数组内存释放（Java垃圾自动回收）。

因此，我们需要对add(int index,int element)接口做如下修改。

ArrayList.java文件：

/*
 *  在index位置添加元素
 * @param: index
 * @param: element
 * @return
 * */
public void add(int index,int element) {
	//判断是否合法
	if (index < 0 || index > size) {
		throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);	//抛出异常
	}
	//确保容量充足
	ensureCapacity(size + 1);
	//从后往前循环移动
	for (int i = size - 1; i >= index; i--) {
		elements[i + 1] = elements[i];
	}
	elements[index] = element;
	size++;
}

/*
 *  保证要有capacity的容量
 * @param: capacity
 * @return
 * */
@SuppressWarnings("unchecked")//注解
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("容量已从 " + oldCapacity + " 扩充到  " + newCapacity);
}

（12）实现“add(int element)”接口

add(int element)接口是add(int index,int element)接口的特例。我们只需在size处添加新元素即可。

ArrayList.java文件：

/*
 *  添加元素到尾部
 * @param: element
 * @return 
 * */
public void add(int element) {
	add(size, element);
}

（13）打印数组中的所有元素

在Java中，当我们要打印某一个对象时，系统内部其实是通过调用toString()方法来实现的。默认情况下，打印的该对象的类名。为了打印对象数组中的所有元素，我们只需重写（也称覆盖）toString()方法，并在其中完成字符串的拼接即可。

注： Java中字符串拼接建议使用StringBuilder类。

ArrayList.java文件：

/*
 * 打印数组中的所有元素：重载toString()函数
 *  @param
 *  @return 数组元素
 * */
@Override
public String toString() {
	//新建StringBuilder
	StringBuilder string = new StringBuilder();
	
	//拼接字符串
	string.append("size = ").append(size).append("; [");
	for (int i = 0; i < size; i++) {
		string.append(elements[i]);
		
		if (i != size - 1) {
			string.append(", ");
		}
	}
	string.append("]");
	
	return string.toString();
}

3.2 接口测试

在Main类（Main.java文件）中新建一个ArrayList对象，用来测试自己封装的动态数组。这里仅以添加元素接口为例进行测试，其它接口的测试方法与此类似，这里不再赘述。

Main.java文件：

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		//动态数组接口测试
		ArrayList list = new ArrayList();
		
		for (int i = 0; i < 30; i++) {
			list.add(i);
		}
		
		System.out.println(list);
	}

}

运行该程序，输出结果为：

4、完善动态数组

4.1 泛型 & 对象数组

由于我们前面实现的动态数组只考虑数组元素为整数的情况，而实际应用过程中，我们还经常需要使用存放小数、对象等数据类型的动态数组。因此，我们需要在前面的基础上，对数组中存放元素的数据类型进行 “泛型” 处理。

使用泛型技术可以让动态数组更加通用，使其可以存放任何数据类型。 Java中实现泛型的步骤主要包括：

(1)在类的定义时进行泛化。（泛化类）

public class ArrayList<E> {}

其中：E为泛化后的类型名，我们可自定义，一般使用常用的泛型类型变量即可。

**附：**一些常用的泛型类型变量：

E：元素（Element），多用于java集合框架
K：关键字（Key）
N：数字（Number）
T：类型（Type）
V：值（Value）

（2）泛化用来存放数组的成员变量。（泛化成员变量）

private E[] elements;	//用来存放数组的变量

**（3）泛化各方法中所有元素的数据类型。（泛化成员函数）**如：

public void add(E element) {}

需要说明的是：Java中在创建数组时不能直接对其进行泛化。（即：elements = new E[capacity]; 是错误的。）由于Java中的所有类最终都会继承Object类，因此我们可以通过先创建对象数组再强制转换成泛型数组的方式对数组元素的类型进行泛化。即：

elements = (E[]) new Object[capacity]; //创建动态数组

**注：**此时会有一个警告。按“Ctrl + 1”键，在弹出菜单中选择uncheck选项，此时系统便自动生成@SuppressWarnings(“unchecked”)注解。

综上所述，泛型后的ArrayList.java文件为：

package com.atangbiji;

@SuppressWarnings("unchecked")//注解

public class ArrayList<E> {
	
	private int size;	//数组存放元素的数量
	private E[] elements;	//用来存放数组的变量
	
	//注：static为静态，保证变量的值只有一份；
	//final为常量，类似于C++中的const	
	private static final int DEFAULT_CAPACITY =  10; //默认容量
	private static final int ELEMENT_NOT_FOUND = -1; //未找到

	
	/*
	 * 构造函数
	 * @param capacity初始容量
	 * @return
	 * */
	public ArrayList(int capacity) {
		capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;//边界条件处理
		elements = (E[]) new Object[capacity]; //创建动态数组 
	}
	public ArrayList() {
		this(DEFAULT_CAPACITY);//调用有形参的构造函数
	}
	/*
	 * 清除所有元素
	 * @param
	 * @return
	 * */
	public void clear() {
		size = 0;	//并不需要释放数组内存
	}
	
	/*
	 *  元素的数量
	 * @param
	 * @return 
	 * */
	public int size() {
		return size;	//直接返回size成员变量即可
	}
	
	/*
	 *  是否为空
	 * @param
	 * @return 
	 * */
	public boolean isEmpty() {
		return size == 0;	//size为0为空，否则不为空
	}
	
	/*
	 *  添加元素到尾部
	 * @param: element
	 * @return 
	 * */
	public void add(E element) {
		add(size, element);
	}
	
	/*
	 *  获取index位置对应的元素
	 * @param: index
	 * @return 
	 * */
	public E get(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);	//抛出异常
		}
		return elements[index];
	}
	
	/*
	 *  设置index位置的元素（覆盖）
	 * @param: index
	 * @param: element
	 * @return: 原来的元素
	 * */
	public E set(int index, E element) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);	//抛出异常
		}
		
		E old = elements[index];
		elements[index] = element;
		
		return old;
	}
	
	/*
	 *  在index位置添加元素
	 * @param: index
	 * @param: element
	 * @return
	 * */
	public void add(int index,E element) {
		//判断是否合法
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);	//抛出异常
		}
		//确保容量充足
		ensureCapacity(size + 1);
		//从后往前循环移动
		for (int i = size - 1; i >= index; i--) {
			elements[i + 1] = elements[i];
		}
		elements[index] = element;
		size++;
	}
	
	/*
	 *  保证要有capacity的容量
	 * @param: capacity
	 * @return
	 * */
	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;
		
		System.out.println("容量已从 " + oldCapacity + " 扩充到  " + newCapacity);
	}
	
	/*
	 *  删除index位置对应的元素
	 * @param: index
	 * @return: 被删除的元素
	 * */
	public E remove(int index) {
		//判断是否合法
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);	//抛出异常
		}
		
		E old = elements[index];
		//循环移动
		for (int i = index + 1; i < size; i++) {
			elements[i - 1] = elements[i];
		}
		size --;
		
		return old;
	}
	
	/*
	 *  查看元素的位置
	 * @param: element
	 * @return: 元素的位置
	 * */
	public int indexOf(E element) {
		//遍历数组
		for (int i = 0; i < size; i++) {
			if(elements[i] == element)
			{
				return i;
			}
		}
		return ELEMENT_NOT_FOUND;
	}
	
	/*
	 *  是否包含某元素
	 * @param: element
	 * @return 
	 * */
	public boolean contains(E element) {
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}
	
	/*
	 * 打印数组中的所有元素：重载toString()函数
	 *  @param
	 *  @return 数组元素
	 * */
	@Override
	public String toString() {
		//新建StringBuilder
		StringBuilder string = new StringBuilder();
		
		//拼接字符串
		string.append("size = ").append(size).append("; [");
		for (int i = 0; i < size; i++) {
			string.append(elements[i]);
			
			if (i != size - 1) {
				string.append(", ");
			}
		}
		string.append("]");
		
		return string.toString();
	}
}

附：泛型接口测试

新建一个Person类，添加成员变量：age、name，按“Shift+Alt+S”键，通过弹出菜单快速生成构造函数和toString()函数。

Person.java文件：

package com.atangbiji;

public class Person {
	private int age;
	private String name;
	
	//	构造函数
	public Person(int age, String name) {
		this.age = age;
		this.name = name;
	}

	@Override
	public String toString() {
		return "Person [age=" + age + ", name=" + name + "]";
	}
}

在Main.java文件中创建存放元素为Person对象的 对象数组，并对泛化后的动态数组接口进行测试。这里仅以添加元素接口为例进行测试，其它接口的测试方法与此类似，这里不再赘述。

Main.java文件：

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		//动态数组接口测试
		//对象数组
		ArrayList<Person> persons = new ArrayList<>();
		
		persons.add(new Person(10, "Tom"));
		persons.add(new Person(12, "Jack"));
		persons.add(new Person(15, "Rose"));
		
		System.out.println(persons);
		
		//整型数组（Integer为int的包装类）
		ArrayList<Integer> ints = new ArrayList<>();
		
		for (int i = 0; i < 30; i++) {
			ints.add(i);
		}
		
		System.out.println(ints);
	}
}

运行程序，输出结果为：

由此可见，泛化后的动态数组可以存放各种数据类型的元素。

注：泛化后的数据结构不能直接存放基本数据类型，此时需要使用相应的包装类。 Java 中提供的 8 种基本数据类型及对应的包装类如下表所示。

4.2 对象数组内存管理

完成泛型后的动态数组，既可以存储基本数据类型，也可以存储引用类型（对象）。

（1）若数组元素是基本数据类型，则数组内存中存放的是数据本身。

（2）若数组元素是类的对象，则数组内存中存放的是指向各对象的引用。

**注：**当对象数组中的某一（或某些）对象不再使用时，我们需要主动释放该（或这些）对象所占用的内存空间。即：我们需要将对象数组中被删除对象的地址设为null。（有一利必有一弊）

因此，我们还需要对ArrayList类的如下接口进行完善。

4.3 完善接口

（1）完善“clear()”接口

ArrayList.java文件：

/*
 * 清除所有元素
 * @param
 * @return
 * */
public void clear() {
	for (int i = 0; i < size; i++) {
		elements[i] = null;	//主动释放对象数组中被删除对象所占用的内存空间
	}
	size = 0;	//并不需要释放数组内存
}

**注：**我们只是清除了数组中地址所指向的对象，而数组本身并没有清除。

附：完善后接口测试

为了证明完善后的接口的确释放了被删除对象的内存空间，我们可以使用Java中自带的finalize()方法进行测试，我们可以在该方法中留下对象死前的“遗言”。

Person.java文件：

@Override
protected void finalize() throws Throwable {
	// TODO Auto-generated method stub
	super.finalize();
	
	System.out.println("被删除对象的内存空间已释放");
}

**注：**finalize()方法类似于C++中的析构函数。

Main.java文件：

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		//动态数组接口测试
		//对象数组
		ArrayList<Person> persons = new ArrayList<>();
		
		persons.add(new Person(10, "Tom"));
		persons.add(new Person(12, "Jack"));
		persons.add(new Person(15, "Rose"));
		
		persons.clear();
		//提醒JVM进行垃圾回收
		System.gc();
		System.out.println(persons);
	}
}

运行程序，输出结果为：

若将clear()接口恢复到完善前的状态，再次运行程序，输出结果为：

由此可见，完善后的动态数组会主动释放被删除对象所占用的内存空间，系统性能更好。

（2）完善“remove(int index)”接口

同样地，对于remove(int index)接口，当我们删除index对应的元素后，原来存放最后一个元素的内存空间也必须主动清空，否则可能导致对象数组中的最后一个元素无法被彻底删除。

ArrayList.java文件：

/*
 *  删除index位置对应的元素
 * @param: index
 * @return: 被删除的元素
 * */
public E remove(int index) {
	//判断是否合法
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);	//抛出异常
	}
	
	E old = elements[index];
	//循环移动
	for (int i = index + 1; i < size; i++) {
		elements[i - 1] = elements[i];
	}
	size --;
	
	elements[size] = null;//清空动态数组的最后一个元素
	
	return old;
}

（3）完善“indexOf(E element)”接口

① equals(Object obj)——对象相等问题

前面获取元素序号的方法是通过比较元素是否相等来实现的。当数组元素为数字时我们可以使用“==”来判断它们是否相等；由于对象数组中存放的是对象的引用（地址），当元素类型为对象时，如何比较两个对象是否相等呢？

Java中比较两个对象是否相等，一般我们不建议比较内存地址是否相等，而是通过重写equals(Object obj)方法，并在其内部自定义两个对象相等的条件。比如这里我们可以自定义：当两个人的age和name均相等时，我们就认为这两个Person对象相等。具体代码如下：

Person.java文件：

@Override
public boolean equals(Object obj) {
	Person person = (Person)obj;
	//当两个人的age和name均相等时，我们就认为这两个Person对象相等
	return (this.age == person.age)&&(this.name.equals(person.name));
}

Integer类中默认重写了equals方法，并在其中定义数值相等时两元素相等。因此，为了使indexOf(E element)接口更通用，我们需对其进行如下优化：

ArrayList.java文件：

/*
 *  查看元素的位置
 * @param: element
 * @return: 元素的位置
 * */
public int indexOf(E element) {
	//遍历数组
	for (int i = 0; i < size; i++) {
		if(elements[i].equals(element))
		{
			return i;
		}
	}
	return ELEMENT_NOT_FOUND;
}

**注：**若未重写equals(Object obj)方法，则Object1.equals(Object2)默认比较的是Object1与Object2的内存地址是否相等。

此时，该接口便既适用于数组元素为基本数据类型的情况，也适用于数组元素为对象类型的情况。

② null的处理

我们前面设计的动态数组是否允许数组元素为空（null）呢？下面我们进行测试：

Main.java文件：

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		//动态数组接口测试
		//对象数组
		ArrayList<Person> persons = new ArrayList<>();
		
		persons.add(new Person(10, "Tom"));
		persons.add(new Person(12, "Jack"));
		persons.add(new Person(15, "Rose"));
		persons.add(null);
		
		System.out.println(persons);
	}
}

运行程序，输出结果为：

由此可见，我们前面设计的动态数组是允许数组元素为空（null）的。

**注：**一般情况下，Java中的动态数组也是允许元素为空的。

由于null元素是不能调用方法的。若elements[i] = null，则elements[i].equals()会出现空指针异常。因此，为了更好使动态数组更好地处理null元素，我们需要对indexOf(E element)接口做进一步优化。

ArrayList.java文件：

/*
 *  查看元素的位置
 * @param: element
 * @return: 元素的位置
 * */
public int indexOf(E element) {
	//若元素为空（null）
	if (element == null) {
		//遍历数组
		for (int i = 0; i < size; i++) {
			//elements[i]可以是null，也可以不是null。
			if (elements[i] == null) {
				return i;
			}
		}
	}else {
		//若元素不为空（null）。
		//遍历数组
		for (int i = 0; i < size; i++) {
			//elements[i]可以是null，也可以不是null。
			if(element.equals(elements[i]))
			{
				return i;
			}
		}
	}
	return ELEMENT_NOT_FOUND;
}

附：完善后接口测试

Main.java文件：

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		//动态数组接口测试
		//对象数组
		ArrayList<Person> persons = new ArrayList<>();
		
		persons.add(new Person(10, "Tom"));
		persons.add(new Person(12, "Jack"));
		persons.add(new Person(15, "Rose"));
		persons.add(null);
		persons.add(new Person(12, "Jack"));
		persons.add(null);
		
		System.out.println(persons);
		
		Person person = new Person(12, "Jack");
		System.out.println("动态数组中第一个Jack的索引是：" + persons.indexOf(person) + " 。");
		
		System.out.println("动态数组中第一个空元素的索引是：" + persons.indexOf(null) + " 。");
	}
}

运行程序，输出结果为：

（4）缩容

① remove(int index)时缩容

当数据规模很大时，扩容可能会使动态数组有比较多的剩余空间。若此时内存使用比较紧张，我们可以考虑对动态数组进行缩容操作。

缩容与扩容的操作类似。两者都是：①先开辟一块新的内存空间；②然后再将之前的数组元素逐一移到新的内存；③让用来存放数组的成员elements指向新的内存空间；④将之前的数组内存释放（Java垃圾自动回收）。只不过，扩容新开辟的内存空间更大，缩容新开辟的内存空间更小。

我们主要在删除元素后考虑是否要缩容。（这里我们考虑，当“剩余空间 > 总容量/2”的时候，就对其进行缩容。当然我们也不希望数组容量缩的太小，因此我们这里缩容后的数组容量不小于默认容量。）

ArrayList.java文件：

/*
 *  删除index位置对应的元素
 * @param: index
 * @return: 被删除的元素
 * */
public E remove(int index) {
	//判断是否合法
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);	//抛出异常
	}
	
	E old = elements[index];
	//循环移动
	for (int i = index + 1; i < size; i++) {
		elements[i - 1] = elements[i];
	}
	size --;
	
	elements[size] = null;//清空动态数组的最后一个元素
	
	//判断动态数组是否需要缩容
	trim();
	
	return old;
}

/*
 *  动态数组缩容
 * @param
 * @return
 * */
private void trim() {
	//数组容量
	int oldCapacity = elements.length;
	//当数组剩余空间超过总容量一半的时候，就对其进行缩容
	//且缩容后的数组容量不小于默认容量
	if (size < (oldCapacity >> 1) && oldCapacity > DEFAULT_CAPACITY) 
	{
		//若原数组容量足够用，则缩容0.5倍
		int newCapacity = oldCapacity >> 1;
		//开辟新的内存空间
		E[] newElements = (E[]) new Object[newCapacity];
		//逐一移到元素
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		//指向新内存
		elements = newElements;
		
		System.out.println("容量已从 " + oldCapacity + " 缩容到  " + newCapacity);
	}	
}

附：动态数组缩容测试

Main.java文件：

package com.atangbiji;

public class Main {

	public static void main(String[] args) {
		
		//动态数组缩容测试
		ArrayList<Integer> list = new ArrayList<>();
		
		//添加
		for (int i = 0; i < 40; i++) {
			list.add(i);
		}
		
		System.out.println(list);
		
		//删除
		for (int i = 0; i < 40; i++) {
			list.remove(0);
		}
		
		System.out.println(list);
		
	}
}

运行程序，输出结果为：

② 复杂度震荡（掌握结论即可）

**注意：**如果扩容倍数和缩容时机设计不当，有可能会导致复杂度震荡。

如：若我们设置动态数组扩容时数组容量×2；且“剩余空间 >= 总容量/2”时动态数组进行缩容。则：当数组的容量为n，且此时数组中元素的个数为n个（即刚好满了）时，若此时我们向数组中再添加一个元素，则会触发扩容操作；若紧接着我们又将刚添加的元素从数组中删除，则又会重新触发缩容操作。反复执行上述两步，动态数组便会反复扩容和缩容，此时每步操作的时间复杂度都是O(n)。这与我们大多数情况下在数组尾部一直添加（或一直删除）元素时要隔n次操作才会有一次操作的时间复杂度为O(n)，其余操作的时间复杂度一直为O(1)的情况相悖。这种突发状况我们称为 “复杂度震荡”。

**注：我们只需让“扩容倍数×缩容条件≠1”即可避免复杂度震荡。**我们这里1.5×0.5≠1，因此不会出现复杂度震荡。

③ clear()时缩容

建议清空动态数组后，对其进行缩容。我们这里：清空动态数组后，若数组长度>默认容量，则自动将数组长度缩容至默认容量。

ArrayList.java文件：

/*
  * 清除所有元素
 * @param
 * @return
 * */
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];
	}
}

5、java.util.ArrayList类源码分析

其实，在Java的java.util包中已经为我们封装好了一个ArrayList类。通过对比可以分析，我们自己实现的动态数组和官方提供的差不多，只是官方的接口更加丰富，而我们只实现了常用的增删改查接口。

6、动态数组的时间复杂度分析

一般情况下，我们提到的运行时间都是最坏情况下代码的运行时间。

有时候一段代码在不同情况下，其时间复杂度是不一样的。为了描述代码在不同情况下的不同时间复杂度，我们引入了最好、最坏、平均和均摊时间复杂度。

（1）最好情况复杂度（best case time complexity）

即：在最理想的情况下，执行这段代码的时间复杂度。

（2）最坏情况复杂度（worst case time complexity）

即：在最糟糕的情况下，执行这段代码的时间复杂度。

（3）平均情况复杂度（average case time complexity）

即：平均情况下的时间复杂度。（又称“加权平均时间复杂度”和“期望时间复杂度”）

• 平均情况时间复杂度=各种情况执行时间相加÷总的情况数

如：由于动态数组插入和删除元素的位置不同，会导致时间复杂度出现量级差异。这种情况下就需要考虑平均情况时间复杂度。

由于最好和最坏情况复杂度是极端情况，发生的概率并不大。因此，平均情况时间复杂度是所有情况中比较有意义的。

**注意：**多数情况下，我们不需要区分最好、最坏、平均情况时间复杂度。为的是更有效的描述代码的时间复杂度，只有同一块代码在不同情况下的时间复杂度有量级差距时，我们才会区分这3种情况。

（4）均摊复杂度（amortized time complexity）

均摊复杂度是一个更加高级的概念，它是一种特殊的情况，应用的场景也更加特殊和有限。

如：对于“add(int element)”接口，由于大多数情况下size < capacity，此时便直接在数组的最后添加新元素，此时时间复杂度为O(1)；但当数组空间用完时，size=capacity，若再添加一个新元素，便需要扩容，从而让这一次添加元素的时间复杂度会突变至O(n)，然后又恢复到O(1)，如此往复。对于这种某些特殊情况下执行时间存在突变的函数，我们使用均摊复杂度来描述算法的复杂度会更加合理。即：将这一次突变的执行时间均摊到每一次调用上去（一般情况下，均摊复杂度=最好时的复杂度）。（就好像大佬们的收入被平均了一样！）

某段代码在反复执行过程中，若某次执行的时间复杂度出现突变。即：当一组操作存在前后连贯的时序关系时，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度较高。此时，若我们将这一组操作放在一起分析，将这一次突变的执行时间均摊到每一次调用上去，使用均摊复杂度来描述算法的时间复杂度会更加合理。由于僧多粥少，所以一般均摊时间复杂度就等于最好情况时间复杂度。

**注：**其实，我们还可以进一步优化动态数组的add(int index,int element)和remove(int index)接口。具体优化思路和实现过程我们会在后面学习循环队列时讲解，该知识点了解即可。

7、总结

（1）动态数组的优点：

• 既可以存放基本数据类型，也可以存放类的对象。
• 可以动态扩容。
• 循秩访问，随机访问速度非常快。（省时间）

（2）动态数组的缺点：

• **（费空间）**因为size<=capacity且大多数情况下size < capacity（申请了却未使用），所以可能会造成内存空间的大量浪费。（内存利用率一般小于100%）

（本讲完，系列博文持续更新中…… ）

参考文献：
[1] 《恋上数据结构与算法》，小码哥MJ
[2] 《数据结构与算法》，邓俊辉

如何获取源代码？

关注 “阿汤笔迹” 微信公众号，在后台回复关键词 “数据结构与算法设计与实现” ，即可获取项目源代码。

原文地址：http://www.atangbiji.com/2020/05/24/ArrayList/
博主最新文章在个人博客 http://www.atangbiji.com/ 发布。