通过二次封装创建属于自己的数组
创建一个Array类,实现一些简单的方法
public class Array {
private int[] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity){
data = new int[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;
}
}
这样就实现了一个数组的简单封装,接下来就要对数组中的元素进行增删改查操作了
添加元素
添加元素时,需要将传入的下标后面的元素都向后挪一位,再将传入的元素插入
// 在index索引的位置插入一个新元素e
public void add(int index, int 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 ++;
}
在方法的内部对下标进行判断,防止用户跨空间操作
这样还可以实现两个插入操作
// 向所有元素后添加一个新元素
public void addLast(int e) {
add(size, e);
}
// 在所有元素前添加一个新元素
public void addFirst(int e) {
add(0, e);
}
重写父类的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();
}
编写一个main函数进行测试
public class Main {
public static void main(String[] args) {
Array arr = new Array(20);
for(int i = 0 ; i < 10 ; i ++)
arr.addLast(i);
System.out.println(arr);
arr.add(1, 100);
System.out.println(arr);
arr.addFirst(-1);
System.out.println(arr);
}
}
结果
Array: size = 10 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 12 , capacity = 20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
修改元素
// 获取index索引位置的元素
public int 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, int e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
data[index] = e;
}
在方法的内部对下标进行判断,防止用户查询数组中未使用的空间
查找元素
// 查找数组中是否有元素e
public boolean contains(int e) {
for (int i = 0; i < size; i++) {
if (data[i] == e)
return true;
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(int e) {
for (int i = 0; i < size; i++) {
if (data[i] == e)
return i;
}
return -1;
}
删除元素
删除元素和添加元素类似
// 从数组中删除index位置的元素, 返回删除的元素
public int remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
int ret = data[index];
for (int i = index + 1; i < size; i++)
data[i - 1] = data[i];
size--;
return ret;
}
// 从数组中删除元素e
public void removeElement(int e) {
int index = find(e);
if (index != -1)
remove(index);
}
将元素删除后,原来最后一位的元素并没有被删除,因为用户根本访问不到那个元素,所以也没有必要进行删除
编写main函数进行测试
public class Main {
public static void main(String[] args) {
Array arr = new Array(20);
for (int i = 0; i < 10; i++)
arr.addLast(i);
System.out.println(arr);
arr.add(1, 100);
System.out.println(arr);
arr.addFirst(-1);
System.out.println(arr);
// [-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
arr.remove(2);
System.out.println(arr);
arr.removeElement(4);
System.out.println(arr);
arr.removeFirst();
System.out.println(arr);
}
}
结果
Array: size = 10 , capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 12 , capacity = 20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 10 , capacity = 20
[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size = 9 , capacity = 20
[0, 1, 2, 3, 5, 6, 7, 8, 9]
使用泛型
上面封装的数组类只支持整形对象,如果想要让其支持更多的类型,就要使用泛型了
将Array更改为支持泛型的类
public class Array<E> {
private E[] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
...
新建一个Student类进行测试
public class Student {
private String name;
private int score;
public Student(String studentName, int studentScore){
name = studentName;
score = studentScore;
}
@Override
public String toString(){
return String.format("Student(name: %s, score: %d)", name, score);
}
public static void main(String[] args) {
Array<Student> arr = new Array<>();
arr.addLast(new Student("Alice", 100));
arr.addLast(new Student("Bob", 66));
arr.addLast(new Student("Charlie", 88));
System.out.println(arr);
}
}
结果
Array: size = 3 , capacity = 10
[Student(name: Alice, score: 100), Student(name: Bob, score: 66), Student(name: Charlie, score: 88)]
动态数组
上面的数组中使用的都是静态数组,创建时容量有多大,就一直是这么大了;但是大部分情况是不知道容量的大小,如果开辟空间大了,就会造成浪费;如果小了,就没法存储下数据.这时动态数组的优势就体现出来了.
这里先写一个动态扩容(缩容)的方法
// 将数组空间的容量变成newCapacity大小
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
data = newData;
}
这个方法应该在添加元素,删除元素时调用,当数组的容量到达一定量的时候,就需要调用这个resize方法了
// 在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)
resize(2 * data.length);
for(int i = size - 1; i >= index ; i --)
data[i + 1] = data[i];
data[index] = e;
size ++;
}
// 从数组中删除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; // loitering objects != memory leak
if(size == data.length / 2)
resize(data.length / 2);
return ret;
}
简单测试一下
public class Main {
public static void main(String[] args) {
Array<Integer> arr = new Array<>();
for(int i = 0 ; i < 10 ; i ++)
arr.addLast(i);
System.out.println(arr);
arr.add(1, 100);
System.out.println(arr);
arr.addFirst(-1);
System.out.println(arr);
arr.remove(2);
System.out.println(arr);
arr.removeElement(4);
System.out.println(arr);
arr.removeFirst();
System.out.println(arr);
}
}
结果
Array: size = 10 , capacity = 10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 12 , capacity = 20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11 , capacity = 20
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 10 , capacity = 10
[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size = 9 , capacity = 10
[0, 1, 2, 3, 5, 6, 7, 8, 9]
时间复杂度分析
添加操作 O(n)
-
addLast(e)O(1)(O(n))
在所有元素后添加元素,可以根据索引直接赋值,时间复杂度是O(1)
最坏的情况,需要对数组进行扩容,需要进行resize操作,此时的复杂度是O(n) -
addFirst(e)O(n)
在所有元素前添加元素,后面的所有元素都需要向后移一位,时间复杂度是O(n) -
add(index, e)O(n/2) = O(n)
添加元素时,由于不确定元素将被插在那里,近似取n/2,当n无限大时,近似O(n)
删除操作 O(n)
-
removeFirst(e)O(n)
从数组中删除第一个元素,后面的所有元素都需要向前移一位,时间复杂度是O(n) -
removeLast(e)O(1) (O(n))
从数组中删除最后一个元素,根据索引可以直接删除,时间复杂度是O(1)
最坏的情况,需要对数组进行缩容,需要进行resize操作,此时的复杂度是O(n) -
remove(index, e)O(n/2) = O(n)
和添加元素类似
修改操作 O(1)
-
set(index, e)O(1)
根据下标直接进行赋值即可
查找操作
-
get(index)O(1) -
contains(e)O(n) -
find(e)O(n)
contains(e)和find(e)需要对数组进行遍历
resize复杂度分析
假设当前capacity=8,并且每一次添加操作都使用的是addLast,这样在进行第9次添加操作时,就会触发resize,这个过程一共进行了17次基本操作(赋值)
8次正常赋值, 扩容时又进行了8次赋值, 最后将第9个元素赋值,共8+8+1, 平均每次addLast进行了2次基本操作
假设当前capacity=n,进行n+1次addLast操作,触发resize,总共进行2n+1次基本操作,平均每次addLast操作,进行2次基本操作,这样均摊计算的话,均摊复杂度是O(1)级别的!
同理, removeLast是一样的,也是O(1)级别的
但是, 当我们同时关注addLast和removeLast,当容量刚好装满时,
此时调用addLast, 需要进行resize操作, 此时时间复杂度是O(n)级别的;
再进行removeLast操作, 此时元素个数刚好是容量的一半, 又需要进行resize操作,此时时间复杂度也是O(n)级别的.
出现问题的原因是在进行removeLast操作时,resize过于着急了,解决方案是使用更懒惰的
策略,当size = capacity/4时,再进行resize容量减半操作
// 从数组中删除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; // loitering objects != memory leak
if(size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}
Array源码
public class Array<E> {
private E[] data;
private int size;
// 构造函数，传入数组的容量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;
}
// 在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)
resize(2 * data.length);
for (int i = size - 1; i >= index; i--)
data[i + 1] = data[i];
data[index] = e;
size++;
}
// 向所有元素后添加一个新元素
public void addLast(E e) {
add(size, e);
}
// 在所有元素前添加一个新元素
public void addFirst(E e) {
add(0, e);
}
// 获取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;
}
// 查找数组中是否有元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e)
return true;
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == 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; // loitering objects != memory leak
if (size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}
// 从数组中删除元素e
public void removeElement(E e) {
int index = find(e);
if (index != -1)
remove(index);
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst() {
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast() {
return remove(size - 1);
}
// 将数组空间的容量变成newCapacity大小
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++)
newData[i] = data[i];
data = newData;
}
@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();
}
}
网友评论