本文共 6027 字，大约阅读时间需要 20 分钟。

小码哥数据结构与算法(一): 动态数组

本篇是的学习笔记, 使用JAVA语言

一、数组(Array)

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

int[] array = new int[]{11, 22, 33}复制代码

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

实际开发中我们希望数组的容量是动态变化的

二、动态数组

• 可以通过数组实现一个动态数组, 动态数组的容量是动态变化的
• 可以对动态数组进行增删改查操作

// 元素的数量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(); 复制代码

三、动态数组的设计

• 创建类ArrayList 如下图, 创建size属性来管理数组中元素的个数, 创建elements属性来管理存取的数据

public class ArrayList
   
     {	private int size;	private E[] elements;}复制代码
   

• 添加初始化方法, 创建elements数组, 并指定elements默认的容量

public class ArrayList
   
     {	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、添加元素

• 我们知道, 每当数组添加新元素时, 都会在数组最后一个元素的后面添加新元素
• 这个新元素需要添加到的索引等于当前数组元素的个数, 在ArrayList中size属性就是当前数组元素的个数, 所以就是将新元素添加到数组的size位置上, 然后size加1

public void add(E element) {	elements[size] = element;	size++;}复制代码

2、数组扩容

• 由于数组elements最大的容量只有10, 所以当数组存满元素时, 就需要对数组进行扩容
• 因为数组是无法动态扩容的, 所以需要创建一个新的数组,这个数组的容量要比之前数组的容量大
• 然后在将原数组中的元素存放到新数组中, 这样就实现了数组的扩容

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;}复制代码

• 此时, add方法的实现如下, 在添加新元素之前, 先判断是否需要扩容

public void add(E element) {    // 添加新元素之前, 先判断是否需要扩容	ensureCapacity();	elements[size] = element;	size++;}复制代码

3、删除元素

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

public E remove(int index) {	// 取出需要删除的元素	E element = elements[index];	// 通过循环, 将index后面的所有元素向前移动一位	for (int i = index; i < size - 1; i++) {		elements[i] = elements[i + 1];	}	// 删除最后一个元素	elements[--size] = null;	// 将删除的元素返回	return element;}复制代码

• 注意: 删除元素时传入的索引不能越界, 即不能小于0, 也不能大于等于size
• 所以我们在删除元素之前需要先进行索引检查

private void rangeCheck(int index) {	if (index < 0 || index >= size) {		throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);	}}复制代码

• 此时, remove方法实现如下

public E remove(int index) {	// 判断索引是否越界	rangeCheck(index);	// 取出需要删除的元素	E element = elements[index];	// 通过循环, 将index后面的所有元素向前移动一位	for (int i = index; i < size - 1; i++) {		elements[i] = elements[i + 1];	}	// 删除最后一个元素	elements[--size] = null;	// 将删除的元素返回	return element;}复制代码

4、数组缩容

• 当数组中的元素删除后, 数组剩余的空间可能会很大, 这样就会造成内存的浪费
• 所以当数组中元素删除后, 我们需要对数组进行缩容
• 实现方法类似于扩容, 当数组中容量小于某个值时, 创建新的数组, 然后将原有数组中的元素存入新数组即可

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;}复制代码

• 每次删除元素后, 判断是否需要缩容

public E remove(int index) {	// 判断索引是否越界	rangeCheck(index);	// 取出需要删除的元素	E element = elements[index];	// 通过循环, 将index后面的所有元素向前移动一位	for (int i = index; i < size - 1; i++) {		elements[i] = elements[i + 1];	}	// 删除最后一个元素	elements[--size] = null;	// 判断数组是否需要缩容	trim();	// 将删除的元素返回	return element;}复制代码

5、清空元素

• 清空元素, 只需要将所有的元素置为null, 然后size置为0

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

6、修改元素

• 修改元素时, 只需要将原有位置的元素替换掉即可, 只是需要注意一下索引是否越界

public E set(int index, E element) {	// 判断索引是否越界	rangeCheck(index);	// 取出被替换元素	E oldElement = elements[index];	// 替换元素	elements[index] = element;	// 返回被替换元素	return oldElement;}复制代码

7、 查询元素

• 查询元素, 只需要将指定索引的元素返回, 注意索引是否越界即可

public E get(int index) {	rangeCheck(index);	return elements[index];}复制代码

8、插入元素

• 插入元素类似于删除元素, 只需要将插入位置后面的元素向后移动即可
• 注意: 需要从后向前移动元素, 如果从前向后移动元素, 那么会进行元素覆盖, 最后出错

public void add(int index, E element) {	// 从后向前的顺序, 将元素向后移动	for (int i = size - 1; i >= index; i--) {		elements[i + 1] = elements[i];	}	// 插入元素	elements[index] = element;	// size+1	size++;}复制代码

• 需要注意的是, 插入元素的索引也不能越界, 不过不同于删除和设置元素时, 插入的位置可以是所有元素的最后, 即size的位置

public void rangeCheckForAdd(int index) {	// 当索引小于0 或 大于 size时 抛出异常	if (index < 0 || index > size) {		throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);	}}复制代码

• 此时, add方法如下

public void add(int index, E element) {	// 检查索引是否越界	rangeCheckForAdd(index);	// 从后向前的顺序, 将元素向后移动	for (int i = size - 1; i >= index; i--) {		elements[i + 1] = elements[i];	}	// 插入元素	elements[index] = element;	// size+1	size++;}复制代码

9、查看元素位置

• 可以通过循环, 查找元素在数组中的位置
• 注意: 数组中可以存储null, 而null是不能调用equals方法的, 所以需要对传入的元素进行判断, 如果查找的元素是null, 需要单独处理
• 当元素存在时返回索引, 否则返回变量ELEMENT_ON_FOUND的值

private static final int ELEMENT_ON_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_ON_FOUND;}复制代码

10、是否包含某个元素

• 当元素存在时, 只需要判断索引是否等于ELEMENT_ON_FOUND即可

public boolean contains(E element) {	// 查看元素的索引是否为ELEMENT_ON_FOUND即可	return indexOf(element) != ELEMENT_ON_FOUND;}复制代码

11、元素的数量

• 数组元素的数量, 就是size的值

public int size() {	return size;}复制代码

12、数组是否为空

• 判断size的值是否为0即可

public boolean isEmpty() {	return size == 0;}复制代码

13、动态数组打印

• 可以重写toString方法, 来打印ArrayList中的元素

@Overridepublic 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();}

转载地址：https://javaedge.blog.csdn.net/article/details/104489125 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！