数据结构与算法(一): 动态数组
【摘要】 小码哥数据结构与算法(一): 动态数组
本篇是恋上数据结构与算法（第一季）的学习笔记, 使用JAVA语言
一、数组(Array)
数组是一种顺序存储的线性表,所有元素的内存地址都是连续的
int[] array = new int[]{11, 22, 33}复制代码
在很多编程语言中, 数组有个致命的...
小码哥数据结构与算法(一): 动态数组
本篇是恋上数据结构与算法（第一季）的学习笔记, 使用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<E> {
-
private int size;
-
private E[] elements;
-
}
-
复制代码
- 添加初始化方法, 创建
elements数组, 并指定elements默认的容量
-
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、添加元素
- 我们知道, 每当数组添加新元素时, 都会在数组最后一个元素的后面添加新元素
- 这个
新元素需要添加到的索引等于当前数组元素的个数, 在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中的元素
-
@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();
-
}
文章来源: javaedge.blog.csdn.net，作者：JavaEdge.，版权归原作者所有，如需转载，请联系作者。
原文链接：javaedge.blog.csdn.net/article/details/104489125
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）