前言

開篇一張圖，知識(shí)全靠吹！

為華容等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及華容網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為成都做網(wǎng)站、成都網(wǎng)站制作、成都外貿(mào)網(wǎng)站建設(shè)、華容網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

開篇點(diǎn)個(gè)贊，博主能上天！

本系列文章已收錄到github：

• 手撕數(shù)據(jù)結(jié)構(gòu)與算法

1. 什么是數(shù)組？

數(shù)組是數(shù)據(jù)結(jié)構(gòu)中最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)，是一種線性表數(shù)據(jù)結(jié)構(gòu)，在內(nèi)存中是一塊連續(xù)的存儲(chǔ)空間，是有限個(gè)相同類型變量所組成的有序集合。數(shù)組中的每一個(gè)變量叫做元素。

線性表：線性表從字面意義上來理解是數(shù)據(jù)的排列像一條線的結(jié)構(gòu)，只有前后兩個(gè)方向。線性表中的元素都是一對(duì)一的關(guān)系，除了首尾元素外，其他元素都是首尾相連的。除了數(shù)組，鏈表、隊(duì)列、棧也是線性表結(jié)構(gòu)的。

以整型數(shù)組為例，我們new一個(gè)整型數(shù)組int[] array = new int[]{1,2,3,4};，數(shù)組內(nèi)的元素存儲(chǔ)的元素是1、2、3、4。那么數(shù)組的存儲(chǔ)形勢(shì)就如下圖：

在上圖中粉色的格子代表已經(jīng)被占用了的存儲(chǔ)單元，綠色的格子代表數(shù)組的存儲(chǔ)位置，白色的格子代表空閑的存儲(chǔ)單元。數(shù)組的下標(biāo)是從0開始的。所以元素和下標(biāo)的對(duì)應(yīng)關(guān)系是：

2. 數(shù)組的優(yōu)缺點(diǎn)

談起數(shù)組的優(yōu)點(diǎn)，我相信大部分的人都會(huì)說隨機(jī)訪問這個(gè)堪稱殺手锏的特性，那么它為什么能夠做到隨機(jī)訪問呢？

我認(rèn)為主要有兩點(diǎn)：

• 連續(xù)的存儲(chǔ)空間
• 線性表結(jié)構(gòu)

正因?yàn)樗窃趦?nèi)存中是一塊連續(xù)的存儲(chǔ)空間，并且是線性表結(jié)構(gòu)，前后元素都是一一對(duì)應(yīng)的，所以才能夠讓他擁有隨機(jī)訪問的特性。在上一篇文章數(shù)據(jù)結(jié)構(gòu)與算法-開篇當(dāng)中我們介紹了時(shí)間復(fù)雜度和空間復(fù)雜度，這里就不對(duì)說了，比如我們要查找上邊的數(shù)組中的第三個(gè)元素，那么打印出array[2]就能夠獲取到第三個(gè)元素值，這里輸出的是3，因?yàn)閿?shù)組支持隨機(jī)訪問，所以根據(jù)下標(biāo)隨機(jī)訪問的時(shí)間復(fù)雜度為O(1)，因?yàn)樗牟檎也僮髦粓?zhí)行了一次。

這樣的結(jié)構(gòu)使它的查詢操作非常的方便，有利也有弊，它的插入、刪除操作就會(huì)變得低效，因?yàn)橐ＷC數(shù)據(jù)的連續(xù)性，所以執(zhí)行插入、刪除操作就需要做大量的數(shù)據(jù)搬移工作。如果這個(gè)時(shí)候一個(gè)數(shù)組的隨機(jī)訪問正好訪問到?jīng)]有值得下標(biāo)上就會(huì)獲取不到值。如果不搬移數(shù)據(jù)將中間的空洞補(bǔ)充上，那么內(nèi)存就不連續(xù)了。我們?cè)跀?shù)組的操作中在詳細(xì)介紹。

3. 數(shù)組的基本操作

3.1 添加元素

• 中間插入

  中間插入稍微復(fù)雜一些，每個(gè)元素都有自己的下標(biāo)，如果一個(gè)元素想要插入到數(shù)組的中的除首尾的位置，那么插入的該位置上的元素都要向后移動(dòng)，給新的位置騰出空間，保證連續(xù)性。

  

  

• 尾部插入

  尾部插入這種情況比較簡(jiǎn)單，直接把元素放到數(shù)組尾部的空閑位置即可，等同于更新元素的操作。

  

  

?

3.2 刪除元素

刪除操作和插入操作的過程正好相反，如果刪除的元素在數(shù)組的中間，那么其后的元素都要向前移動(dòng)。

3.3 更新元素

?

這里更新元素的時(shí)間復(fù)雜度為O(1)。

3.4 讀取元素

這里讀元素的時(shí)間復(fù)雜度為O(1)。

4. 容器能夠代替數(shù)組嗎？

針對(duì)數(shù)組類型，很多語言都提供了容器類，例如Java的List，如果你是一個(gè)Java程序員，那么你應(yīng)該清楚ArrayList，對(duì)它應(yīng)該非常的熟悉，和數(shù)組對(duì)比它有哪些優(yōu)勢(shì)呢？為什么開發(fā)的過程中經(jīng)常使用它，大的優(yōu)勢(shì)就是封裝了對(duì)數(shù)組的操作，例如前面說的插入和刪除，如果使用ArrayList還有一個(gè)優(yōu)勢(shì)是它支持動(dòng)態(tài)擴(kuò)容，當(dāng)容器不夠大的時(shí)候會(huì)自動(dòng)擴(kuò)容1.5倍，我們完全不需要關(guān)心底層的實(shí)現(xiàn)邏輯。那么什么時(shí)候使用數(shù)組更合適呢？有一下幾點(diǎn)：

• ArrayList無法存儲(chǔ)基本數(shù)據(jù)類型，例如int、long需要封裝為Integer、Long。這里的裝箱、拆箱操作有一定的性能損耗，如果特別關(guān)注性能，希望使用基本類型，那么就可以選擇數(shù)組。
• 對(duì)數(shù)據(jù)只是簡(jiǎn)單的存儲(chǔ)操作，那么選擇數(shù)組效率更好些。
• 當(dāng)做一些底層開發(fā)的時(shí)候數(shù)組可能用的比較多，比如一些框架。都是比較要求性能的。

5. 參考

《漫畫算法》

《數(shù)據(jù)結(jié)構(gòu)與算法之美》

6.結(jié)尾求關(guān)注環(huán)節(jié)

在我看來后端程序員應(yīng)該學(xué)的有三大基礎(chǔ)知識(shí)"數(shù)據(jù)結(jié)構(gòu)與算法"、"計(jì)算機(jī)系統(tǒng)"、"操作系統(tǒng)Linux"。在這個(gè)互聯(lián)網(wǎng)寒冬時(shí)代，是不是我們的衣服穿得不夠多？徹夜難眠的我（純屬扯淡，哈哈）決定帶領(lǐng)大家一起學(xué)習(xí)三大基礎(chǔ)知識(shí)，本次開篇系列是《手撕數(shù)據(jù)結(jié)構(gòu)與算法》，每一個(gè)系列更完就會(huì)開啟下一個(gè)系列，大家不要著急?？梢躁P(guān)注我的公眾號(hào)，持續(xù)追更、持續(xù)學(xué)習(xí)。

注意、注意 前方高能======>

如果你對(duì)我的這個(gè)系列感興趣可以關(guān)注我的公眾號(hào)，帶你走上”超神之路、拿高薪offer、當(dāng)上技術(shù)專家、出任個(gè)大廠、迎娶白富美、走上人生巔峰，想想還有點(diǎn)小激動(dòng)?！?(哈哈，請(qǐng)?jiān)试S我吹個(gè)

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。