本書：<<漫畫算法小灰的算法之旅>>
作者：魏夢舒（@程序員小灰）
我是將本書中內容，重新整理一遍。基本是書中的內容，方便以后閱讀查看！！！希望喜歡本書的小伙伴們可以相互學習，多多支持！

第二章數據結構基礎

• 什么是數組？
• 什么是鏈表？
• 什么是棧？
• 什么是隊列？
• 什么是散列表？

1、數組是由有限個相同類型的變量所組成的有序集合，它的物理存儲方式是順序存儲，訪問方式是隨機訪問。利用下標查找數組元素的時間復雜度是O(1)，中間插入、刪除數組元素的時間復雜度是O(n)。
2、鏈表是一種鏈式數據結構，由若干節點組成，每個節點包含指向下一節點的指針。鏈表的物理存儲方式是隨機存儲，訪問方式是順序訪問。查找鏈表節點的時間復雜度是O(n)，中間插入、刪除節點的時間復雜度是O(1)。
3、棧是一種線性邏輯結構，可以用數組實現，也可以用鏈表實現。棧包括入棧和出棧操作，遵循先入后出的原則（FILO）。
4、隊列也是一種線性邏輯結構，可以用數組實現，也可以用鏈表實現。隊列包含入隊和出隊操作，遵循先入先出的原則（FIFO）。
5、散列表也叫哈希表，是存儲Key-Value映射的集合。對于某一個Key，散列表可以在接近O(1)的時間內進行讀寫操作。散列表通過哈希函數實現Key和數組下標的轉換，通過開放尋址法和鏈表法來解決哈希沖突。
2.1.1初始數組

• 數組的特點是在內存中順序存儲，因此可以很好地實現邏輯上的順序表。
• 內存是由一個個連續的內存單元組成的，每一個內存單元都有自己的地址。在這些內存單元中，有些被其他數據占用了，有些是空閑的。
• 數組中的每一個元素，都存儲在小小的內存單元中，并且元素之間緊密排列，既不能打亂元素的存儲順序，也不能跳過某個存儲單元進行存儲。
• 下標從0開始，一直到數組長度-1。

2.1.2數組的基本操作
1、讀取元素：根據下標讀取元素的方式——隨機讀取。
2、更新元素：直接利用數組下標，就可以把新值賦給該元素。
3、插入元素：數組的實際元素數量有可能小于數組的長度。
（1）尾部插入：直接把插入的元素放在數組尾部的空閑位置即可，等同于更新元素的操作。
（2）中間插入：先把插入位置及后面的元素向后移動，騰出地方，再把插入的元素放到對應的數組位置上。
（3）超范圍插入：數組擴容。
創建一個新數組，長度是舊數組的2倍。再把舊數組中的元素統統復制過去。
4、刪除元素：和插入操作的過程相反，如果刪除的元素位于數組中間，其后的元素都需要向前挪動1位。
取巧方式：可以把最后一個元素復制到所刪除元素的位置上，然后再刪除掉最后一個元素。這樣一來，無須進行大量的元素移動，時間復雜度降低為O(1)。這種方式只供作為參考，并不是刪除元素時主流的操作方式。
總結：數組適合讀操作多，寫操作少的場景。
2.2什么是鏈表
鏈表（linked list）是一種在物理上非連續、非順序的數據結構。由若干節點所組成。
鏈表在內存中的存儲方式是隨機存儲。采用了見縫插針的方式，鏈表的 每一個節點分布在內存的不同位置，依靠next指針關聯起來。
（1）單向鏈表的每一個節點又包含兩部分。一部分是存放數據的變量data，另一部分是指向下一個節點的指針next。
（2）雙向鏈表，它的每一個節點除了擁有data和next指針，還擁有指向前置節點的pre指針。
2.2.2鏈表的基本操作
1、查找節點：
（1）將查找的指針定位到頭節點。
（2）根據頭節點的next指針，定位到第2個節點。
（3）依次類推，找到所要查詢的節點。
2、更新節點：直接把舊數據替換成新數據即可。
3、插入節點
（1）尾部插入：把最后一個節點的next指針指向新插入的節點即可。
（2）頭部插入：
第一步，把新節點的next指針指向原先的頭節點。
第二步，把新節點變為鏈表的頭節點。
（3）中間插入
第一步，把插入位置的前置節點的next指針指向插入的新節點。
第二步，將新節點的next指針指向前置節點的next指針原先所指向的節點。
只要內存空間允許，能夠插入鏈表的元素是無窮無盡的，不需要像數組那樣考慮擴容的問題。
4、刪除元素
（1）尾部刪除：把倒數第2個節點的next指針指向空即可
（2）頭部刪除：把鏈表的頭節點設為原先頭節點的next指針即可。
（3）中間刪除：把要刪除節點的前置節點的next指針，指向要刪除元素的下一個節點即可。
總結：插入和刪除的時間復雜度都是O(1)。
2.3棧和隊列
2.3.1物理結構和邏輯結構

2.3.2什么是棧？
棧(stack)是一種線性數據結構，棧中的元素只能先入后出（Fast in Last Out，簡稱FILO）。
最早進入的元素存放的位置叫作棧底，最后進入的元素存放的位置叫作棧頂。
2.3.3棧的基本操作
1、入棧（push）
2、出棧（pop）
3、時間復雜度都是O(1)。
2.3.4什么是隊列？
隊列（queue）是一種線性數據結構，隊列中的元素只能先入先出（First in First Out，簡稱FIFO）。隊列的出口端叫作隊頭（front），隊列的入口端叫作隊尾（rear）。
總結：棧和隊列既可以用數組來實現，也可以用鏈表來實現。
2.3.5隊列的基本操作
1、入隊（enqueue）
2、出隊（dequeue）
3、循環隊列
假設一個隊列經過反復的入隊和出隊的操作，還剩下2個元素，在“物理”上分布于數組的末尾位置。這時又有一個新元素將要入隊。在數組不做擴容的前提下，如何讓新元素入隊并確定新的隊尾位置呢？可以開勇已出隊元素留下的空間，讓隊尾指針重新指回數組的首位。這樣一來，整個隊列的元素就“循環”起來了。在物理存儲上，隊尾的位置也可以在隊頭之前。當再有元素入隊時，將其放入數組首位，隊尾指針繼續后移即可。一直到（隊尾下標+1）%數組長度=隊頭下標時，代表此隊列真的已經滿了。需要注意的是，隊尾指針指向的位置永遠空出1位，所以隊列最大容量比數組長度小1。
總結：時間復雜度為O(1)。
2.3.6棧和隊列的應用
1、棧的應用：
（1）實現遞歸的邏輯，棧可以回溯方法的調用鏈。
（2）面包屑導航，使用戶在瀏覽頁面時可以輕松的回溯到上一級或更上一級頁面。
2、隊列的應用：
（1）通常用于對“歷史”的回放，也就是按照“歷史”順序，把“歷史”重演一遍。
（2）在多線程中，爭奪公平鎖的等待隊列，就是按照訪問順序來決定線程在隊列中的次序的。
（3）網絡爬蟲實現網站抓取時，也是把待抓取的網站URL存入對列中，再按照存入對列的順序來依次抓取和解析的。
3、雙端隊列：從隊頭一端可以入隊或出隊，從隊尾一端也可以入隊或出隊。
4、優先隊列：誰的優先級最高，誰先出隊。
2.4神奇的散列表
哈希函數：把Key和數組下標進行轉換的中轉站。
index=HashCode(Key)%Array.length
2.4.3散列表的讀寫操作
1、寫操作（put）:在散列表中插入新的鍵值對。
哈希沖突：通過哈希函數把Key轉化成數組下標，但是，由于數組的長度是有限的，當插入的Entry越來越多時，不同的Key通過哈希函數獲得的下標有可能是相同的。
解決方法：（1）開放尋址法：尋找下一個空檔位置。
（2）鏈表法：HashMap數組的每一個元素不僅是一個Entry對象，還是一個鏈表的頭節點。每一個Entry對象通過next指針指向它的下一個Entry節點。當新來的Entry映射到與之沖突的數組位置時，只需要插入到對應的鏈表中即可。
2、讀操作（get）：通過給定的Key，在散列表中查到對應的Value。
3、擴容(resize):
（1）什么時候進行擴容？當經過多次元素插入，散列表達到一定飽和度時，Key映射位置發生沖突的概率會逐漸提高。這樣一來，大量元素擁擠在相同的數組下標位置，形成很長的鏈表，對后續插入操作和查詢操作的性能都有很大的影響。
（2）影響擴容的因素：

• Capacity，即HashMap的當前長度。
• LoadFactor，即HashMap的負載因子，默認值為0.75f。需要進行擴容的條件如下：HashMap.Size>=Capacity*LoadFactor。

（3）步驟

• 擴容，創建一個新的Entry空數組，長度時原數組的2倍。
• 重新Hash，遍歷原Entry數組，把所有的Entry重新Hash到新數組中。因為長度擴大以后，Hash的規則也隨之改變。
• 經過擴容，原本擁擠的散列表重新變得稀疏，原有的Entry也重新得到了盡可能均勻的分配。
• JDK直接閱讀HashMap類的源碼。
• JDK 8和以前的版本有很大的不同。當多個Entry被Hash到同一個數組下標位置時，為了提升插入和查找的效率，HashMap會把Entry的鏈表轉化為紅黑樹這種數據結構。

總結

以上是生活随笔為你收集整理的漫画算法：小灰的算法之旅的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。