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

前言

開篇一張圖，知識全靠吹！

開篇點個贊，博主能上天！

本系列文章已收錄到github：

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

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

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

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

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

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

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

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

我認為主要有兩點：

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

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

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

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

3.1 添加元素

• 中間插入

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

  

  

• 尾部插入

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

  

  

?

3.2 刪除元素

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

?

3.3 更新元素

?

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

3.4 讀取元素

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

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

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

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

5. 參考

《漫畫算法》

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

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

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

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

如果你對我的這個系列感興趣可以關(guān)注我的公眾號，帶你走上”超神之路、拿高薪offer、當上技術(shù)專家、出任個大廠、迎娶白富美、走上人生巔峰，想想還有點小激動。” (哈哈，請允許我吹個