面試的時候，常常會問數組和鏈表的區別，很多人都回答說，“鏈表適合插入、刪除，時間複雜度O(1)；數組適合查找，查找時間複雜度為O(1)”。實際上，這種表述是不準確的。數組是適合查找操作，但是查找的時間複雜度並不為O(1)。即便是排好序的數組，你用二分查找，時間複雜度也是O(logn)。所以，正確的表述應該是，數組支持隨機訪問，根據下標隨機訪問的時間複雜度為O(1)。
每一種編程語言中，基本都會有數組這種數據類型。不過，它不僅僅是一種編程語言中的數據類型，還是一種最基礎的數據結構。儘管數組看起來非常基礎、簡單，但是我估計很多人都並沒有理解這個基礎數據結構的精髓。在大部分編程語言中，數組都是從0開始編號的，但你是否下意識地想過，為什麼數組要從0開始編號，而不是從1開始呢？ 從1開始不是更符合人類的思維習慣嗎？帶着這個問題來學習接下來的內容,帶着問題去學習往往效果會更好！！！
什麼是數組？我估計你心中已經有了答案。不過，我還是想用專業的話來給你做下解釋。數組（Array）是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型的數據。這個定義里有幾個關鍵詞，理解了這幾個關鍵詞，我想你就能徹底掌握數組的概念了。下面就從我的角度分別給你“點撥”一下。
第一是線性表（Linear List）。顧名思義，線性表就是數據排成像一條線一樣的結構。每個線性表上的數據最多只有前和后兩個方向。其實除了數組，鏈表、隊列、棧等也是線性表結構。而與它相對立的概念是非線性表，比如二叉樹、堆、圖等。之所以叫非線性，是因為，在非線性表中，數據之間並不是簡單的前後關係。
第二個是連續的內存空間和相同類型的數據。正是因為這兩個限制，它才有了一個堪稱“殺手鐧”的特性：“隨機訪問”。但有利就有弊，這兩個限制也讓數組的很多操作變得非常低效，比如要想在數組中刪除、插入一個數據，數組為了保持內存數據的連續性，會導致插入、刪除這兩個操作比較低效,相反的數組查詢則高效
數組java代碼：
package array;
/**
* 1) 數組的插入、刪除、按照下標隨機訪問操作；
* 2）數組中的數據是int類型的；
*
* Author: Zheng
* modify: xing, Gsealy
*/
public class Array {
//定義整型數據data保存數據
public int data[];
//定義數組長度
private int n;
//定義中實際個數
private int count;
//構造方法，定義數組大小
public Array(int capacity){
this.data = new int[capacity];
this.n = capacity;
this.count=0;//一開始一個數都沒有存所以為0
}
//根據索引，找到數據中的元素並返回
public int find(int index){
if (index<0 || index>=count) return -1;
return data[index];
}
//插入元素:頭部插入，尾部插入
public boolean insert(int index, int value){
//數組中無元素
//if (index == count && count == 0) {
// data[index] = value;
// ++count;
// return true;
//}
// 數組空間已滿
if (count == n) {
System.out.println("沒有可插入的位置");
return false;
}
// 如果count還沒滿，那麼就可以插入數據到數組中
// 位置不合法
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;
}
//根據索引，刪除數組中元素
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];
}
//刪除數組末尾元素 這段代碼不需要也可以
/*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數組代碼
public class GenericArray<T> {
private T[] data;
private int size;
// 根據傳入容量，構造Array
public GenericArray(int capacity) {
data = (T[]) new Object[capacity];
size = 0;
}
// 無參構造方法，默認數組容量為10
public GenericArray() {
this(10);
}
// 獲取數組容量
public int getCapacity() {
return data.length;
}
// 獲取當前元素個數
public int count() {
return size;
}
// 判斷數組是否為空
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];
}
// 查看數組是否包含元素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);
// 如果當前元素個數等於數組容量，則將數組擴容為原來的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++;
}
// 向數組頭插入元素
public void addFirst(T e) {
add(0, e);
}
// 向數組尾插入元素
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);
}
// 從數組中刪除指定元素
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.");
}
}
}到這裏，就回溯最初的問題：
從數組存儲的內存模型上來看，“下標”最確切的定義應該是“偏移（offset）”。前面也講到，如果用a來表示數組的首地址，a[0]就是偏移為0的位置，也就是首地址，a[k]就表示偏移k個type_size的位置，所以計算a[k]的內存地址只需要用這個公式：
a[k]_address = base_address + k * type_size
但是，如果數組從1開始計數，那我們計算數組元素a[k]的內存地址就會變為：
a[k]_address = base_address + (k-1)*type_size
對比兩個公式，我們不難發現，從1開始編號，每次隨機訪問數組元素都多了一次減法運算，對於CPU來說，就是多了一次減法指令。那你可以思考一下，類比一下，二維數組的內存尋址公式是怎樣的呢？有興趣的可以在評論區評論出來哦QAQ
數組作為非常基礎的數據結構，通過下標隨機訪問數組元素又是其非常基礎的編程操作，效率的優化就要盡可能做到極致。所以為了減少一次減法操作，數組選擇了從0開始編號，而不是從1開始。
不過我認為，上面解釋得再多其實都算不上壓倒性的證明，說數組起始編號非0開始不可。所以我覺得最主要的原因可能是歷史原因。
關於數組，它可以說是最基礎、最簡單的數據結構了。數組用一塊連續的內存空間，來存儲相同類型的一組數據，最大的特點就是支持隨機訪問，但插入、刪除操作也因此變得比較低效，平均情況時間複雜度為O(n)。在平時的業務開發中，我們可以直接使用編程語言提供的容器類，但是，如果是特別底層的開發，直接使用數組可能會更合適。
如果本文對你有一點點幫助，那麼請點個讚唄，謝謝~
最後，若有不足或者不正之處，歡迎指正批評，感激不盡！如果有疑問歡迎留言，絕對第一時間回復！
歡迎各位關注我的公眾號，一起探討技術，嚮往技術，追求技術，說好了來了就是盆友喔…
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"
※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線
※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整
※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!