把玩算法 | 數組

基礎

數組是由相同類型的元素的集合所組成的數據結構，分配一塊連續的內存來存儲。數組是使用索引來訪問裏面的元素的。如果我們有n個值，那麼數組索引的範圍為0至n-1。對於0到n-1之間的任意的i，我們就能在Java代碼中用arr[i]來訪問第i個元素的值。

下面的代碼創建了一個人名的數組，然後打印數組中的第二個元素：

String[] names = {"張三", "李四", "王五"};
System.out.println(names[1]);

但是數組創建完成後，其大小也就不能改變了。如果我們想要動態的改變數組的大小，那麼就需要先創建足够大的同類型的數組，然後再將原始的數組中的數據拷貝到新創建的數組中。例如原先創建了一個長度為3的數組存放了3個人的名字，後來需要再存放"趙六"和"錢七"這兩個人名，那麼就需要重新創建長度為5的數組來存放這5個人名。相關的代碼如下（注：數組的拷貝可以使用System.arraycopy方法來進行拷貝）：

String[] names = {"張三", "李四", "王五"}; // 原先的數組
// 現在需要存放"趙六"和"錢七"這兩個人名
String[] newNames = new String[5];
// 拷貝之前的數據
for (int i = 0; i < names.length; i++) {
newNames[i] = names[i];
}
// 存放"趙六"和"錢七"
newNames[3] = "趙六";
newNames[4] = "錢七";

每次都要自己手動的來對數組進行擴容確實挺麻煩的，我們可以將添加、删除、訪問數組中的元素的方法進行封裝，在需要用到時直接用就行了。

API

下面是我們為數組定義的相關API：

---

數組

pubic class Array<Element> implements Iterable<Element>
Array() 創建一個空數組
Array(int capacity) 創建一個初始化容量的數組
void add(Element e) 添加一個元素
Element get(int index) 獲取指定比特置的元素
void set(int index, Element e) 設置指定比特置的元素
Element remove(int index) 移除指定比特置的元素
int size() 獲取數組的大小

---

• 泛型：一種特別的Java的機制，也叫參數化類型。在API中，類名後面的<Element>將Element定義為一個類型參數，它是一個占比特符，錶示的是該類將會使用到的某個具體的數據類型。Array<Element>可以理解為某種元素的數組。我們這裏的數組是能存放任意類型的數據的，例如，可以編寫下面的代碼來存放String類型的對象：

  Array<String> arr = new Array<String>();
  arr.add("張三");
  ...
  

• 可迭代的集合：在很多情况下，只需要用某種方式來處理集合中的每個元素，這種模式一般叫做迭代器模式。有了它，我們就能寫出很清晰的代碼而不必依賴於具體的集合類型的實現。只要實現了Iterable，就能使用for-each來遍曆集合中的每一個元素，例如下面的代碼打印出所有的人的姓名：

  Array<String> names = new Array<String>();
  ...
  for (String name : names) {
  System.out.println(name);
  }
  

  上面的for-each等同於下面的代碼（很明顯，使用for-each要簡介方便很多）：

  for (Iterator<String> iterator = names.iterator(); iterator.hasNext();) {
  String name = iterator.next();
  System.out.println(name);
  }
  

有了上面的API後，就能將上面的代碼改為使用Array來編寫。在這裏只需要關注所需要實現的邏輯，而不必關注具體的內部實現細節：

public static void main(String[] args) {
Array<String> names = new Array<>(3);
names.add("張三");
names.add("李四");
names.add("王五");
System.out.println(names);
// 存放"趙六"和"錢七"
names.add("趙六");
names.add("錢七");
System.out.println(names);
}

實現

更加詳細的實現見github：Array.java

public class Array<Element> implements Iterable<Element> {
private Object[] elements; // 元素
private int size; // 元素的個數
public Array() { this(0); }
public Array(int capacity) { elements = new Object[capacity]; }
public void add(Element e) {
if (size == elements.length) {
resize(size * 2 + 1);
}
elements[size++] = e;
}
public Element get(int index) { return (Element) elements[index]; }
public void set(int index, Element e) { elements[index] = e; }
public int size() { return size; }
// 下面這幾個方法的實現，請看接下來的實現說明
private void resize(int capacity)
public void remove(int index)
public Iterator<Element> iterator()
}

默認的構造器創建了一個空白的數組（長度為0），也提供了一個能指定初始化容量的版本，這樣就可以根據自己的使用場景提供一個恰當的容量，避免在添加元素的過程中，數組內部頻繁的進行擴容，影響性能。內部維護了一個數組Object[]用來存放元素，使用實例變量size來記錄數組的大小。

為了能更加直觀的看到數組存放的元素，還需要重寫toString方法：

public String toString() {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
if (i > 0) {
sb.append(",");
}
sb.append(elements[i]);
}
sb.append("]");
return sb.toString();
}

add, get, set這幾個方法的實現都比較簡單，都是直接操作存放元素的數組來實現，還提供了size()方法來獲取數組的大小。如果元素數組滿了，add方法會在添加元素之前會數組進行擴展，相關的實現如下：

數組擴容

elements的初始化長度是固定的，當elements滿了之後就沒有空餘的空間來存放後續添加的元素了，這時就需要進行擴容了。這裏的實現也比較簡單，創建一個新的數組，再將原先數組中的值複制過去，再將新的數組賦值給elements就可以了。

private void resize(int capacity) {
Object[] newElements = new Object[capacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}

在add方法中，將元素數組的長度調整為原先的2倍再加1（size * 2 + 1）

移除

移除數組中指定索引i處的元素時，需要將索引i之後的所有元素往前挪一格，並且還需要將數組中最後的一個元素設置為null，避免對失效比特置對元素的引用。

例如，數組中存放了5個元素：[張三,李四,王五,趙六,錢七]，如果要删除第二個元素，調用remove(1)方法的示例圖如下：

移除過程（灰色方格錶示還未處理到的比特置）：

實現如下：

public Element remove(int index) {
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
size--;
Element oldValue = (Element) elements[size];
elements[size] = null;
if (size > 0 && size < elements.length / 4) {
resize(elements.length / 2);
}
return oldValue;
}

當數組的大小為其容量的四分之一時，將數組的容量縮减為數組容量的二分之一。

迭代

iterator()方法的實現如下：

public Iterator<Element> iterator() {
return new Iterator<Element>() {
int cursor;
@Override
public boolean hasNext() {
return cursor < size;
}
@Override
public Element next() {
return (Element) elements[cursor++];
}
@Override
public void remove() {
throw new UnsupportedOperationException("remove");
}
};
}

內部維護了一個當前迭代器的指針cursor，相關方法的實現說明如下：

• hasNext()：錶示是否還有下一個元素，如果cursor指針未超過數組的大小，那麼說明還有下一個元素
• next()：獲取下一個元素，並將cursor指針指向下一個元素
• remove()：這裏不支持移除操作，直接拋出了UnsupportedOperationException异常

迭代示意圖如下：