手撕數據結構與算法-數組

前言

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

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

本系列文章已收錄到github：

• 手撕數據結構與算法

1. 什么是數組？

數組是數據結構中最簡單、最常用的數據結構，是一種線性表數據結構，在內存中是一塊連續的存儲空間，是有限個相同類型變量所組成的有序集合。數組中的每一個變量叫做元素。

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

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

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

2. 數組的優缺點

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

我認為主要有兩點：

• 連續的存儲空間
• 線性表結構

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

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

3. 數組的基本操作

3.1 添加元素

• 中間插入

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

  

  

• 尾部插入

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

  

  

?

3.2 刪除元素

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

?

3.3 更新元素

?

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

3.4 讀取元素

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

4. 容器能夠代替數組嗎？

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

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

5. 參考

《漫畫算法》

《數據結構與算法之美》

6.結尾求關注環節

在我看來后端程序員應該學的有三大基礎知識"數據結構與算法"、"計算機系統"、"操作系統Linux"。在這個互聯網寒冬時代，是不是我們的衣服穿得不夠多？徹夜難眠的我（純屬扯淡，哈哈）決定帶領大家一起學習三大基礎知識，本次開篇系列是《手撕數據結構與算法》，每一個系列更完就會開啟下一個系列，大家不要著急。可以關注我的公眾號，持續追更、持續學習。

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

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