手把手寫一個集合框架（一）動態陣列

摘要： 陣列的建構函式 //首先，我們需要設計一個帶有泛型功能的類 public class Array<E> { private E[]data; private int size; //建構函式，空引數預設...

• 陣列的建構函式

//首先，我們需要設計一個帶有泛型功能的類
public class Array<E> {
private E[]data;
private int size;
//建構函式，空引數預設的容量為10
public Array(){
this(10);
}
//使用者帶引數的建構函式
public Array(int Capacity){
data = (E[])new Object[Capacity];
size = 0;
}
}

• 實現動態陣列的基本功能

public int getCapacity(){ //獲取陣列容量
return data.length;
}
public int getSize(){//獲取陣列元素個數
return this.size;
}
public boolean isEmpty(){ //判斷陣列是否為空
return this.size==0;
}
//當我們陣列的元素已經滿的時候，我們需要擴容
private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for(int i=0;i<size;i++){
newData[i]=data[i];
}
data=newData;
}

• 向動態陣列新增元素

//在某一個位置插入一個元素
public void add(int index , E e){
if(index<0 || index>size) throw new 
IllegalArgumentException("index is error...");
if(size==data.length)
resize(2*data.length);
for(int i= size-1;i>=index ;i--){
data[i+1] = data[i];
}
data[index]=e;
}
//再新增兩個輔助函式，方便介面呼叫
public void addFirst(E e){//在第一個位置插入一個元素
add(0,e);
}
public void addLast(E e){//陣列最後新增一個元素
if(size == data.length)
throw new IllegalArgumentException("add last...");
data[size]=e;
size++;
}

• 向陣列刪除元素

//刪除某一個索引下面的元素
public E remove(int index){//刪除某一個索引下面的元素
if(index<0 || index>size)
throw new IllegalArgumentException();
E ret = data[index];
for(int i=index+1;i <size;i++){
data[i-1] = data[i];
}
size--;
//使用懶惰策略進行縮容，同時當元素為1個就不能縮容了
if(size == data.length >>2 && size>1)
resize(data.length>>1); //縮小一半容量
return ret;
}
public void removeElement(E e){ //安裝元素刪除
int index = find(e);
if(index!=-1)
remove(index);
return;
}
//新增兩個輔助介面函式，方便我們後續基於陣列實現其他資料結構
public E removeFirst(){
return remove(0);
}
public E removeLast(){
return remove(this.size-1);
}

• 向陣列修改元素

public void set(int index ,E e){ //修改某一個索引下面的元素值
if(size==data.length)
throw new IllegalArgumentException("add last...");
data[index]=e;
}

• 在陣列中查詢某一元素

public int find(E e){ //查詢元素的索引
for(int i=0;i<size;i++){
if(data[i].equals(e))
return i;
}
return -1;
}
public boolean contains(E e){ //查詢一是否存在一個元素
for(int i=0;i<size;i++){
if(data[i].equals(e))
return true;
}
return false;
}

• 在陣列中獲取元素

//這些方法有利於我們後續基於陣列實現其他資料結構
public E get(int index){//獲取指定下標元素
if(index<0||index>=size)
throw new IllegalArgumentException("index error");
return data[index];
}
public E getLast(){//獲取最後一個元素
return get(size);
}
public E getFirst(){//獲取第一個元素
return get(0);
}

• 總結

  本文藉助靜態陣列實現了一種動態陣列，包括增加、刪除、修改、查詢等功能。為我們後續基於動態陣列實現棧和佇列打下基礎。