• 【恋上数据结构与算法】理论 二：动态数组

    版权声明：本文为博主原创文章，未经博主允许不得转载。

    文章目录

    一、动态数组：Dynamic Array

    1.1 数组

    • 数组是一种顺序存储的线性表, 所有元素的内存地址都是连续的
    int[] array = new int[]{11, 22, 33}

    • 1

    在这里插入图片描述

    • 很多编程语言中，数组有个致命的缺点， 无法动态修改容量
    • 实际开发中我们希望数组的容量是动态变化的

    1.1.1 泛型

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

    1.1.2 对象数组

    在这里插入图片描述

    1.2 动态数组接口设计

    • 创建 ArrayList 类，创建 size 属性来管理数组中元素的个数， 创建 elements 属性来管理存取的数据
    • 可以对动态数组进行 增删改查 操作

    在这里插入图片描述

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

    // 元素的数量
    int size(); 
    // 是否为空
    boolean isEmpty();
    // 是否包含某个元素
    boolean contains(E element); 
    // 添加元素到最后面
    void add(E element); 
    // 返回index位置对应的元素
    E get(int index); 
    // 设置index位置的元素
    E set(int index, E element); 
    // 往index位置添加元素
    void add(int index, E element); 
    // 删除index位置对应的元素 
    E remove(int index); 
    // 查看元素的位置
    int indexOf(E element); 
    // 清除所有元素
    void clear(); 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    1.3 动态数组的实现

    1.3.1 构造方法

    • 如果构建的数组空间小于默认空间，则会以默认空间构建数组
    public class ArrayList<E> {
    private int size;
    private E[] elements;
    // 设置elements数组默认的初始化空间
    private static final int CAPACITY_DEFAULT = 10;
	
    public ArrayList(int capacity) {
        capacity = capacity < CAPACITY_DEFAULT ? CAPACITY_DEFAULT : capacity;
        elements = (E[]) new Object[capacity];
    }
	
    // 便利构造器
    public ArrayList() {
        this(CAPACITY_DEFAULT);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    1.3.2 添加元素

    • 数组添加元素分为 在最后一个元素的后面添加新元素 和 将元素插入到某个位置（非最后面） 两种情况

    1.3.2.1 第一种情况

    • 这个新元素需要添加到的索引等于当前数组元素的个数，在 ArrayList 中 size 属性就是 当前数组元素的个数，所以就是将新元素添加到数组的size位置上，然后 size加 1

    在这里插入图片描述

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

    • 1
    • 2
    • 3
    • 4

    1.3.2.2 第二种情况

    • 只需要将插入位置后面的元素 向后移动 即可
    • 注意：元素移动顺序：需要从后向前移动元素，如果从前向后移动元素，那么会进行元素覆盖, 最后出错

    在这里插入图片描述

    1.3.2.3 数组越界

    • 添加元素，还要注意传入的索引不能越界，即不能小于0, 也不能大于size
    private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size) {
        outOfBounds(index);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5

    1.3.2.4 数组扩容

    • 由于数组 elements 最大的容量只有 10，所以当数组存满元素时，就需要对数组进行扩容
    • 因为数组是无法动态扩容的，所以需要创建一个 新的数组，这个数组的容量要比之前数组的容量大
    • 然后再将原数组中的元素存放到新数组中，这样就实现了数组的扩容，原来数组自动销毁（被垃圾回收）

    在这里插入图片描述

    //length： 容量（空间长度 / 个数），size：空间中元素的个数

private void ensureCapacity() {
    // 获取数组当前容量
    int oldCapacity = elements.length;
    // 如果 当前存储的元素个数 < 当前数组容量, 直接返回
    if (size < oldCapacity) 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 实现add函数，需要在添加新元素之前，判断数组越界和扩容
    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++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 最终在最后一个元素的后面添加新元素，即添加元素到尾部的实现方式如下
    public void add(E element) {
    add(size, element);
}

    • 1
    • 2
    • 3

    1.3.3 删除元素

    • 删除元素，实际上就是去掉 指定位置的元素，并将后面的元素 向前移动
    • 如下图，当删除索引为 3 的元素时，只需要将后面的元素向前移动，然后在去掉最后一个元素，size 减 1即可

    在这里插入图片描述

    1.3.3.1 数组越界

    • 删除元素时传入的索引不能越界，即 不能小于0，也不能大于等于 size
    • 所以我们在删除元素之前需要先进行索引检查
    private void outOfBounds(int index) {
    throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
	
private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        outOfBounds(index);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    1.3.3.2 数组缩容

    • 当数组中的元素删除后，数组剩余的空间可能会很大，这样就会造成 内存的浪费
    • 所以当数组中元素删除后，我们需要对数组进行 缩容
    • 实现方法类似于扩容，当数组中容量小于某个值时，创建新的数组，然后将原有数组中的元素 存入新数组
      即可
    public void trim() {
    // 获取当前数组的容量
    int capacity = elements.length;
    // 当size大于等于容量的一半, 或则容量已经小于默认容量(10)时, 直接返回
    if (size >= capacity >> 1 || capacity < CAPACITY_DEFAULT) return;
    // 计算新的容量 = 原有容量的一半
    int newCapacity = capacity >> 1;
    // 创建新数组
    E[] newElements = (E[]) new Object[newCapacity];
    // 将原数组元素存入新数组
    for (int i = 0; i < size; i++) {
    	newElements[i] = elements[i];
    }
    // 引用新数组
    elements = newElements;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 最终 remove 方法实现如下
    public E remove(int index) {
    // 判断索引是否越界
    rangeCheck(index);
    // 取出需要删除的元素
    E old = elements[index];
    // 通过循环, 将index后面的所有元素向前移动一位
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    // 删除最后一个元素
    elements[--size] = null;
    // 判断数组是否需要缩容
    trim();
    // 将删除的元素返回
    return old;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    1.3.4 清空数组

    • 清空数组时，需要将所有的元素置为 null ，只有这样才能真正的释放对象，然后 size 置为 0

    在这里插入图片描述

    public void clear() {
    // 清空存储的数据
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    // 将size置为0
    size = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    1.3.5 修改元素

    • 修改元素时，只需要将原有位置的元素 替换 掉即可，同样需要注意一下索引是否 越界
    public E set(int index, E element) {
    // 判断索引是否越界
    rangeCheck(index);
    // 取出被替换元素
    E oldElement = elements[index];
    // 替换元素
    elements[index] = element;
    // 返回被替换元素
    return oldElement;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    1.3.6 查询元素

    • 查询元素，只需要将指定索引的元素返回，注意索引是否 越界 即可
    public E get(int index) {
    rangeCheck(index);
    return elements[index];
}

    • 1
    • 2
    • 3
    • 4

    1.3.7 查看元素位置

    • 可以通过循环, 查找元素在数组中的位置
    • 注意：假如数组中可以存储 null ，而 null 是不能调用 equals 方法的，所以需要对传入的元素进行判断，如果查找的元素是 null ，需要单独处理
    • 当元素存在时返回索引，否则返回变量 ELEMENT_ON_FOUND 的值
    private static final int ELEMENT_NOT_FOUND = -1;
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    1.3.8 是否包含某元素

    • 只需通过判断索引是否等于 ELEMENT_ON_FOUND 即可
    public boolean contains(E element) {
    // 查看元素的索引是否为ELEMENT_ON_FOUND即可
    return indexOf(element) != ELEMENT_ON_FOUND;
}

    • 1
    • 2
    • 3
    • 4

    1.3.9 元素的数量

    • size 的值，即为元素的数量
    public int size() {
    return size;
}

    • 1
    • 2
    • 3

    1.3.10 数组是否为空

    • 通过判断 size 的值是否为 0 即可
    public boolean isEmpty() {
    return size == 0;
}

    • 1
    • 2
    • 3

    1.3.11 动态数组打印

    • 可以重写 toString 方法，来打印 ArrayList 中的元素
    @Override
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();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    1.4 动态数组的复杂度

    在这里插入图片描述

    1.5 ArrayList 能否进一步优化？

    在这里插入图片描述

    • 在ArrayList中，如果要删除索引 0 位置的元素，则需要将索引 0 之后的元素全部往前移一位
    • 如果要在索引 0 位置添加元素，也需要将索引 0 及之后的元素全部往后移一位

    在这里插入图片描述

    • 在ArrayList中增加一个记录首元素位置的属性
    • 删除索引 0 位置的元素，我们只需要将 first 属性改为 1
    • 在索引 0 位置添加元素，则只需要将 first 属性改为0

    在这里插入图片描述

    • 如果继续往前插入元素，则将插入的元素存放在索引 8 这个位置，并将 first 改为8
    • 当要获取索引 8 下一个元素时，对索引取 摩，则拿到索引 0 位置的元素
      在这里插入图片描述
    • 如果插入元素，则可选择挪动前半段数据或后半段数据
    • 在索引 2 处插入元素 99 ，可以选择将元素 22 ， 33 左移，然后插入 99 即可
    • 扩容 和 缩容 同样可以优化

    1.6 完整代码

    1.6.1 Main.java

    package com.mj;


public class Main {

	public static void main(String[] args) {
		ArrayList<Object> list  = new ArrayList<>();
		list.add(10);
		list.add(new Person(10, "Jack"));
		list.add(22);
		
		list.indexOf(new Person(10, "Jack"));
		
		
//		ArrayList<Object> persons  = new ArrayList<>();
//		persons.add(new Person(10, "Jack"));
//		persons.add(null);
//		persons.add(new Person(15, "Rose"));
//		persons.add(null);
//		persons.add(new Person(12, "James"));
//		persons.add(null);
//
//		System.out.println(persons.indexOf(null));
	}

	static void test() {
		// int -> Integer
	
		// 所有的类，最终都继承java.lang.Object

		// new是向堆空间申请内存
		ArrayList<Person> persons  = new ArrayList<>();
		persons.add(new Person(10, "Jack"));
		persons.add(new Person(12, "James"));
		persons.add(new Person(15, "Rose"));
		persons.clear();
		persons.add(new Person(22, "abc"));
		
		System.out.println(persons);
		ArrayList<Integer> ints  = new ArrayList<>();
		ints.add(10);
		ints.add(10);
		ints.add(22);
		ints.add(33);
		System.out.println(ints);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    1.6.2 ArrayList.java

    package com.mj;

@SuppressWarnings("unchecked")
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;
	}

	/**
	 * 元素的数量
	 * @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) {
		rangeCheck(index);
		return elements[index];
	}

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

	/**
	 * 在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++;
	}

	/**
	 * 删除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;
	}

	/**
	 * 查看元素的索引
	 * @param element
	 * @return
	 */
	public int indexOf(E element) {
		if (element == null) {  // 1
			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倍
		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);
		}
	}
	
	@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();
	}
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210

    1.6.3 Asserts.java 接口测试

    package com.mj;

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


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    1.6.4 Person.java

    package com.mj;

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 + "]";
	}
	
	@Override
	protected void finalize() throws Throwable {
		super.finalize();
		
		System.out.println("Person - finalize");
	}
	
	@Override
	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;
	}
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    1.6.5 Car.java

    package com.mj;

public class Car {

}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    版权声明：本文为博主原创文章，未经博主允许不得转载。
  • 相关阅读:
    塑料工厂5G智能制造数字孪生可视化平台，推进塑料行业数字化转型
    墨者学院——登录密码重置漏洞分析溯源
    大学阶段总结
    WebRTC系列--track的set_enabled详解
    如何做好项目管理？年薪百万项目大佬一直在用这11张图
    dnmp一键部署搞定的php开发环境基于Docker的LNMP一键安装程序
    8086，8088CPU管脚，奇偶地址体， ready信号，reset复位信号。规则字和非规则字
    K8S：pod集群调度及相关操作
    ZYNQ上的简单 FSK 基带发射器
    JavaFX Scene Builder Menu 控件详解
  • 原文地址：https://blog.csdn.net/InitialHeart2021/article/details/125424190