数组(Array)
- 数组是一种顺序存储的线性表，所有元素的内存地址是连续的；
自定义数组的接口设计
- 要想实现一个数组的基本功能，通常情况下需要包含以下接口：
- 数组中元素的数量；
- 存储元素的集合；
- 添加元素至尾部；
- 往指定index下标位置插入元素；
- 返回指定index下标对应的元素；
- 删除指定index下标位置的元素；
- 清除所有元素；
- 设置指定index下标位置的元素，会将之前的元素覆盖，并返回之前的元素；
- 根据元素获取其index下标；
- 获取指定index下标的元素；
- 判断数组是否为空；
- 判断数组是否包含某个元素。
- 上面所列出的所有功能接口，适用于所有的编程语言，这是一种编程的思想，可以使用不同的语言将其实现，以后会考虑用OC语言再实现一遍；
- 下面我们使用Java语言，自定义一个数组，由于缺乏Java的基础知识，目前仅实现操作基础数据类型int的数组，代码实现如下：
package com.example.dynamicarray.ArrayList;
import java.util.Arrays;
public class YYArrayList {
/**
* 元素的数量
*/
private int size;
/**
* 存储所有元素的集合
*/
private int[] elements;
/**
* 存储元素的默认长度
*/
private static final int DEFAULT_CAPACITY = 2;
/**
* 目标元素不存在,返回的默认下标index
*/
private static final int ELEMENT_NOT_FOUND = -1;
public YYArrayList(){
//构造函数之间的调用 用到this关键字
this(DEFAULT_CAPACITY);
}
/**
* 自定义构造方法
* @param capaticy 存储元素的长度
*/
public YYArrayList(int capaticy){
capaticy = capaticy < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capaticy;
//申请内存空间
elements = new int[capaticy];
}
/**
* 返回数组元素的数量
*/
public int size(){
return size;
}
/**
* 往数组添加目标元素
* @param element 目标元素
*/
public void addObject(int element){
insertObjectAtIndex(size,element);
}
/**
* 在指定index位置插入元素
* @param index
* @param element
*/
public void insertObjectAtIndex(int index,int element){
if (index < 0 || index > size){
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
//检测是否需要进行扩容
ensureCapacity(size + 1);
for (int i = size - 1;i >= index;i--){
elements[i+1] = elements[I];
}
elements[index] = element;
size++;
}
/**
* 删除指定index位置的元素,且返回被删除的元素
* @param index
* @return
*/
public int removeObjectAtIndex(int index){
if (index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
int old = elements[index];
for (int i = index + 1;i <= size - 1;i++){
elements[i-1] = elements[I];
}
size--;
return old;
}
/**
* 清除所有元素
*/
public void clear(){
//将数组的size直接置为0,就不能访问数组中的元素,相当于清空数组
size = 0;
}
/**
* 设置指定index位置的元素,且返回原来的元素
* @param index 指定下标
* @param element 新元素
* @return 原来的元素
*/
public int setObjectAtIndex(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;
}
/**
* 查询元素的index下标
* @param element
* @return
*/
public int indexOfObject(int element){
for (int i = 0;i < size;i++){
if (elements[i] == element) return I;
}
return ELEMENT_NOT_FOUND;
}
/**
* 获取指定index下标的元素
* @param index 指定下标
* @return 目标元素
*/
public int objectAtIndex(int index){
//下标检测,不符合时抛出异常
if (index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
return elements[index];
}
/**
* 判断数组是否为空
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 判断是否包含某个元素
* @param element 目标元素
* @return
*/
public boolean containsObject(int element){
//判断目标元素的index是否存在
return indexOfObject(element) != ELEMENT_NOT_FOUND;
}
@Override
public String toString() {
StringBuffer string = new StringBuffer();
string.append("size=").append(size).append(", [");
for (int i = 0;i < size;i++){
string.append(elements[I]);
if (i != size - 1){
string.append(", ");
}
}
string.append("]");
return string.toString();
}
/**
* 保证要有capacity的容量 -- 涉及数组的扩容
* @param capacity
*/
private void ensureCapacity(int capacity){
int oldCapacity = elements.length;
//不需要扩容
if (oldCapacity >= capacity) return;;
//需要进行数组的扩容,新的容量大小是原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >>1);
//重新申请内存空间
int[] newElements = new int[newCapacity];
//将原来内存空间上的元素赋值到新开辟的内存空间中
for (int i = 0;i < size;i++){
newElements[i] = elements[I];
}
elements = newElements;
System.out.println(oldCapacity + "扩容为" + newCapacity);
}
}
- 首先size属性，是描述数组中元素的个数；
- elements属性，是专门用来存储数据元素的集合，需要进行初始化；
-
DEFAULT_CAPACITY是存储数据元素集合的默认容量， -
ELEMENT_NOT_FOUND当目标元素不存在,返回的默认下标index=-1； -
YYArrayList()与YYArrayList(int capaticy)是自定义数组YYArrayList的构造方法，这里涉及到方法重载的技术； -
public int size()：返回数组中的元素个数； -
public void addObject(int element)：往数组中添加一个元素，内部调用public void insertObjectAtIndex(int index,int element)函数，在数组末尾添加一个元素； -
public void insertObjectAtIndex(int index,int element)：往数组指定index位置插入一个元素；首先对index进行了检测，然后因为每次添加元素时，有可能数组的初始容量不够用，需要对数组容量进行扩容，才能加入新的元素，内部调用private void ensureCapacity(int capacity)，在index位置插入了一个新元素，那么index位置之后的直到数组末尾的元素都要向后移动一个单位；最后数组的长度size+1； -
public int removeObjectAtIndex(int index)：移除指定index位置的元素且将移除元素返回；首先对index进行了检测；然后删除指定index位置的元素，那么index位置之后的直到数组末尾的元素都要向前移动一个单位；最后数组的长度size-1； -
public void clear()：清空数组元素，因为数组中存储的是基本数据类型int，不涉及内存管理，直接数组size属性置为0即可，size置为0，外界就无法访问数组中元素了，因为涉及index都做了检测处理； -
public int setObjectAtIndex(int index,int element)：设置指定index位置的元素，就是替换元素，首先对index进行了检测，然后替换，最后然后被替换的原来的元素； -
public int indexOfObject(int element)：查询元素的index下标，遍历数组，找到目标元素，返回index下标； -
public int objectAtIndex(int index)：获取指定index位置的元素，首先对index进行了检测，然后直接返回目标元素； -
public boolean isEmpty()：判断数组元素是否为空，直接判断size是否为0即可； -
public boolean containsObject(int element)：判断数组是否包含某个元素，内部直接调用public int indexOfObject(int element)函数，通过是否存在index，来判断是否存在元素； -
public String toString()：重写打印方法； -
private void ensureCapacity(int capacity)：数组扩容保证数组容量足够能加入新的元素；首先数组已经存储的元素个数(length)与当前数组容量(oldCapacity)进行比较，若oldCapacity>=length表明数组容量足够，不需要扩容；否则需要进行数组扩容：- 确定新的容量newCapacity其大小是原来的1.5倍；
- 重新创建一个以新的容量newCapacity的数组newElements，申请内存空间；
- 循环遍历将原来内存空间上的元素赋值到新开辟的内存空间中；
- 将数组的存储集合elements指向新的数组newElements；
- 外界测试代码：
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
YYArrayList array = new YYArrayList();
array.addObject(10);
array.addObject(20);
array.addObject(30);
array.addObject(40);
array.addObject(50);
Log.d("MainActivity",array.toString());
array.removeObjectAtIndex(3);
Log.d("MainActivity",array.toString());
array.insertObjectAtIndex(3,88);
Log.d("MainActivity",array.toString());
array.setObjectAtIndex(3,99);
Log.d("MainActivity",array.toString());
int index = array.indexOfObject(50);
Log.d("MainActivity","50的index下标 = " + index);
int element = array.objectAtIndex(1);
Log.d("MainActivity","index = 1的元素为:" + element);
}
- 打印结果：
Snip20210330_65.png
- 上面自定义的数组YYArrayList，实现了操作int类型的基本功能，但是局限性很大，只能操作int，现在使用泛型这项技术，将其改造成操作任意对象的数组；
- 改造之后在代码如下：
package com.example.dynamicarray.ArrayList;
public class YYArrayList <E> {
/**
* 元素的数量
*/
private int size;
/**
* 存储所有元素
*/
private E[] elements;
/**
* 存储元素的默认长度
*/
private static final int DEFAULT_CAPACITY = 2;
/**
* 目标元素不存在,返回的默认下标index
*/
private static final int ELEMENT_NOT_FOUND = -1;
public YYArrayList(){
//构造函数之间的调用 用到this关键字
this(DEFAULT_CAPACITY);
}
/**
* 自定义构造方法
* @param capaticy 存储元素的长度
*/
public YYArrayList(int capaticy){
capaticy = capaticy < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capaticy;
//申请内存空间
elements = (E[])new Object[capaticy];
}
/**
* 返回数组元素的数量
*/
public int size(){
return size;
}
/**
* 往数组添加目标元素
* @param element 目标元素
*/
public void addObject(E element){
insertObjectAtIndex(size,element);
}
/**
* 在指定index位置插入元素
* @param index
* @param element
*/
public void insertObjectAtIndex(int index,E element){
if (element == null) return;
if (index < 0 || index > size){
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
//检测是否需要进行扩容
ensureCapacity(size + 1);
for (int i = size - 1;i >= index;i--){
elements[i+1] = elements[I];
}
elements[index] = element;
size++;
}
/**
* 删除指定index位置的元素,且返回被删除的元素
* @param index
* @return
*/
public E removeObjectAtIndex(int index){
if (index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
E old = elements[index];
for (int i = index + 1;i <= size - 1;i++){
elements[i-1] = elements[I];
}
elements[--size] = null;
return old;
}
/**
* 清除所有元素
*/
public void clear(){
//将数组中对象地址全部清空 -- 对象回收
//数组没有回收,可循环使用
for (int i = 0; i < size;i++){
elements[i] = null;
}
size = 0;
}
/**
* 设置指定index位置的元素,且返回原来的元素
* @param index 指定下标
* @param element 新元素
* @return 原来的元素
*/
public E setObjectAtIndex(int index,E element){
if (index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
E old = elements[index];
elements[index] = element;
return old;
}
/**
* 获取指定index下标的元素
* @param index 指定下标
* @return 目标元素
*/
public E objectAtIndex(int index){
//下标检测,不符合时抛出异常
if (index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
return elements[index];
}
/**
* 查询元素的index下标
* @param element
* @return
*/
public int indexOfObject(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 (elements[i].equals(element)) return I;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 判断数组是否为空
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 判断是否包含某个元素
* @param element 目标元素
* @return
*/
public boolean containsObject(E element){
//判断目标元素的index是否存在
return indexOfObject(element) != ELEMENT_NOT_FOUND;
}
@Override
public String toString() {
StringBuffer string = new StringBuffer();
string.append("size=").append(size).append(", [");
for (int i = 0;i < size;i++){
string.append(elements[I]);
if (i != size - 1){
string.append(", ");
}
}
string.append("]");
return string.toString();
}
/**
* 保证要有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);
}
}
-
public class YYArrayList <E>其中<E>就是泛型，在设计YYArrayList数组的时候由于使用泛型这项技术，使得YYArrayList可以存储任意对象类型的数据元素，只有当真正使用YYArrayList的时候才去确定存储元素的类型； - 在涉及元素类型的地方全部替换成泛型<E>
-
定义存储集合 private E[] elements与elements = (E[])new Object[capaticy]其中Object类在Java中是所有类的基类，用Object来定义数组则数组能存储任意对象类型的元素，最后做了一个 (E[])强制类型转换，要与声明定义的数组类型保持一致； public class YYArrayList <E>-
public void clear()：清除元素，需要做改动，因为我们现在存储的是对象类型的元素，这就涉及到对象的内存管理，详细原理见附件1；所以需要将数组中所有指针全部置为null，则指针引用的对象才会回收，不会造成内存泄漏。 -
public E removeObjectAtIndex(int index)：移除指定index位置的元素，在遍历移动之后，要将原来数组的最后一个指针清空，防止清除移动之后末尾元素被引用两次； - 附件1:
Snip20210330_66.png
- 定义了一个objects存储Object类型的数组，初始容量为7；
- objects在栈区分配内存，new产生的数组对象在堆区分配内存，且objects指向数组对象；数组中存储的是对象的指针地址，而不是对象，我们通过对象的指针去访问对象。
- 对象的指针指向对象，则对象不会被销毁，若对象的指针清空为null，表明没有外界去引用目标对象了，则对象就会被自动回收，这与OC中引用计数器类似。
- 下面给出添加/移除指定index位置元素的图表：
- 初始图：
Snip20210330_67.png
- 在index = 2处插入元素88，操作原理图如下：
Snip20210330_71.png
- 在index = 2处移除元素30，操作原理图如下：
Snip20210330_72.png
- 外界调用代码：定义了一个YYPerson类；
package com.example.dynamicarray.Bean;
import android.util.Log;
public class YYPerson {
private int age;
private String name;
public YYPerson(int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "YYPerson{" +
"age=" + age +
", name='" + name + '\'' +
'}';
}
/**
* 对象销毁时调用
* @throws Throwable
*/
@Override
protected void finalize() throws Throwable {
super.finalize();
Log.d("Person:" + this.name,"finalize");
}
}
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
YYPerson p1 = new YYPerson(20,"Tom");
YYPerson p2 = new YYPerson(30,"John");
YYPerson p3 = new YYPerson(40,"Jim");
YYPerson p4 = new YYPerson(50,"Jack");
//XSArrayList在实际使用的时候才确定元素的存储类型为YYPerson
XSArrayList<YYPerson> persons = new XSArrayList<>();
persons.addObject(p1);
persons.addObject(p2);
persons.addObject(p3);
persons.addObject(p4);
System.out.println(persons);
persons.removeObjectAtIndex(2);
System.out.println(persons);
persons.clear();
}
- 调试结果：
Snip20210330_70.png
- Java对象销毁时会调用
finalize方法相当于OC中dealloc方法； - 数组清除，对象销毁没有造成内存泄漏；
复杂度分析
- 复杂度分析分三种情况：
- 最好情况复杂度；
- 最坏情况复杂度；
- 平均情况复杂度；
-
public E objectAtIndex(int index)：根据index获取元素
public E objectAtIndex(int index) {
rangeCheck(index);
return elements[index];
}
- 复杂度为：常数阶O(1)
-
public E setObjectAtIndex(int index, E element)：设置index位置的元素；
public E setObjectAtIndex(int index, E element) {
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
- 复杂度为：常数阶O(1)；
-
public void insertObjectAtIndex(int index, E element)：往指定index位置插入元素；
public void insertObjectAtIndex(int index, E element) {
if (element == null) return;
rangeCheckForInsert(index);
//检测是否需要进行扩容
ensureCapacity(size + 1);
for (int i = size - 1;i >= index;i--){
elements[i+1] = elements[I];
}
elements[index] = element;
size++;
}
- 数据规模为size；
- 最好情况复杂度：index = size时，即往尾部插入元素，其复杂度为O(1)；
- 最坏情况复杂度：index = 0时，即往首位置插入元素，其复杂度为O(n)；
- 平均情况复杂度：其复杂度为O(n)；
-
public E removeObjectAtIndex(int index)：移除指定index位置的元素；
public E removeObjectAtIndex(int index) {
rangeCheck(index);
E old = elements[index];
for (int i = index + 1;i <= size - 1;i++){
elements[i-1] = elements[I];
}
elements[--size] = null;
return old;
}
- 数据规模为size；
- 最好情况复杂度：index = size时，即往尾部插入元素，其复杂度为O(1)；
- 最坏情况复杂度：index = 0时，即往首位置插入元素，其复杂度为O(n)；
- 平均情况复杂度：其复杂度为O(n)；
- 当数组出现扩容的时候，复杂度会猛然上升，像这种经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况，使用均摊复杂度；
动态数组的缩容
- 当内存空间使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作；
- 比如剩余空间占总容量的一半时，就进行缩容；
- 在
public E removeObjectAtIndex(int index)中调用缩容方法，实现如下：
/**
* 当内存空间使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容
* 当剩余空间占总容量的一半时，就进行缩容；
*/
private void trim(){
int oldCapacity = elements.length;
int newCapacity = oldCapacity >> 1;
if (size >= newCapacity || oldCapacity <= DEFAULT_CAPACITY) return;
//重新申请内存空间
E[] newElements = (E[])new Object[newCapacity];
//将原来内存空间上的元素赋值到新开辟的内存空间中
for (int i = 0;i < size;i++){
newElements[i] = elements[I];
}
elements = newElements;
System.out.println(oldCapacity + "缩容为" + newCapacity);
}
- 调用代码：
public E removeObjectAtIndex(int index) {
rangeCheck(index);
E old = elements[index];
for (int i = index + 1;i <= size - 1;i++){
elements[i-1] = elements[I];
}
elements[--size] = null;
//数组缩容
trim();
return old;
}
- 在清空数组的时候，如果数组内部集合的容量过大，也需要进行缩容处理，代码实现如下：
@Override
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];
}
}
- 测试代码：
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
YYArrayList array = new YYArrayList(6);
array.addObject(1);
array.addObject(2);
array.addObject(3);
array.addObject(4);
array.addObject(5);
array.addObject(6);
System.out.println(array);
array.addObject(7);
array.addObject(8);
array.addObject(9);
array.addObject(10);
array.removeObjectAtIndex(2);
array.removeObjectAtIndex(2);
array.removeObjectAtIndex(2);
array.removeObjectAtIndex(2);
array.removeObjectAtIndex(2);
System.out.println(array);
}
- 调试结果：
Snip20210401_94.png
- 若动态数组的扩容倍数，缩容倍数设计不得当，有可能造成复杂度的震荡；
Snip20210401_95.png
- 数组初始容量为4；
- 扩容与缩容都是原来容量的两倍；
- 那么当在添加元素55时，数组扩容，复杂度由O(1)，变成O(n)；
- 当再次删除元素55时，数组缩容，复杂度O(n)，再删除元素44，复杂度变成O(1)；
