Version: Next

动态数组接口设计

定义

Java：在堆中申请的连续内存空间

  • int size() 元素的数目
  • boolean isEmpty() 是否为空
  • boolean contains(E element) 是否包含某个元素
  • void add(E element) 添加一个元素到最后面
  • E get(int index) 返回index位置对应的元素
  • E set(int index, E element) 设置Index位置的元素
  • void add(int index, E element) 向index位置插入一个元素
  • E remove(int index) 移除index位置的元素并返回
  • int indexOf(E element) 查看元素的位置
  • void clear() 清除所有元素

动态数组的成员变量

  • int size 元素个数
  • int[] elements 元素数组
private int size; // 数目
private int[] elements; // 元素数组
private static final int DEFAULT_CAPACITY = 10;

构造方法

可以指定初始容量，也可以不指定，采用默认初始容量

如果指定容量小于默认容量，默认按照默认大小初始化数组

//构造方法
public MyArrayList(int capacity) {
capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
elements = new int[capacity];
}
public MyArrayList() {
this(DEFAULT_CAPACITY);
}

toString方法

@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("MyArrayList{")
.append(size)
.append(", elements=");
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(elements[i]);
if (i != size - 1) stringBuilder.append(" ,");
}
stringBuilder.append("]");
stringBuilder.append("}");
return stringBuilder.toString();
}

isEmpty方法

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

get方法

// 返回index位置对应的元素
public int get(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index:" + index + " | size:" + size);
return elements[index];
}

时间复杂度分析：数组连续内存地址寻址，复杂度为O(1)

set方法

// 设置Index位置的元素
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;
}

indexOf方法

// 查看元素的位置
public int indexOf(int element) {
for (int i = 0; i < size; i++) {
if (elements[i] == element)
return i;
}
return -1;
}

复杂度O(1)

contains方法

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

clear方法

// 清除所有元素
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
  • 考虑缩容
// 清除所有元素
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];
}

add方法

在数组尾部添加一个元素

  • 尾部的下标正好等于size的值
// 添加一个元素到最后面
public void add(int element) {
elements[size++] = element;
}
info

可以根据add(int index, E element)方法进行重构

// 添加一个元素到最后面
public void add(int element) {
// elements[size++] = element;
add(size, element);
}

  • 时间复杂度：永远在数组的最后面添加

    • 最好情况，直接在末尾添加，O(1)

    • 最差情况，在末尾添加时出发了数组扩容：创建新数组，旧数组遍历复制到新数组 O(n)

    • 平均复杂度：n-1个O(1)，和1个O(n) -> [(n-1) + n] / n = (2n-1) / n -> 极限 -> 2n /n = 2 -> O(1)

    • 均摊复杂度：O(1)将最后扩容那一次的时间开销分摊到每一次操作中去

      • 未触发扩容时每次执行复杂度为O(1)，共n-1次
      • 触发扩容时复杂度为O(n)
      • 将O(n)分摊到n-1次O(1)上去
      • 大致为每次操作O(2) 即复杂度为O(1)

  • 使用均摊复杂度的场景：连读大量复杂度很低的操作后，突然出现少量复杂度较高的操作

remove方法

  • 记录被删除的元素的值
  • 所有后面的元素向前移动
  • size--
// 移除index位置的元素并返回
public int remove(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index:" + index + " | size:" + size);
int removedElement = elements[index];
for (int i = index + 1; i <= size - 1; i++) {
elements[i - 1] = elements[i];
}
size--;
return removedElement;
}
public static void main(String[] args) {
MyArrayList list = new MyArrayList();
list.add(11);
list.add(22);
list.add(33);
int removed = list.remove(0);
System.out.println(list);
System.out.println("removed = " + removed);
}
MyArrayList{2, elements=[22 ,33]}
removed = 11
  • 时间复杂度——与添加方法同理，时间复杂度为O(n)

add(int index, E element)方法

在指定索引位置添加元素

  • 倒着挪动，从size-1挪动到size
  • size-2挪动到size-1
  • 一共挪动size - index 次
  • 挪动范围 [index, size-1]
// 向index位置插入一个元素
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++;
}

  • 时间复杂度：数据规模为n，此处数据规模取决于size

    • 最好情况复杂度 index = size

      在最后添加一个元素，直接寻址到追后面，不需要元素的移动，O(1)

    • 最差情况复杂度 移动size次

      插在最前面，后面的所有元素都需要移动，O(n)

    • 平均复杂度

      [O(1) + O(2) + ... + O(n)] / n = (n + 1)n / n ， 当 n->无穷 ，等于 n^2 / n = n

      O(n)

下标越界检查函数

private void outOfBoundsException(int index) {
throw new IndexOutOfBoundsException("Index:" + index + " | size:" + size);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
outOfBoundsException(index);
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
outOfBoundsException(index);
}

扩容

  1. 申请一段新的内存空间
  2. 将原数组的内容复制过来
  3. 将引用指向新数组
  4. 垃圾回收机制自动回收旧数组
info

在添加时判断是否扩容

  • 根据elements数组的长度得到现在的容量
  • 如果现在的容量大于指定的容量，则扩容函数直接返回
  • 否则扩容，申请新数组，大小为旧数组的1.5倍
  • 将旧数组的值复制到新数组中（不考虑线程安全）
  • 将引用指向新数组，旧数组被垃圾回收器回收
/**
* 保证要有capacity的容量
*
* @param capacity 指定容量
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity > capacity) return;
// 右移一位相当于/2 ， 再加上原值，等于原值的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 建立新数组
int[] newElements = new int[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
// 引用指向新数组
System.out.format("扩容了，旧容量: %s | 新容量：%s \n", oldCapacity, newCapacity);
elements = newElements;
}

在add方法前，添加扩容方法，指定的确保容量为size + 1

// 向index位置插入一个元素
public void add(int index, int element) {
rangeCheckForAdd(index);
// 扩容
ensureCapacity(size + 1);
for (int i = size - 1; i >= index; i--) {
elements[i + 1] = elements[i];
}
elements[index] = element;
size++;
}

执行测试

test
public static void main(String[] args) {
MyArrayList list = new MyArrayList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
System.out.println(list);
}
扩容了，旧容量: 10 | 新容量：15
MyArrayList{12, elements=[0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11]}

缩容

和扩容类似，还是开辟新的数组空间

  • 在remove方法执行期间，考虑对数组进行缩容
  • 在clear方法执行期间，考虑对数组进行缩容
  • 缩容触发条件（自己定义）：SIZE为总容量（数组的length）的一半时，就进行缩容
    • 要求当前容量不能比默认容量小，否则缩到很小后，频繁触发扩容缩容影响效率
  • 确定新数组的容量
/**
* 缩容
*/
private void trim() {
int capacity = elements.length;
int newCapacity = capacity >> 1;
// size 大于 容量的一半 或 容量小于等于默认容量，不需要缩容
if (size > newCapacity || capacity <= DEFAULT_CAPACITY) return;
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
System.out.format("缩容了，旧容量: %s | 新容量：%s \n", capacity, newCapacity);
elements = newElements;
}
  • 测试
public static void main(String[] args) {
MyArrayList<Integer> list = new MyArrayList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
for (int i = 0; i < 7; i++) {
list.remove(0);
}
System.out.println(list.toString());
}
扩容了，旧容量: 10 | 新容量：15
缩容了，旧容量: 15 | 新容量：7
MyArrayList{5, elements=[7 ,8 ,9 ,10 ,11]}

泛型

定义并使用泛型的步骤
  1. 在类后面指定泛型 class MyArrayList<E>
  2. 类中方法的返回类型都可以写成E
  3. 泛型类型的数组通过Object类型在堆内存中申请，再强转成需要的类型
对象数组的存储方式

对象数组中存储的不是对象本身，而是对象在堆中的地址值

修改clear方法适应泛型

为什么需要修改

如果不做处理，那么对象的地址存在对象数组中，却没有人用，但引用是实实在在存在的，那么就造成了内存泄漏

  • 应当将对象数组的全部位置设置为null
// 清除所有元素
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
查看对象被垃圾回收器回收

可以重写类的finalize()方法，该方法在对象即将被销毁时被调用

  • 通过System.gc()，主动触发垃圾回收

修改remove方法适应泛型

为什么要修改

执行remove方法时，进行了元素的移动，在数组的尾部空出了一个空间，需要对其进行处理，否则会产生内存泄漏

// 移除index位置的元素并返回
public E remove(int index) {
rangeCheck(index);
E removedElement = elements[index];
for (int i = index + 1; i <= size - 1; i++) {
elements[i - 1] = elements[i];
}
// 将最后一个位置设置为null，防止内存泄漏
size--;
elements[size] = null;
return removedElement;
}

修改indexOf方法适应泛型

为什么修改

在原先的indexOf方法中，通过==判断传入的值与数组中的值是否相等，在泛型下，传入的参数可能为引用类型，也就是可能是一个对象，对象间的判等不能使用==来进行，因为==判断的是对象的地址，两个各种属性一致的对象可能具有不同的地址从而被==判断为不相等

  • 应当使用equls()方法来进行判等，可以通过重写来自定义判断的方式
// 查看元素的位置
public int indexOf(E element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element))
return i;
}
return ELEMENT_NOT_FOUND;
}

修改indexOf方法适应null值的搜索

为什么修改

因为如果数组中存储了null，在调用equals方法是会引发空指针异常

// 查看元素的位置
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;
}
}
return ELEMENT_NOT_FOUND;
}

完整代码

public class MyArrayList<E> {
private int size; // 数目
private E[] elements; // 元素数组
private static final int DEFAULT_CAPACITY = 10;
private static final int ELEMENT_NOT_FOUND = -1;
//构造方法
public MyArrayList(int capacity) {
capacity = capacity < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity;
elements = (E[]) new Object[capacity];
}
public MyArrayList() {
this(DEFAULT_CAPACITY);
}
// 元素 g的数目
public int size() {
return size;
}
// 是否为空
public boolean isEmpty() {
return size == 0;
}
// 是否包含某个元素
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
// 添加一个元素到最后面
public void add(E element) {
// elements[size++] = element;
add(size, element);
}
// 返回index位置对应的元素
public E get(int index) {
rangeCheck(index);
return elements[index];
}
// 设置Index位置的元素
public E set(int index, E element) {
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
// 向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++;
}
// 移除index位置的元素并返回
public E remove(int index) {
rangeCheck(index);
E removedElement = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
// 将最后一个位置设置为null，防止内存泄漏
size--;
elements[size] = null;
return removedElement;
}
// 查看元素的位置
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;
}
}
return ELEMENT_NOT_FOUND;
}
// 清除所有元素
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("MyArrayList{")
.append(size)
.append(", elements=");
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(elements[i]);
if (i != size - 1) stringBuilder.append(" ,");
}
stringBuilder.append("]");
stringBuilder.append("}");
return stringBuilder.toString();
}
private void outOfBoundsException(int index) {
throw new IndexOutOfBoundsException("Index:" + index + " | size:" + size);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
outOfBoundsException(index);
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
outOfBoundsException(index);
}
/**
* 保证要有capacity的容量
*
* @param capacity 指定容量
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity > capacity) return;
// 右移一位相当于/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];
}
// 引用指向新数组
System.out.format("扩容了，旧容量: %s | 新容量：%s \n", oldCapacity, newCapacity);
elements = newElements;
}
}