数组是最为常见也是最简单的数据结构之一，本文通过2次封装来一步一步实现数组的功能，来了解与熟悉这个最基本的数据结构
初始化
public class Array<E> {
private int size;
private E[] data;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity){
data = (E[]) new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public Array(){
this(10);
}
// 获取数组的容量
public int getCapacity(){
return data.length;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
}
添加元素
public void addLast(E e){
add(size,e);
}
public void addFirst(E e){
add(0,e);
}
// 在index索引的位置插入一个新元素e
public void add(int index,E e){
if(size == data.length)
throw new IllegalArgumentException("Add failed. Array is full.");
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++;
}
-
在add函数中通过for循环，将数据从最后一个开始一个一个往后挪一位，这样做的目的是讲
index这个位置空出来最终插入需要添加的元素 -
这里我们的数组只能实现固定的长度，当添加超过规定长度时会抛出异常，不用担心接下来会实现动态扩容和缩减功能
获取和修改元素
// 获取index索引位置的元素
public E get(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改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;
}
包含，搜索和删除
public E removeFirst(){
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast(){
return remove(size-1);
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
E e = data[index];
for (int i = index; i <=data.length; i++) {
data[i] = data[i+1];
}
size--;
data[size] = null;
return e;
}
// 从数组中删除元素e
public void removeElement(E e){
int index = find(e);
if(index != -1)
remove(index);
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e){
for (int i = 0; i < data.length; i++) {
if (data[i].equals(e)) {
return I;
}
}
return -1;
}
// 查找数组中是否有元素e
public boolean contain(E e){
for (E datum : data) {
if (datum.equals(e)) {
return true;
}
}
return false;
}
- 注意remove中最后将data[size]设为null
动态数组(动态扩容和缩容)与复杂度震荡
// 在index索引的位置插入一个新元素e
public void add(int index,E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
if(size == data.length)
resetData(size*2);
for (int i = 0; i < data.length; i++) {
data[index + 1] = data[I];
}
data[index] = e;
size++;
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
E e = data[index];
for (int i = index; i < data.length; i++) {
data[i] = data[i+1];
}
size--;
if (size==data.length/4) {
resetData(data.length/2);
}
return e;
}
// 将数组空间的容量变成newCapacity大小
public void resetData(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < sze; i++) {
newData[i] = data[I];
}
data = newData;
}
-
resetData方法传入需要的容量，并新建数组newData，通过循环将之前data的数据复制到newData中。最后将
data地址指到新建的newData。而老数组由于没有了指向，最终会被jvm回收 -
add函数中，当
size达到容量界限时扩容到现在的2倍。而remove中，当size为容量的¼时,可能同学们都有疑问这里缩容条件为什么不是½呢？这里就涉及到一个效率问题，举例：假设缩容条件为½
Aarry array = new Array(5);
array.addLast(1);
array.addLast(2);
array.addLast(3);
size为3，容量为5，当我们再次添加数据：
array.addLast(4);
此时该操作方法的时间复杂度时O(1),然而当我们再次array.addLast时由于有了扩容操作resetData,此时时间复杂度为O(n)容量变为10。如果此时进行一个removeLast，由于满足了缩容条件½,会再次调用resetData此操作又是一个时间复杂度为O(n)的操作。如果一个操作反复在这个条件之间操作，就会极大的降低操作效率，这种一个时间复杂度O(1)的操作变为O(n)的操作又叫做--复杂度震荡。如果此时缩容条件为四分之一则可以有效的避免这种情况
网友评论