动态数组

什么是数据结构？

• 数据结构是计算机存储、组织数据的方式。

• 包含以下几种结构：

  线性结构

  • 线性表（数组、链表、栈、队列、哈希表）

  树形结构

  • 二叉树、AVL 树、红黑树、B树、堆、Trie(字典树)、哈夫曼树、并查集

  图形结构

  • 邻接矩阵，邻接表

• 在实际应用中，根据使用场景来选择最合适的数据结构

线性表

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

一般来说，都有个索引，便于查找元素。

例如：

从 a1 -> a(n) 的一行元素

• a1 是首节点(首元素)，a(n) 是尾结点(尾元素)
• a1 是 a2 的前驱，a2 是 a1 的后继

数组

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

下面来分析下这段代码：

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

内存中的表现

array 是个局部变量，既然它是个局部变量，它肯定是放栈空间，那它右边这些数据是通过 new 获取的，所以它肯定是放堆空间。

new 是向堆空间申请内存

最终它的这个内存结构其实就是：栈空间里面有个 array 这个变量，然后指向堆空间的这个数组元素，由于它是数组，所以它们的内存地址是连续的。

缺陷

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

但在实际开发中，我们是不是希望数组的容量是可以动态改变的？

所以需要实现动态数组。

动态数组

接口设计

动态数组 (Dynamic Array) 接口设计

补充一个删除接口：

E remove(E element) // 直接删除指定元素并返回

代码实现

public class ArrayList<E> {
	/**
	 * 元素的数量
	 */
	private int size;
	/**
	 * 所有的元素
	 */
	private E[] elements;
	
	private static final int DEFAULT_CAPACITY = 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);
	}
	
	/**
	 * 清除所有元素
	 */
	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];
    }
	}

	/**
	 * 元素的数量
	 * @return
	 */
	public int size() {
		return size;
	}

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

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

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

	/**
	 * 获取index位置的元素
	 * @param index
	 * @return
	 */
	public E get(int index) { // O(1) -- 编译器根据索引偏移量（字节）直接找到对应的元素
		rangeCheck(index);
		return elements[index]; 
	}

	/**
	 * 设置index位置的元素
	 * @param index
	 * @param element
	 * @return 原来的元素ֵ
	 */
	public E set(int index, E element) { // O(1)
		rangeCheck(index); // 1
		
		E old = elements[index]; // 1
		elements[index] = element; // 1
		return old;
	}

	/**
	 * 在index位置插入一个元素
	 * @param index
	 * @param element
	 */
	public void add(int index, E element) { // O(n) -- n 是数据规模
    /**
	   * 最好：O(1)
	   * 最坏：O(n)
	   * 平均：(1+2+···+n)/n == O(n)
	   */
    rangeCheckForAdd(index);
    
    ensureCapacity(size + 1); // 确保容量
		
		for (int i = size; i > index; i--) { // 在这里 size 就是数据规模
			elements[i] = elements[i - 1];
		}
		elements[index] = element;
		size++;
	}

	/**
	 * 删除index位置的元素
	 * @param index
	 * @return
	 */
	public E remove(int index) {
    /**
	   * 最好：O(1) -- 删最后一个位置
	   * 最坏：O(n) -- 删第一个位置
	   * 平均：O(n)
	   */
		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;
	}

  /**
	 * 直接删除指定元素
	 * @param element
	 * @return
	 */
	public E remove(E element){
		remove(indexOf(element));
	}
  
	/**
	 * 查看元素的索引
	 * @param element
	 * @return
	 */
	public int indexOf(E element) {
     // null 值处理
		if (element == null) {  // 1
       // 找出第一个 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;
	}
	
//	public int indexOf2(E element) {
//		for (int i = 0; i < size; i++) {
//			if (valEquals(element, elements[i])) return i; // 2n
//		}
//		return ELEMENT_NOT_FOUND;
//	}
//	
//	private boolean valEquals(Object v1, Object v2) {
//		return v1 == null ? v2 == null : v1.equals(v2);
//	}

    /**
	 * 保证要有capacity的容量
	 * @param capacity
	 */
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		if (oldCapacity >= capacity) return;
		
		// 新容量为旧容量的1.5倍
    // 右移一相当于除以2，即 1 + 1/2 = 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);
	}
	
	private void outOfBounds(int index) {
		throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
	}
	
	private void rangeCheck(int index) {
		if (index < 0 || index >= size) {
			outOfBounds(index);
		}
	}
	
	private void rangeCheckForAdd(int index) {
		if (index < 0 || index > size) {
			outOfBounds(index);
		}
	}
  
  private void trim() {
		// 30
		int oldCapacity = elements.length;
		// 15
		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;
		
		System.out.println(oldCapacity + "缩容为" + newCapacity);
	}
	
  // 重写 toString 方法
	@Override
	public String toString() {
		// size=3, [99, 88, 77]
		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]);
			
//			if (i != size - 1) { // 不推荐这种方式，因为多了一步减法运算
//				string.append(", ");
//			}
		}
		string.append("]");
		return string.toString();
	}
}

接口测试

在使用的时候，可以再写一个断言类来方便单元测试。

单元测试是指对软件中的最小可测试单元进行检查和验证。至于 “单元” 的大小或范围，并没有一个明确的标准，“单元” 可以是一个函数、方法、类、功能模块或者子系统。

public class Asserts {
	public static void test(boolean value) {
		try {
			if (!value) throw new Exception("测试未通过");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

设计分析

动态扩容

在上面创建的 ArrayList 文件中补充内容

	/**
	 * 在index位置插入一个元素
	 * @param index
	 * @param element
	 */
	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++;
	}	

  /**
	 * 保证要有capacity的容量
	 * @param capacity
	 */
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		if (oldCapacity >= capacity) return;
		
		// 新容量为旧容量的1.5倍
    // 右移一相当于除以2，即 1 + 1/2 = 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);
	}

泛型

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

注：使用泛型时，<> 中需写引用类型，写基本数据类型会报错

不难看出，我们上面写的 ArrayList 是有局限性的，只能存放 int 数据类型。

所以要实现动态数组，还需要用到泛型。

对象数组

一旦改成泛型之后，就会多了个对象的内存管理问题。

简单来说就是：无法确定一个数组存储空间放多少个字节。

代码解析：

Object[] objects = new object[7];

内存空间展示：

内存地址，说白了就是 xx 对象的地址值。每一个对象的内存地址大小是一样的。

为什么是存放地址？

因为这样可以节省空间。

对象数组在初始化时不会为对象分配内存，而只会为对象引用分配内存。只有在你显式创建对象并将其分配给数组元素时，才会为对象分配实际的内存。这有助于节省内存，因为不会预先分配所有对象的内存，只有在需要时才会分配。

具体概念分析：

1. 对象数组的初始化：在 Java 中，当你创建一个对象数组时，数组的每个元素都会被初始化为 null。这意味着，创建数组时并不会立即分配内存来存储对象，只有在你将对象分配给数组的元素时才会分配内存。
2. 内存分配：当你通过 new 操作符创建一个对象时，Java 会在堆内存中为该对象分配内存。这个对象的引用会存储在数组元素中。因此，数组的每个元素都是一个引用，指向堆内存中的对象。
3. 节省空间：与基本数据类型数组不同，对象数组本身并不存储对象的实际数据，而只存储对对象的引用。这可以节省内存，因为对象可能会占用大量的内存，但数组中的引用通常只需要占用相对较小的内存空间。

一个引用地址占多少字节？

在 Java 中，一个对象引用通常占用 4 个字节（32 位系统）或 8 个字节（64 位系统）。这取决于你的 Java 虚拟机和操作系统的架构。

• 在 32 位系统上，一个对象引用通常占用 4 个字节。
• 在 64 位系统上，一个对象引用通常占用 8 个字节。

内存管理细节

clear 清空

推荐的写法如下：

	/**
	 * 清除所有元素
	 */
	public void clear() {
		for (int i = 0; i < size; i++) {
			elements[i] = null;
		}
		size = 0;
	}

分析：

• 将每个元素的内存地址设置为 null，相当于切断了内存地址与对象的联系，对象没有被引用，后续就会被 JVM 垃圾回收(GC) -- 循环利用数组空间
• 将 size 设置为 0，下次再添加新元素时就会覆盖第一个元素的位置，并且不需要重新开辟数组空间

可以写下面这行代码来提醒 JVM 进行垃圾回收：

System.gc();

不推荐的写法如下：

1、是设定 size = 0

	public void clear() {
		size = 0;
	}

缺点：

• 不是实际删除对象内存占用，浪费空间，只是后续添加新元素时覆盖掉旧的内存地址，从而让旧的对象失去引用从而被回收

2、调用 remove 方法

	public void clear() {
		for (int i = 0; i < size; i++) {
			remove(i)
		}
		size = 0;
	}

缺点：

• 每次都会调用 remove 方法，而调用方法是需要开辟空间，影响性能
• 如果是正序遍历的话，还会导致每次删除，后面的元素需要往前挪，更耗费时间

3、直接将元素设置为 0

	public void clear() {
		elements = null;
	}

缺点：

• 相当于直接把数组的堆内存空间删掉，下次再使用数组时，需重新开辟空间，从而影响性能

remove 删除

	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; // 最后一个元素设置为null
		return old;
	}

循环问题

在写代码时应该养成一种能少一步运算操作就少一步运算操作的写法

		// 修改前
		for (int i = size - 1; i >= index; i--) { // 元素向后挪动
			elements[i + 1] = elements[i];
		}
		
		// 修改后
		for (int i = size; i > index; i--) {
			elements[i] = elements[i - 1];
		}

ArrayList 缩容

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

1、添加 trim() 方法

	private void trim() {
		// 30
		int oldCapacity = elements.length;
		// 15
		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;
		
		System.out.println(oldCapacity + "缩容为" + newCapacity);
	}

2、在 remove 方法中调用

	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;
	}

3、clear 清除元素的时候也需要缩容

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