在深入淺出數(shù)據(jù)結(jié)構(gòu)這一篇中說道：
數(shù)據(jù)元素的物理存儲(chǔ)結(jié)構(gòu)形式有兩種：
- 順序存儲(chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里盲憎，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的刽脖。實(shí)際上就是基于數(shù)組實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)
- 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的炊林。數(shù)據(jù)元素的存儲(chǔ)關(guān)系并不能反映其邏輯關(guān)系，需要用一個(gè)指針存放數(shù)據(jù)元素的地址稽穆，通過地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置澜建。實(shí)際上就是基于鏈表實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。
所以數(shù)組和鏈表是實(shí)現(xiàn)所有數(shù)據(jù)結(jié)構(gòu)的基石蚕甥，是最基本的兩種數(shù)據(jù)結(jié)構(gòu)哪替，需要牢牢掌握。這一篇主要討論一下數(shù)組的相關(guān)概念和實(shí)現(xiàn)菇怀。
數(shù)組的基本概念
-
什么是數(shù)組
數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)凭舶，它用一組連續(xù)的內(nèi)存空間晌块，來存儲(chǔ)一組具有相同類型的數(shù)據(jù)。
-
為什么數(shù)組能夠?qū)崿F(xiàn)隨機(jī)訪問帅霜，并且隨機(jī)訪問的時(shí)間復(fù)雜度是
O(1)根據(jù)數(shù)組的定義匆背，需要一組連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)。正是因?yàn)閿?shù)組具備兩個(gè)限制身冀，所有數(shù)組才能隨機(jī)訪問钝尸，因?yàn)閿?shù)組中的元素能知道其具體所在位點(diǎn)。
其實(shí)可以用一種不太專業(yè)的解釋來理解搂根，我們知道珍促，所有的數(shù)據(jù)都是存放在內(nèi)存中的，如果是一個(gè)零散的內(nèi)存空間剩愧，如何知道數(shù)據(jù)的具體位點(diǎn)呢猪叙，數(shù)據(jù)的位點(diǎn)是雜亂無章的，所以要想能夠?qū)崿F(xiàn)隨機(jī)訪問仁卷，首要條件之一就是要一段連續(xù)的內(nèi)存空間穴翩。
那如何理解必須要有相同的數(shù)據(jù)類型呢？我們以
int類型的數(shù)組為例锦积，我們知道int類型的數(shù)據(jù)在32位操作系統(tǒng)占4字節(jié)芒帕，假設(shè)我們執(zhí)行下面一段代碼：int[] a = new int[10];a數(shù)組創(chuàng)建好了以后，分配到了一塊連續(xù)的內(nèi)存空間1000~1039丰介，首地址為1000副签。
首地址為1000，每個(gè)元素占四個(gè)字節(jié)基矮，所以下一個(gè)元素的地址就為（1000 + 4） = 1004淆储，以此類推。
有人說家浇，如果其他類型也占4個(gè)字節(jié)本砰，我這樣是不是也照樣可以找到我想要的元素呢？如果想要深究的同學(xué)钢悲，可以自行研究一下点额，可以看看計(jì)算機(jī)組成原理相關(guān)的知識(shí)，這里呢就不深入下去了莺琳。
注意：
數(shù)組是適合查找还棱，但是查找的時(shí)間復(fù)雜度并不是O(1)。隨機(jī)訪問才是O(1)惭等。隨機(jī)訪問的意思珍手，按照我們常說的，就是根據(jù)下標(biāo)或者索引返回元素。但是要查找或者判斷某個(gè)元素在該數(shù)組中是否存在琳要，即使是已經(jīng)排好序的數(shù)組寡具，利用二分查找法，時(shí)間復(fù)雜度也是O(logn)稚补。
-
為什么下標(biāo)都是從0開始童叠？
當(dāng)計(jì)算機(jī)需要隨機(jī)訪問數(shù)組中的某個(gè)元素的時(shí)候，它會(huì)如下的公式來計(jì)算出實(shí)際需要訪問數(shù)據(jù)的內(nèi)存地址课幕。
a[i]_address = base_address + i * data_type_size,其中i為偏移量厦坛。在上述數(shù)組中，由于類型是int乍惊，占4個(gè)字節(jié)杜秸，所以data_type_size為4。我們可以就這么理解為偏移量污桦，有人說那為什么不寫成
a[i]_address = base_address + (i-1) * data_type_size i >= 1呢？實(shí)際上匙监，沒有必要過于糾結(jié)這個(gè)由來凡橱，這是coding界約定俗成的規(guī)定，所以大家記住即可亭姥。
靜態(tài)數(shù)組和動(dòng)態(tài)數(shù)組
靜態(tài)數(shù)組
-
什么是靜態(tài)數(shù)組稼钩？
一個(gè)靜態(tài)數(shù)組是一個(gè)包含n個(gè)元素的定長(zhǎng)容器，其中的元素是可以索引的达罗，范圍從[0, n-1]坝撑，其實(shí)就是數(shù)組的定義。
-
靜態(tài)數(shù)組的使用場(chǎng)景
存儲(chǔ)和訪問順序數(shù)據(jù)
臨時(shí)存儲(chǔ)對(duì)象
用作IO程序的緩沖區(qū)
正向和反向查找表
用于在函數(shù)結(jié)束時(shí)返回多個(gè)值
用于在動(dòng)態(tài)規(guī)劃中緩存子問題的結(jié)果
-
靜態(tài)數(shù)組的特點(diǎn)
- 固定長(zhǎng)度粮揉，不能進(jìn)行增加巡李，刪除元素
java example:
int[] a = new int[10];// 不能對(duì)a進(jìn)行插入，添加扶认，刪除的操作侨拦，只能修改和查找 -
靜態(tài)數(shù)組修改和查找的時(shí)間復(fù)雜度
操作 時(shí)間復(fù)雜度 示例 按索引訪問 O(1)a[0]查找 O(n)for循環(huán)遍歷查找修改 O(1)a[2] = 5
動(dòng)態(tài)數(shù)組
-
什么是動(dòng)態(tài)數(shù)組？
動(dòng)態(tài)數(shù)組的大小可以擴(kuò)展和縮小辐宾，動(dòng)態(tài)數(shù)組不僅支持靜態(tài)數(shù)組的操作狱从，也能支持插入，添加叠纹，刪除等操作季研。
-
動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)方案
創(chuàng)建一個(gè)具有初始容量的靜態(tài)數(shù)組。
向底層靜態(tài)數(shù)組中添加元素誉察，跟蹤元素的個(gè)數(shù)与涡。
如果繼續(xù)添加元素會(huì)超出容量，那么就創(chuàng)建一個(gè)具有兩倍容量的新數(shù)組，并將原數(shù)組的內(nèi)容拷貝到新數(shù)組當(dāng)中去递沪。
-
動(dòng)態(tài)數(shù)組的時(shí)間復(fù)雜度
操作 時(shí)間復(fù)雜度 按索引訪問 O(1)查找 O(n)修改 O(1)插入 O(n)添加 O(1)刪除 O(n)
動(dòng)態(tài)數(shù)組的具體實(shí)現(xiàn)
插入
假設(shè)一個(gè)數(shù)組豺鼻，長(zhǎng)度為n，現(xiàn)在要在第k個(gè)位置插入一條元素款慨。正常的邏輯應(yīng)該是把第k個(gè)位置騰出來儒飒，第k個(gè)位置往后的元素需要往后移動(dòng)一位，再將新元素賦值給第k個(gè)位置檩奠，這樣呢就保證了新數(shù)組和之前的順序一致桩了。
如果k就是最后一位，那么插入的時(shí)間復(fù)雜度為o(1)埠戳，不需要移動(dòng)任何數(shù)據(jù)井誉。但是如果k是第一位，那么插入的時(shí)間復(fù)雜度為o(n),需要移動(dòng)所有數(shù)據(jù)整胃。即最好時(shí)間復(fù)雜度為o(1),最壞為o(n)颗圣，平均時(shí)間復(fù)雜度為(1+2+…n)/n=O(n)。
刪除
與插入操作類似屁使，我們要?jiǎng)h除第k個(gè)位置的元素在岂，為了保證內(nèi)存的連續(xù)性，也是需要做數(shù)據(jù)遷移工作的蛮寂。如果刪除數(shù)組末尾的數(shù)據(jù)蔽午，則最好情況時(shí)間復(fù)雜度為 O(1)；如果刪除開頭的數(shù)據(jù)酬蹋，則最壞情況時(shí)間復(fù)雜度為O(n)及老；平均情況時(shí)間復(fù)雜度也為 O(n)。
數(shù)組越界
int[] a = new int[10];
System.out.print(a[10]); // java.lang.ArrayIndexOutOfBoundsException: 10
容器與數(shù)組
在java中范抓，使用數(shù)組作為底層數(shù)據(jù)結(jié)構(gòu)的容器還是蠻多的骄恶，用的最多的就是ArrayList，ArrayList支持動(dòng)態(tài)擴(kuò)容匕垫，將數(shù)組的很多操作細(xì)節(jié)都封裝起來了叠蝇。如果實(shí)現(xiàn)知道數(shù)據(jù)的大小，建議還是指定好ArrayList的大小年缎，畢竟悔捶，擴(kuò)容涉及到申請(qǐng)內(nèi)存和數(shù)據(jù)遷移等操作，具有一定的開銷单芜。
那么選擇容器還是數(shù)組呢蜕该？
- ArrayList是無法存儲(chǔ)基本數(shù)據(jù)類型，雖說可以存儲(chǔ)包裝類型洲鸠，但是自動(dòng)裝箱和拆箱等操作堂淡，是有一定性能消耗的馋缅。如果特別關(guān)注性能，并且需要使用基本數(shù)據(jù)類型绢淀，建議還是選用數(shù)組萤悴。
- 如果數(shù)據(jù)大小事先知道，并且操作很簡(jiǎn)單皆的，建議是使用數(shù)組覆履。
- 如果是多維，建議使用數(shù)組表示费薄。
- 在普通的業(yè)務(wù)開發(fā)中硝全，使用容器就已經(jīng)足夠了，省時(shí)省力楞抡。但是如果開發(fā)的是底層框架等伟众，建議還是使用數(shù)組。
多維數(shù)組
對(duì)于一個(gè)m * n的二維數(shù)組arr[i][j]召廷，其中i < m,j < n
它的地址計(jì)算公式為base_address + (i * n + j) * data_type_size
動(dòng)態(tài)數(shù)組代碼實(shí)現(xiàn)
/**
* 動(dòng)態(tài)數(shù)組 {@link java.util.ArrayList}
*/
public class DynamicArray<T> implements Iterable<T> {
/** 數(shù)組的實(shí)際大小 */
private int size;
/** 數(shù)組的容量 */
private int capacity;
/** 內(nèi)部維護(hù)的數(shù)組 */
private Object[] data;
/** 默認(rèn)的數(shù)組容量 */
private static final int DEFAULT_CAPACITY = 2 << 3;
public DynamicArray() {
this(DEFAULT_CAPACITY);
}
public DynamicArray(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("Illegal Capacity: " + capacity);
}
this.capacity = capacity;
this.size = 0;
this.data = new Object[capacity];
}
public void add(T t) {
resize(size + 1);
data[size] = t;
size++;
}
public void add(int index, T t) {
checkIndexForAdd(index);
resize(size + 1);
System.arraycopy(data, index, data, index + 1, size - index);
data[index] = t;
size++;
}
public void set(int index, T t) {
checkIndex(index);
data[index] = t;
}
public T remove(int index) {
checkIndex(index);
T t = data(index);
System.arraycopy(data, index + 1, data, index, size - index - 1);
data[--size] = null;
return t;
}
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1) {
return false;
}
remove(i);
return true;
}
public T get(int index) {
checkIndex(index);
return data(index);
}
public void clear() {
for (int i = 0; i < size; i++) {
data[i] = null;
}
size = 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++) {
if (data[i] == null) {
return i;
}
}
} else {
for (int i = 0; i < size; i++) {
if (o.equals(data[i])) {
return i;
}
}
}
return -1;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size() == 0;
}
public boolean contains(T t) {
return indexOf(t) != -1;
}
public Iterator<T> iterator() {
return new Iterator<T>() {
private int index = 0;
public boolean hasNext() {
return index < size;
}
public T next() {
return data(index++);
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
@Override
public String toString() {
if (size == 0) {
return "[]";
}
StringBuilder builder = new StringBuilder();
for (int i = 0; i < size - 1; i++) {
builder.append(data[i] + ", ");
}
builder.append(data[size - 1]);
return String.format("Size: %d, Data: [%s]", size, builder.toString());
}
@SuppressWarnings("unchecked")
private T data(int index) {
return (T) data[index];
}
private void checkIndex(int index) {
if (index < 0 || index >= size) {
throw new ArrayIndexOutOfBoundsException(String.format("Index: %d, Size: %d", index, size));
}
}
private void checkIndexForAdd(int index) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException(String.format("Index: %d, Size: %d", index, size));
}
}
private void resize(int length) {
if (length >= capacity) {
if (capacity == 0) {
capacity = 1;
} else {
capacity = capacity << 1;
}
Object[] newData = new Object[capacity];
System.arraycopy(data, 0, newData, 0, size);
data = newData;
}
}
}
