之前1和2都是靜態(tài)數(shù)組，我們創(chuàng)造動(dòng)態(tài)數(shù)組
package com.company;
/**
* @program: Array
* @description: 數(shù)組
* @author: Gu
* @create: 2019-04-10 22:03
**/
public class Array<E> {
private E[] data;
private int size;
//初始化
public Array(int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
//無參構(gòu)造函數(shù)默認(rèn)最大容量為10
public Array() {
this(10);
}
//數(shù)組長(zhǎng)度
public int length() {
return data.length;
}
//數(shù)組元素個(gè)數(shù)
public int getSize() {
return size;
}
//數(shù)組是否為空
public boolean isEmpty() {
return size == 0;
}
//向數(shù)組指定位置中添加元素
public void add(int index, E element) {
if (index >= data.length || index < 0) {
throw new IllegalArgumentException("[數(shù)組索引非法]");
}
if (size == data.length) {
//throw new IndexOutOfBoundsException("[數(shù)組已達(dá)到最大容量]");
//動(dòng)態(tài)數(shù)組爆侣，數(shù)組容量到達(dá)最大值時(shí)鸟蜡，要擴(kuò)容，我們暫定為擴(kuò)容2倍（與java動(dòng)態(tài)數(shù)組倍數(shù)不同）
int newCapacity = data.length * 2;
resize(newCapacity);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = element;
size++;
}
//向數(shù)組第一個(gè)索引添加元素
public void addFirst(E element) {
add(0, element);
}
//數(shù)組末尾添加元素
public void addLast(E element) {
add(size, element);
}
//根據(jù)index查找指定元素
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("[數(shù)組索引非法]");
}
return data[index];
}
//查找數(shù)組是否包含指定元素
public boolean contains(E element) {
for (E value : data) {
if (value.equals(element)) {
return true;
}
}
return false;
}
//返回指定元素的索引
public int find(E element) {
for (int i = 0; i < size; i++) {
if (data[i].equals(element)) {
return i;
}
}
return -1;
}
//修改數(shù)組元素
public void set(int index, E element) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("[數(shù)組索引非法]");
}
data[index] = element;
}
//刪除指定元素
public void delete(E element) {
int index = find(element);
if (index == -1) {
throw new IllegalArgumentException("[數(shù)組沒有該元素]");
}
remove(index);
}
//根據(jù)索引刪除元素
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("[數(shù)組索引非法]");
}
E res = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size = size - 1;
//刪除內(nèi)容后诉稍，我們希望向數(shù)組擴(kuò)容一樣，數(shù)組容量也會(huì)減少最疆，我們假定size為1/2時(shí)杯巨，容量減半
if (size == data.length / 4 && data.length / 2 != 0) {
int newCapacity = data.length / 2;
resize(newCapacity);
}
return res;
}
private void resize(int capacity) {
E[] temp = (E[])new Object[capacity];
for (int i = 0; i < size; i++) {
temp[i] = data[i];
}
data = temp;
}
//刪除第一個(gè)
public E removeFirst() {
return remove(0);
}
//刪除最后一個(gè)
public E removeLast() {
return remove(size - 1);
}
//打印數(shù)組相關(guān)信息
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append(String.format("數(shù)組的size : %d, 數(shù)組的capacity : %d \n", size, data.length));
stringBuffer.append("[");
for (int i = 0; i < size; i++) {
stringBuffer.append(data[i]);
if (i == size - 1) {
stringBuffer.append("]");
break;
}
stringBuffer.append(",");
}
return stringBuffer.toString();
}
}
主要是增加數(shù)據(jù)和減少數(shù)據(jù)時(shí)，修改了數(shù)組容量努酸。
測(cè)試類
package com.company;
public class Main {
public static void main(String[] args) {
//add()
Array<Integer> array = new Array<>(10);
for (int i = 0; i < 10; i++) {
array.add(i, i + 1);
}
System.out.println(array);
//[1,2,3,4,5,6,7,8,9,10]
//addFirst()
array.addFirst(0);
System.out.println(array);
//[0,1,2,3,4,5,6,7,8,9,10]
//removeFirst
array.removeFirst();
System.out.println(array);
}
}
這里使用均攤分析簡(jiǎn)單說明下擴(kuò)容或者減半時(shí)的時(shí)間復(fù)雜度服爷。
假如數(shù)組capacity = 4， size = 4获诈， 這時(shí)我們?cè)黾訑?shù)據(jù)時(shí)仍源，會(huì)觸發(fā)resize（）操作，使得capacity = 8舔涎，并且把老數(shù)組的數(shù)據(jù)復(fù)制到新數(shù)組笼踩。
此時(shí)我們統(tǒng)計(jì)下操作步驟：5次add操作 + 4次復(fù)制操作 = 9
我們均攤下時(shí)間復(fù)雜度： 9 / n = 2; 此時(shí)n = 4；是常數(shù)O（1）亡嫌；
數(shù)組容量減半也是如此嚎于。
還有復(fù)雜度的震蕩問題
我們可以看一張圖：
復(fù)雜度的震蕩
數(shù)組capacity = 10, size = 10掘而，我們?cè)黾右粋€(gè)元素 ，此時(shí)capacity = 20于购。 接著 我們減去一個(gè)元素袍睡，capacity = 10，這些都符合邏輯肋僧。但是此時(shí)我們發(fā)現(xiàn)每做一次操作的時(shí)間復(fù)雜度為O（n）斑胜。
上述現(xiàn)象就是復(fù)雜度震蕩問題。
產(chǎn)生問題的原因在于嫌吠，每次size = capacity / 2 時(shí)止潘，我們都會(huì)減半capacity。 現(xiàn)在我們采取新的策略居兆，只有增加時(shí)才會(huì)擴(kuò)容覆山，減少size = capacity / 2 時(shí)我們不急于減半竹伸，只有當(dāng)size = capacity / 4泥栖，我們才將capacity = capacity/2；修改后的代碼如下
//根據(jù)索引刪除元素
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("[數(shù)組索引非法]");
}
E res = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size = size - 1;
//刪除內(nèi)容后勋篓，我們希望向數(shù)組擴(kuò)容一樣吧享，數(shù)組容量也會(huì)減少，我們假定size為1/2時(shí)譬嚣，容量減半
if (size == data.length / 4 && data.length / 2 != 0) {
int newCapacity = data.length / 2;
E[] temp = (E[])new Object[newCapacity];
for (int i = 0; i < size - 1; i++) {
temp[i] = data[i];
}
data = temp;
}
return res;
}
