动态数组
一、动态数组接口设计
// 这里可以写一个List接口,然后ArrayList类去实现这个接口,实现接口中的方法。但为了方便起见,直接将这些方法写在类中。
// 这些方法暂时不添加泛型、和正确的返回值
public class ArrayList {
// 动态数组的长度
private int size;
// 动态数组的所有元素
private int[] elements;
// 返回动态数组的长度
public int size() {
return 0;
}
// 判断动态数组是否为空
public boolean isEmpty() {
return false;
}
// 判断是否包含某个元素
public boolean contains(int element) {
return false;
}
// 添加元素到动态数组末尾
public void add(int element) {
}
// 添加元素到动态数组index索引位置
public void add(int index, int element) {
}
// 返回index索引位置对应的元素
public int get(int index) {
return 0;
}
// 删除index索引位置对应的元素,并返回所删除的元素
public int remove(int index) {
return 0;
}
// 设置index位置的元素,并返回旧值
public int set(int index, int element) {
return 0;
}
// 查看指定元素第一次出现的位置
public int indexOf(int element) {
return 0;
}
// 清除所有元素
public void claer() {
}
// 打印数组,重写toString()方法
@Override
public String toString() {
}
}
二、动态数组的设计
public class ArrayList {
// 动态数组的长度
private int size;
// 动态数组的所有元素
private int[] elements;
}
三、动态数组的构造器
// 提供一个带参构造器,创建用户输入的数组容量,若用户输入容量小于默认初始容量10,则创建10个长度的数组
// 动态数组的默认初始容量
private static final int DEFAULT_CAPACITY = 10;
public ArrayList(int capacity) {
capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
elements = new int[capacity];
}
// 提供一个空参构造器,默认数组的初始容量为10
public ArrayList() {
//elements = new int[DEFAULT_CAPACITY];
this(DEFAULT_CAPACITY);
}
四、核心操作
4.1 获取第一个元素位置:indexOf
// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(int element) {
// 遍历动态数组。注意size和elements.length的区别
for (int i = 0; i < size; i ++) {
if (elements[i] == element) {
return i;
}
}
return ELEMENT_NOT_FOUND;
}
- 注意区别size和elements.length的区别
size
表示的是当前数组元素的个数elements.length
表示的是数组的长度,也即动态数组的容量capacitysize <= elements.length
。所以在遍历动态数组的时候,一定是i < size而不是i < elements.length
。
4.2 清除元素:clear
// 清除所有元素
public void clear() {
size = 0;
}
- 为什么不写成elements=null?
- 原因是当用户执行clear()操作后,后面可能还需要使用add操作,所以数组分配的这些内存空间后面可能还需要使用。
- size = 0 的操作已经对用户来说已经无法访问动态数组中的元素了。但这数组的内存空间还在。
4.3 打印数组:toString
// 打印数组
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("size = ").append(size).append(", ").append("[");
for (int i = 0; i < size; i ++) {
if (i == size - 1) {
sb.append(elements[i]);
break;
}
sb.append(elements[i]).append(",");
}
sb.append("]");
return sb.toString();
}
- 打印引用对象,默认是调用其toString()方法
- 所以需要重写toStirng方法,在toString()方法中将元素拼接成字符串
- 字符串拼接建议使用StringBuilder
4.4 删除元素:remove
// 删除index索引位置对应的元素,并返回所删除的元素
public int remove(int index) {
// 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
}
// 保存要被删除的值
int remove = elements[index];
// 从被删除的后一个元素开始往前移动
for (int i = index + 1; i < size; i ++) {
elements[i - 1] = elements[i];
}
size --;
return remove;
}
4.5 动态数组扩容
- 需要扩容的地方:add方法
// 确保有needCapacity的容量
private void ensureCapacity(int needCapacity) {
// 当前容量为nowCapacity
int nowCapacity = elements.length;
// 当前容量大于等于所需要的容量,容量够
if (nowCapacity >= needCapacity) return;
// 容量不够,则扩容至1.5倍
int newCapacity = nowCapacity + (nowCapacity >> 1);
int[] newElements = new int[newCapacity];
// 拷贝元素
for(int i = 0; i < elements.length; i ++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println(nowCapacity + "扩容为:" + newCapacity);
}
4.6 添加元素:add
// 添加元素到动态数组末尾
public void add(int element) {
add(size, element);
}
// 添加元素到动态数组index索引位置
public void add(int index, int element) {
// // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
// if (index < 0 || index > size) {
// throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
// }
// 扩容
rangeCheckForAdd(index);
// 当前动态数组的元素个数为size,我们确保需要size+1个容量
ensureCapacity(size + 1);
for (int i = size - 1; i >= index; i --) {
elements[i + 1] = elements[i];
}
elements[index] = element;
size ++;
}
五、给动态数组添加泛型
使用泛型技术可以让动态数组更加通用,可以存放任何数据类型的数据。
public class ArrayList<E> {
// 动态数组的长度
private int size;
// 动态数组的所有元素
private E[] elements;
// 特别重要!
elements = (E[]) new Object[capacity];
}
ArrayList<Integer> list = new ArrayList<>();
elements = (E[]) new Object[capacity];
E[] newElements = (E[])new Object[newCapacity];
不能elements = new E[capacity];的原因是泛型是编译时期的,而new是运行时期的
六、内存管理细节
给动态数组添加泛型之后,考虑到内存管理细节,需要修改某些方法的内部实现。
6.1 对象数组
6.2 清空操作clear()细节
// 清除所有元素
public void clear() {
// (内存管理细节)对象内存清空,但是对象数组所分配的内存还在
for (int i = 0; i < size; i ++) {
elements[i] = null;
}
size = 0;
}
6.3 删除操作remove()细节
// 删除index索引位置对应的元素,并返回所删除的元素
public E remove(int index) {
// 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
rangeCheck(index);
// 保存要被删除的值
E remove = elements[index];
// 从被删除的后一个元素开始往前移动
for (int i = index + 1; i < size; i ++) {
elements[i - 1] = elements[i];
}
// (内存管理细节)将最后一个元素变为null
elements[size - 1] = null;
size --;
return remove;
}
6.4 indexOf()方法小细节
// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(E element) {
// 遍历动态数组。注意size和elements.length的区别
for (int i = 0; i < size; i ++) {
// 小细节 不再是 ==
if (elements[i].equals(element)) {
return i;
}
}
return ELEMENT_NOT_FOUND;
}
6.5 null值处理细节
// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(E element) {
// 遍历动态数组。注意size和elements.length的区别
// 找null。则element为空,不可以element.equals(elements[i]),直接用elements[i] == null判断
if (element == null) {
for (int i = 0; i < size; i ++) {
if (elements[i] == null) { // elements[i]为空
return i;
}
}
} else {
// 找不为null。则element不为空,可以element.equals(elements[i])
for (int i = 0; i < size; i ++) {
// 避免空指针异常
if (element.equals(elements[i])) {
return i;
}
}
}
return ELEMENT_NOT_FOUND;
}
七、最终迭代后的代码
package DataStructure._01动态数组;
/**
* @author keyongkang
* @date 2022-07-10-10:09
*/
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 capacity) {
capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
elements = (E[])new Object[capacity];
}
public ArrayList() {
//elements = new int[DEFAULT_CAPACITY];
this(DEFAULT_CAPACITY);
}
private void rangeCheck(int index) {
// 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
}
}
private void rangeCheckForAdd(int index) {
// 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
}
}
// 返回动态数组的长度
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) {
add(size, element);
}
// 添加元素到动态数组index索引位置
public void add(int index, E element) {
// // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
// if (index < 0 || index > size) {
// throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
// }
rangeCheckForAdd(index);
// 当前动态数组的元素个数为size,我们确保需要size+1个容量
ensureCapacity(size + 1);
for (int i = size - 1; i >= index; i --) {
elements[i + 1] = elements[i];
}
elements[index] = element;
size ++;
}
// 确保有needCapacity的容量
private void ensureCapacity(int needCapacity) {
// 当前容量为nowCapacity
int nowCapacity = elements.length;
// 当前容量大于等于所需要的容量,容量够
if (nowCapacity >= needCapacity) return;
// 容量不够,则扩容至1.5倍
int newCapacity = nowCapacity + (nowCapacity >> 1);
E[] newElements = (E[])new Object[newCapacity];
// 拷贝元素
for(int i = 0; i < elements.length; i ++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println(nowCapacity + "扩容为:" + newCapacity);
}
// 返回index索引位置对应的元素
public E get(int index) {
// // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
// if (index < 0 || index >= size) {
// throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
// }
rangeCheck(index);
return elements[index];
}
// 删除index索引位置对应的元素,并返回所删除的元素
public E remove(int index) {
// // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
// if (index < 0 || index >= size) {
// throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
// }
rangeCheck(index);
// 保存要被删除的值
E remove = elements[index];
// 从被删除的后一个元素开始往前移动
for (int i = index + 1; i < size; i ++) {
elements[i - 1] = elements[i];
}
// (内存管理细节)将最后一个元素变为null
elements[size - 1] = null;
size --;
return remove;
}
// 设置index位置的元素,并返回旧值
public E set(int index, E element) {
// // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
// if (index < 0 || index >= size) {
// throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
// }
rangeCheck(index);
// 保存当前索引的旧值
E old = elements[index];
// 设置index位置的新值
elements[index] = element;
return old;
}
// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(E element) {
// 遍历动态数组。注意size和elements.length的区别
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() {
//size = 0;
// (内存管理细节)对象内存清空,但是对象数组所分配的内存还在
for (int i = 0; i < size; i ++) {
elements[i] = null;
}
size = 0;
}
// 打印数组
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("size = ").append(size).append(", ").append("[");
for (int i = 0; i < size; i ++) {
if (i == size - 1) {
sb.append(elements[i]);
break;
}
sb.append(elements[i]).append(", ");
}
sb.append("]");
return sb.toString();
}
}
标签:index,elements,int,ArrayList,数组,动态,public,size
From: https://www.cnblogs.com/keyongkang/p/17880426.html