二次封装属于我们自己的数组
最近在学习数据结构与算法收获颇深，做一点笔记记录一下学习过程。
在学习数据结构的过程中，我们都会从增删改查开始，我们这里基于java的数组，二次封装属于我们自己的数组类。
一. 定义一个数组类
- 数组本身是静态，我们一开始需要设置最多装多少个元素(Capacity)
- 我们使用size来记录数组中的元素个数
二. 向数组中添加元素
- 向数组末尾添加元素（向数组末尾添加元素，就是在size添加元素，添加完以后我们需要将size加1）
- 向指定位置添加元素（向索引为2的位置添加元素99，从索引为2的位置起将所有元素往后移，然后将99插入到索引为2的位置，插入以后我们需要将size加1
三. 向数组中查询元素（根据下标查询相应的元素，查询下标为index的元素）
返回 data[index]即可
四. 向数组中修改元素（修改对应下标index下面的元素，修改值为value）
data[index] = value
五. 从数组中删除指定位置的元素（删除索引为2的元素）
六 . 使用泛型
- 让我们的数据可以放置“任何”数据类型
- 不可以是基本数据类型，只能是类对象 boolean，byte，char，short，int，long，float，double
- 每个基本数据类型都有对应的包装类 Boolean，Byte，Char，Short，Int，Long，Float，Double
七. 将我们的数组封装为动态数组 （重新开一个空间，将之前的元素赋值到现在的空间中，我们这里叫resize操作）
扩容以后，当我们的数据删除到一定的程度以后，我们可以将我们的数组进行缩小，一样的使用resize方法进行缩容。
八. 分析动态数组的时间复杂
- 添加操作 O(n)
addLast(e) O(1)
addFirst(e) O(n)
add(index,e) O(n/2)
最坏情况：O(n), resize：O(n)
2. 修改操作 O(1)
set(index,e) O(1)
3. 查找操作
get（index） O(1)
contains（e） O（n）
find（e） O（n）
总结：
改和查，已知索引为O（1），未知索引为O(n)
增和删，为O（n），由于在我们的动态数组中有resize操作，那么我们在操作最后一个元素时还是O（n）的时间复杂度？
九. 使用均摊复杂度分析resize操作
我们知道进行resize操作时，需要将原数组中的元素复制到新的数组中。假如我们数组中的元素是n，那么我们需要进行n次复制，那么resize时间复杂度为O（n）
假设当前 capacity = 8， 并且每一次添加操作都使用addLast
9次addLast操作，触发resize，总共进行了17次基本操作，平均每次addLast操作，进行2次基本操作。
假设capacity = n，n+1次addLast，触发resize，总共进行2n+1次基本操作，平均每次addLast操作进行2次基本操作，这样均摊计算，时间复杂度是O（1）的！
在这里，其实这样均摊计算，比计算最坏情况更加有意义。
addLast的均摊复杂度为O（1）
同理：removeLast的均摊复杂为O（1）
其实相对一个比较耗时的操作，只要我们不是每一次都进行计算，其实这样子的运行效率还是比较可观的。
十. 防止resize的复杂度震荡
我们会发现，当每次扩容增加一倍和缩容一半时，可能会同时不断触发addLast和removeLast操作
此时会出现复杂度震荡，出现的问题：removeLast时resize过于着急（Eager）
解决方案：Lazy
当 size == capacity / 4 时，才将capacity 减半
具体代码实现：
// 为了简洁，我们都使用//进行注释
public class Array<E> {
private E[] data;
private int size;
private int capacity = 10;
// 有参数的构造函数
public Array(int capacity){
data = (E[])new Object[capacity]; // 我们new 一个泛型类型的数组，需要绕一个弯
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public Array(){
data = (E[])new Object[capacity];
size = 0;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size==0;
}
// 获取数组的容量
public int getCapacity(){
return data.length;
}
// 向数组末尾添加一个新的元素，我们复用add方法，在索引为size的位置添加元素
public void addLast(E e){
add(size,e);
}
// 向数组的第一个位置添加一个新的元素，我们复用add方法，在索引为0的位置添加元素
public void addFirst(E e){
add(0,e);
}
// 在索引为index的位置插入一个新的元素e
public void add(int index, E e){
if(size == data.length)
// 这里扩容1倍，扩容的量与当前的数据是有关系的
resize(2 * data.length);
// index<0 是非法的，index>size 说明插入的不是紧密的，不是我们要的结果
if(index < 0 || index>size)
throw new IllegalArgumentException(“Add failed.Require index >=0 and index<=size”);
for(int i=size-1;i>=index;i–){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
// 获取index索引位置的元素,get 无法读取使用的空间的
public E get(int index){
if(index<0 ||index>=size)
throw new IllegalArgumentException(“Get failed. Index is illegal.”);
return data[index];
}
// 获取数组中最后一个元素
public E getLast(){
return get(size-1);
}
// 获取数组中第一个元素
public E getFirst(){
return get(0);
}
// 修改数组中索引为index的元素，修改值为e
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException(“Set failed. Index is illegal.”);
data[index] = e;
}
//查找数组中是否有元素e
public boolean contains(E e){
for(int i =0; i<size ;i ++){
if(data[i].equals(e)) //这里是比较两个类对象的值是否相等需要使用equals ==为引用比较
return true;
}
return false;
}
//查找数组中元素e 所在的索引，如果不存在元素e，则返回-1
public int find(E e){
for(int i =0; i<size ;i ++){
if(data[i].equals(e))
return i;
}
return -1;
}
//从数组中删除index位置的元素，返回删除的元素
public E remove(int index){
if(index<0 ||index>=size)
throw new IllegalArgumentException(“remove failed. Index is illegal.”);
E ret = data[index];
for(int i=index+1;i<size;i++)
data[i-1]=data[i]; // 这里基本数据类型的话，值还是在这里，当我们插入新的元素的时候，会自动复制掉
size –;
data[size] = null; // 由于这里是泛型，还存在对象的引用，垃圾回收机制就不会去删除，我们将其置为null
if(size == data.length/4 && data.length /2 != 0)
resize(data.length/2);
return ret;
}
// 从数组中删除第一个元素，返回删除的元素
public E removeFirst(){
return remove(0);
}
// 从数组中删除最后一个元素，返回删除的元素
public E removeLast(){
return remove(size-1);
}
// 从数组中删除元素e，这里只删除一个元素e
public void removeElement(E e){
int index = find(e);
if(index !=-1)
remove(index);
}
//重写 toString 定义打印输出的方法
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format(“Array: size =%d, capacity=%d\n”, size,data.length));
res.append(“[“);
for(int i=0;i<size;i++){
res.append(data[i]);
if(i!=size-1)
res.append(“,”);
}
res.append(“]”);
return res.toString();
}
// 为动态数组的扩容和缩容操作
private void resize(int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
for(int i=0 ; i<size ; i++)
newData[i] = data[i];
data = newData;
}
}
转载自：https://blog.csdn.net/qq_22230709/article/details/81298241
