?2016-2026 Matools All rights reserved,
粵ICP備17059708號
面試的時候，常常會問數(shù)組和鏈表的區(qū)別，很多人都回答說，“鏈表適合插入、刪除，時間復雜度O(1)；數(shù)組適合查找，查找時間復雜度為O(1)”。實際上，這種表述是不準確的。數(shù)組是適合查找操作，但是查找的時間復雜度并不為O(1)。即便是排好序的數(shù)組，你用二分查找，時間復雜度也是O(logn)。所以，正確的表述應該是，數(shù)組支持隨機訪問，根據(jù)下標隨機訪問的時間復雜度為O(1)。
每一種編程語言中，基本都會有數(shù)組這種數(shù)據(jù)類型。不過，它不僅僅是一種編程語言中的數(shù)據(jù)類型，還是一種最基礎的數(shù)據(jù)結構。盡管數(shù)組看起來非?；A、簡單，但是我估計
很多人都并沒有理解這個基礎數(shù)據(jù)結構的精髓。在大部分編程語言中，數(shù)組都是從0開始編號的，但你是否下意識地想過，為什么數(shù)組要從0開始編號，而不是從1開始呢？
從1開始不是更符合人類的思維習慣嗎？帶著這個問題來學習接下來的內(nèi)容,帶著問題去學習往往效果會更好?。?！
什么是數(shù)組？我估計你心中已經(jīng)有了答案。不過，我還是想用專業(yè)的話來給你做下解釋。
數(shù)組（Array）是一種線性表數(shù)據(jù)結構。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù)
。這個定義里有幾個關鍵詞，理解了這幾個關鍵詞，我想你就能徹底掌握數(shù)組的概念了。下面就從我的角度分別給你“點撥”一下。
第一是線性表（Linear List）。顧名思義，線性表就是數(shù)據(jù)排成像一條線一樣的結構。每個線性表上的數(shù)據(jù)最多只有前和后兩個方向。其實除了數(shù)組，鏈表、隊列、棧
等也是線性表結構。而與它相對立的概念是非線性表，比如二叉樹、堆、圖等。之所以叫非線性，是因為，在非線性表中，數(shù)據(jù)之間并不是簡單的前后關系。
第二個是連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)
。正是因為這兩個限制，它才有了一個堪稱“殺手锏”的特性：“隨機訪問”。但有利就有弊，這兩個限制也讓數(shù)組的很多操作變得非常低效，比如要想在數(shù)組中刪除、插入一個數(shù)據(jù)，
數(shù)組為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，會導致插入、刪除這兩個操作比較低效,相反的數(shù)組查詢則高效
數(shù)組java代碼：
package array; /** * 1) 數(shù)組的插入、刪除、按照下標隨機訪問操作； * 2）數(shù)組中的數(shù)據(jù)是int類型的； * * Author:
Zheng * modify: xing, Gsealy */ public class Array { //定義整型數(shù)據(jù)data保存數(shù)據(jù) public
int data[]; //定義數(shù)組長度 private int n; //定義中實際個數(shù) private int count; //構造方法，定義數(shù)組大小
public Array(int capacity){ this.data = new int[capacity]; this.n = capacity;
this.count=0;//一開始一個數(shù)都沒有存所以為0 } //根據(jù)索引，找到數(shù)據(jù)中的元素并返回 public int find(int index){
if (index<0 || index>=count) return -1; return data[index]; } //插入元素:頭部插入，尾部插入
public boolean insert(int index, int value){ //數(shù)組中無元素 //if (index == count &&
count == 0) { // data[index] = value; // ++count; // return true; //} // 數(shù)組空間已滿
if (count == n) { System.out.println("沒有可插入的位置"); return false; } //
如果count還沒滿，那么就可以插入數(shù)據(jù)到數(shù)組中 // 位置不合法 if (index < 0||index > count ) {
System.out.println("位置不合法"); return false; } // 位置合法 for( int i = count; i >
index; --i){ data[i] = data[i - 1]; } data[index] = value; ++count; return
true; } //根據(jù)索引，刪除數(shù)組中元素 public boolean delete(int index){ if (index<0 || index
>=count) return false; //從刪除位置開始，將后面的元素向前移動一位 for (int i=index+1; i<count;
++i){ data[i-1] = data[i]; } //刪除數(shù)組末尾元素 這段代碼不需要也可以 /*int[] arr = new
int[count-1]; for (int i=0; i<count-1;i++){ arr[i] = data[i]; } this.data =
arr;*/ --count; return true; } public void printAll() { for (int i = 0; i <
count; ++i) { System.out.print(data[i] + " "); } System.out.println(); } public
static void main(String[] args) { Array array = new Array(5); array.printAll();
array.insert(0, 3); array.insert(0, 4); array.insert(1, 5); array.insert(3, 9);
array.insert(3, 10); //array.insert(3, 11); array.printAll(); } }
GenericArray數(shù)組代碼
public class GenericArray<T> { private T[] data; private int size; //
根據(jù)傳入容量，構造Array public GenericArray(int capacity) { data = (T[]) new
Object[capacity]; size = 0; } // 無參構造方法，默認數(shù)組容量為10 public GenericArray() {
this(10); } // 獲取數(shù)組容量 public int getCapacity() { return data.length; } //
獲取當前元素個數(shù) public int count() { return size; } // 判斷數(shù)組是否為空 public boolean
isEmpty() { return size == 0; } // 修改 index 位置的元素 public void set(int index, T
e) { checkIndex(index); data[index] = e; } // 獲取對應 index 位置的元素 public T get(int
index) { checkIndex(index); return data[index]; } // 查看數(shù)組是否包含元素e public boolean
contains(T e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) {
return true; } } return false; } // 獲取對應元素的下標, 未找到，返回 -1 public int find(T e) {
for ( int i = 0; i < size; i++) { if (data[i].equals(e)) { return i; } } return
-1; } // 在 index 位置，插入元素e, 時間復雜度 O(m+n) public void add(int index, T e) {
checkIndex(index); // 如果當前元素個數(shù)等于數(shù)組容量，則將數(shù)組擴容為原來的2倍 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++; } // 向數(shù)組頭插入元素 public void addFirst(T
e) { add(0, e); } // 向數(shù)組尾插入元素 public void addLast(T e) { add(size, e); } // 刪除
index 位置的元素，并返回 public T remove(int index) { checkIndexForRemove(index); T ret
= data[index]; for (int i = index + 1; i < size; i++) { data[i - 1] = data[i];
} size --; data[size] = null; // 縮容 if (size == data.length / 4 && data.length
/ 2 != 0) { resize(data.length / 2); } return ret; } // 刪除第一個元素 public T
removeFirst() { return remove(0); } // 刪除末尾元素 public T removeLast() { return
remove(size - 1); } // 從數(shù)組中刪除指定元素 public void removeElement(T e) { int index =
find(e); if (index != -1) { remove(index); } } @Override public String
toString() { StringBuilder builder = new StringBuilder();
builder.append(String.format("Array size = %d, capacity = %d \n", size,
data.length)); builder.append('['); for (int i = 0; i < size; i++) {
builder.append(data[i]); if (i != size - 1) { builder.append(", "); } }
builder.append(']'); return builder.toString(); } // 擴容方法，時間復雜度 O(n) private
void resize(int capacity) { T[] newData = (T[]) new Object[capacity]; for (int
i = 0; i < size; i++) { newData[i] = data[i]; } data = newData; } private void
checkIndex(int index) { if (index < 0 || index > size) { throw new
IllegalArgumentException("Add failed! Require index >=0 and index <= size."); }
} private void checkIndexForRemove(int index) { if(index < 0 || index >= size)
{ throw new IllegalArgumentException("remove failed! Require index >=0 and
index < size."); } } }
到這里，就回溯最初的問題：
從數(shù)組存儲的內(nèi)存模型上來看，“下標”最確切的定義應該是“偏移（offset）”。前面也講到，如果用a來表示數(shù)組的首地址，a[0]就是偏移為0的位置，也就是首地址，a[k]就表示偏移k個type_size的位置，所以計算a[k]的內(nèi)存地址只需要用這個公式：
a[k]_address = base_address + k * type_size
但是，如果數(shù)組從1開始計數(shù)，那我們計算數(shù)組元素a[k]的內(nèi)存地址就會變?yōu)椋?br>
a[k]_address = base_address + (k-1)*type_size
對比兩個公式，我們不難發(fā)現(xiàn)，從1開始編號，每次隨機訪問數(shù)組元素都多了一次減法運算，對于CPU來說，就是多了一次減法指令。那你可以思考一下，類比一下，二維數(shù)組的內(nèi)存尋址公式是怎樣的呢？
有興趣的可以在評論區(qū)評論出來哦QAQ
數(shù)組作為非?；A的數(shù)據(jù)結構，通過下標隨機訪問數(shù)組元素又是其非?；A的編程操作，效率的優(yōu)化就要盡可能做到極致。所以為了減少一次減法操作，數(shù)組選擇了從0開始編號，而不是從1開始。
不過我認為，上面解釋得再多其實都算不上壓倒性的證明，說數(shù)組起始編號非0開始不可。所以我覺得最主要的原因可能是歷史原因。
關于數(shù)組，它可以說是最基礎、最簡單的數(shù)據(jù)結構了。數(shù)組用一塊連續(xù)的內(nèi)存空間，來存儲相同類型的一組數(shù)據(jù)，最大的特點就是支持隨機訪問，但插入、刪除操作也因此變得比較低效，平均情況時間復雜度為O(n)。在平時的業(yè)務開發(fā)中，我們可以直接使用編程語言提供的容器類，但是，如果是特別底層的開發(fā)，直接使用數(shù)組可能會更合適。
如果本文對你有一點點幫助，那么請點個贊唄，謝謝~
最后，若有不足或者不正之處，歡迎指正批評，感激不盡！如果有疑問歡迎留言，絕對第一時間回復！
歡迎各位關注我的公眾號，一起探討技術，向往技術，追求技術，說好了來了就是盆友喔...
熱門工具 換一換