什麼是數據結構和算法
很多教材或者教程再開篇的時候都會來介紹這兩個概念，但是概念畢竟是抽象的，所以我們不需要死扣定義，畢竟我們不是為了考試而學的，但這並不是說我們不需要理解其概念，我們只是說不要陷入概念的怪圈。
下面我們來介紹一下相關概念：
1. 數據結構包括數據對象集以及它們在計算機中的組織方式，即它們的邏輯結構和物理存儲結構，一般我們可以認為數據結構指的是一組數據的存儲結構。
2. 算法就是操作數據的方法，即如何操作數據效率更高，更節省資源。這只是抽象的定義，我們來舉一個例子，你有一批貨物需要運走，你是找小轎車來運還是找卡車來運？這就是數據結構的範疇，選取什麼樣的結構來存儲；至於你貨物裝車的時候是把貨物堆放在一起還是分開放這就是算法放到範疇了，如何放置貨物更有效率更節省空間。
數據結構和算法看起來是兩個東西，但是我們為什麼要放在一起來說呢？那是因為數據結構和算法是相輔相成的，數據結構是為算法服務的，而算法要作用在特定的數據結構之上，因此，我們無法孤立數據結構來講算法，也無法孤立算法來講數據結構。
在學習算法之前我們先來學習幾個最基本的數據結構，這是後續學習其他數據結構和算法的基礎，也就是我們今天要來學習的：數組，鍊表，棧，隊列。這個四個數據結構又可稱之為線性表數據結構。
線性表概念
所謂的線性表，就是將數據排成像一條長線一樣的結構，數組，鍊表，棧，隊列都是線性表結構，線性表上的每個數據最多只有前後兩個方向，下面以一幅圖的形式來展現一下線性表結構
與這種線性結構對應的就是非線性結構，比如後續要學習的數，堆，圖等，在這些非線性數據結構中，數據之間並不是簡單的前後關係，如下圖：
好，理解完線性表的概念之後，接下來正式學習今天的四個數據結構
數組
概念
數組是一種線性表數據結構，它用一組連續的內存空間，來存儲一組具有相同類型的數據。這裡我們要抽取出三個跟數組相關的關鍵詞：線性表，連續內存空間，相同數據類型；數組具有連續的內存空間，存儲相同類型的數據，正是該特性使得數組具有一個特性：隨機訪問。但是有利有弊，這個特性雖然使得訪問數組邊得非常容易但是也使得數組插入和刪除操作會變得很低效，插入和刪除數據後為了保證連續性，要做很多數據搬遷工作。
邏輯結構和物理結構
所謂的數組的邏輯結構指的是我們可以用什麼的表示方式來描述數組元素，比如有一個數組 a,數組中有 n 個元素，我們可以用(a1,a2,a3,.....an)來描述數組中的每個元素，當然後面我們會將具體如何訪問數組中的每個元素。數組的物理結構指的是數組元素實際的存儲形式，當然了從概念我們可以看出數組的物理存儲空間是一塊連續的內存單已，為了說明白這個事情，這裡給大家準備了一副圖
從圖中我們可以看出訪問數組中的元素是通過下標來訪問的，那是如何做到的呢？
1.數組元素的訪問
我們拿一個長度為 10 的數組來舉例，int [] a= new int[10]，在下面的圖中，計算機給數組分配了一塊連續的空間，100-139，其中內存的起始地址為baseAddress=100
我們知道，計算機給每個內存單元都分配了一個地址，通過地址來訪問其數據，因此要訪問數組中的某個元素時，首先要經過一個尋址公式計算要訪問的元素在內存中的地址：
a[i] = baseAddress + i * dataTypeSize
其中 dataTypeSize 代表數組中元素類型的大小，在這個例子中，存儲的是 int 型的數據，因此 dataTypeSize=4 個字節
2.數組下標為什麼從 0 開始
數組的下標為什麼要從 0 開始而不是從 1 開始呢？
從數組存儲的內存模型上來看，"下標"最確切的定義應該是"偏移（offset）"。前面也講到，如果用 array 來表示數組的首地址，array[0] 就是偏移為 0 的位置，也就是首地址，array[k] 就表示偏移 k 個 type_size 的位置，所以計算 array[k] 的內存地址只需要用這個公式:
array[k]_address = base_address + k * type_size
但是如果下標從 1 開始，那麼計算 array[k]的內存地址會變成：array[k]_address = base_address + (k-1)*type_size
對比兩個公式，不難發現從數組下標從 1 開始如果根據下標去訪問數組元素，對於 CPU 來說，就多了一次減法指令。
當然另一方面也是由於歷史原因，c 語言設計者使用 0 開始作為數組的下標，後來的高級語言沿用了這一設計。
數組的特點
1.高效的隨機訪問
通過前面的學習我們已經知道，數組元素的訪問是通過下標來訪問的，計算機通過數組的首地址和尋址公式能夠很快速的找到想要訪問的元素
2.低效插入和刪除
前面我們已經講到數組是一段連續的內存空間，因此為了保證數組的連續性會使得數組的插入和刪除的效率變的很低，下面我們來分析一下，
插入
假設數組的長度為 n，現在如果我們需要將一個數據插入到數組中的第 k 個位置。為了把第 k 個位置騰出來給新來的數據，我們需要將第 k～n 這部分的元素都順序地往後挪一位。如下圖所示：
那數組插入有沒有相對優化的方案呢？
如果數組中的數據是有序的，我們在某個位置插入一個新的元素時，就必須按照剛才的方法搬移 k 之後的數據。但是，如果數組中存儲的數據並沒有任何規律，數組只是被當作一個存儲數據的集合。在這種情況下，如果要將某個數組插入到第 k個位置，為了避免大規模的數據搬移，我們還有一個簡單的辦法就是，直接將第 k位的數據搬移到數組元素的最後，把新的元素直接放入第 k 個位置。這種處理思想會在快排中用到
刪除
如果我們要刪除第 k 個位置的數據，為了內存的連續性，也需要搬移數據，不然中間就會出現空洞，內存就不連續了。
實際上，在某些特殊場景下，我們並不一定非得追求數組中數據的連續性。如果我們將多次刪除操作集中在一起執行，刪除的效率是不是會提高很多呢？舉個例子數組 a[6] 中存儲了 6 個元素：a1,a2,a3,a4,a5,a6。現在，我們要依次刪除 a1,a2 這兩個元素。
為了避免 a3,a4,a5,a6 這幾個數據會被搬移兩次，我們可以先記錄下已經刪除的數據。每次的刪除操作並不是真正地搬移數據，只是記錄數據已經被刪除。當數組沒有更多空間存儲數據時，我們再觸發執行一次真正的刪除操作，這樣就大大減少了刪除操作導致的數據搬移。
如果你了解 JVM，你會發現，這不就是 JVM 標記清除垃圾回收算法的核心思想嗎？
沒錯，數據結構和算法的魅力就在於此，很多時候我們並不是要去死記硬背某個數據結構或者算法，而是要學習它背後的思想和處理技巧，這些東西才是最有價值的。如果你細心留意，不管是在軟體開發還是架構設計中，總能找到某些算法和數據結構的影子
數組的應用
針對數組類型，很多語言都提供了容器類，比如 Java 中的 ArrayList、C++ STL 中的 vector。在項目開發中，什麼時候適合用數組，什麼時候適合用容器呢？
這裡我拿 Java 語言來舉例。如果你是 Java 工程師，幾乎天天都在用 ArrayList，對它應該非常熟悉。那它與數組相比，到底有哪些優勢呢？
我個人覺得，ArrayList 最大的優勢就是可以將很多數組操作的細節封裝起來。比如前面提到的數組插入、刪除數據時需要搬移其他數據等。另外，它還有一個優勢，就是 支持動態擴容 。數組本身在定義的時候需要預先指定大小，因為需要分配連續的內存空間。如果我們申請了大小為 10 的數組，當第 11 個數據需要存儲到數組中時我們就需要重新分配一塊更大的空間，將原來的數據複製過去，然後再將新的數據插入。如果使用 ArrayList，我們就完全不需要關心底層的擴容邏輯，ArrayList 已經幫我們實現好了。每次存儲空間不夠的時候，它都會將空間自動擴容為 1.5 倍大小。不過，這裡需要注意一點，因為擴容操作涉及內存申請和數據搬移，是比較耗時的。所以，如果事先能確定需要存儲的數據大小，最好在創建ArrayList 的時候事先指定數據大小。
如果你對以上關於 ArrayList 的講解不太明白，完全不用擔心，因為接下來我們就針對 java 中 ArrayList 底層操作邏輯進行分析，理解數組的應用及 ArrayList 底層的擴容邏輯。
1.ArrayList 源碼分析
首先我們要明確，ArrayList 底層是採用數組來進行數據的存儲，其次 ArrayList 提供了相關的方法來對底層數組中的元素進行操作，包括數據的獲取，數據的插入，數據的刪除等，此次課程中不會完全講解所有的操作，筆者將會從兩個個方面來進行 ArrayList 底層源碼發剖析。
2.容器構建及添加元素
這裡有一段非常簡短的代碼
publicstaticvoidmain(String[] args){//初始化集合List<String> list = new ArrayList<String>(); //向集合中添加元素 list.add("itcast"); }
下面我們以斷點調試的方式查看一下，當我們創建集合對象的時候發生了什麼事
通過分析可以知道：
1：創建 ArrayList 時採用默認的構造函數創建集合然後往裡添加元素，第一次添加時將數組擴容到 10 的大小，之後添加元素都不會在擴容，直到第 11 次添加然後擴容 1.5 倍取整，此後如果需要擴容都是 1.5 倍取整，但是擴容到的最大值是Integer.MAX_VALUE
2：每次擴容時都會創建一個新的數組，然後將原數組中的數據搬移到新的數組中所以回到開始我們所說的： 如果事先能確定需要存儲的數據大小，最好在創建ArrayList 的時候事先指定數據大小
我們可以查看 ArrayList 的帶參構造函數：
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {//直接使用傳遞的容量大小創建數組，這樣的話只會在不夠存儲的時候才會需要擴容this.elementData = new Object[initialCapacity];} elseif (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA; } else {thrownew IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
比如我們要從資料庫中取出 10000 條數據放入 ArrayList。我們看下面這幾行代碼，你會發現，相比之下，事先指定數據大小可以省掉很多次內存申請和數據搬移操作。
ArrayList<User> users = new ArrayList(10000);for (int i = 0; i < 10000; ++i) {users.add(xxx); }
3.獲取元素
接下來我們寫一段代碼來分析一下從集合中獲取元素
publicstaticvoidmain(String[] args){//初始化集合List<String> list = new ArrayList<String>(1); //向集合中添加元素 list.add("itcast"); //獲取剛剛存入的元素 String ele = list.get(0); }
分析查看集合的 get 方法
到這裡我們關於 ArrayList 的底層源碼解析就結束了，當然了我們只分析了ArrayList 中很小一部分源碼，它還提供了很多的方法，大家不妨自己去分析分析看！同時通過我們的分析，你能不能自己手動實現一個基於數組並且支持動態擴容的集合類呢？寫寫看吧！
作為高級語言編程者，是不是數組就無用武之地了呢？當然不是，有些時候，用數組會更合適些，我總結了幾點自己的經驗。
1.Java ArrayList 無法存儲基本類型，比如 int、long，需要封裝為 Integer、Long 類，而 Autoboxing、Unboxing 則有一定的性能消耗，所以如果特別關注性能，或者希望使用基本類型，就可以選用數組。
2.如果數據大小事先已知，並且對數據的操作非常簡單，用不到 ArrayList 提供的大部分方法，也可以直接使用數組。
我總結一下，對於業務開發，直接使用容器就足夠了，省時省力。畢竟損耗一丟丟性能，完全不會影響到系統整體的性能。但如果你是做一些非常底層的開發，比如開發網絡框架，性能的優化需要做到極致，這個時候數組就會優於容器，成為首選。
至此，數組部分的學習就完成了，接下來我們進入鍊表的學習。