鏈表的分類：
（1）單鏈表
頭插法：只需要維護一個頭結點即可，常用來模擬堆棧；
尾插法：需要維護頭結點和尾結點，常用來模擬隊列。
（2）雙向鏈表
雙向遍歷，可以用來保存網頁的歷史記錄等；
（3）循環鏈表
經常出現在面試題中，判斷鏈表是否有環。
鏈表的刪除
方式一：維護兩個指針，current（表示當前節點）和previous（表示當前節點的前一個節點）。當current遍歷到要刪除的元素時，執行previous->next = current->next，並刪除current。在刪除時，需要判斷current是否等於head節點。
方式二：維護一個二級指針，Node ** current和一個臨時變量entry。刪除時只需要執行*current = entry -> next. 並刪除entry即可，無需判斷是否為head節點。
基於內存池的鏈表
傳統鏈表的缺點：鏈表在插入過程中會調用系統函數分配內存，然後將該塊內存鏈接到鏈表中。插入操作有三個缺點：
（1）進行頻繁的系統調用，會浪費不少時間；
（2）在鏈表節點分配釋放的過程中會產生很多內存碎片，不利於分配整塊內存；
（3）可能會導致頻繁的cache缺失；
解決方案：
構造一個內存池，每次插入都從內存池中獲取一個節點，每次刪除都將節點放回內存池。這樣做的優點是不存在內存碎片，也不進行系統調用。
鏈表的反轉（面試常考）
（1）思路一：在從前往後遍歷的過程中進行反轉。維護三個指針，分別指向當前節點以及當前節點的前後節點。
（2）思路二：將第三個節點到第N個節點，依次逐節點插入到第一個節點（head節點）之後，最後將第一個節點挪到新表的表尾。
（3）思路三：遞歸的處理head後面的節點，然後再修改head和head後面節點的指向。
倒序打印鏈表
（1）遞歸：倒序打印意味著先最後的元素，然後依次往前打印，可以用遞歸實現這個過程。遞歸的打印head後面所有的節點，然後打印head節點。
（2）棧模擬：遞歸使用系統棧（活動記錄），我們可以用STL中的棧來模擬上述遞歸過程。首先順序遍歷一遍鏈表，將元素放入堆棧，然後依次出棧打印元素。
判斷鏈表是否有環
（1）如何判斷是否存在環？
解法：設置一對快慢指針，同時從鏈表的頭開始往前遍歷。慢指針一次前進一步，快指針一次前進兩步，如果有環則兩個指針會相遇。
（2）如何知道環的長度？
解法：記錄下問題（1）的碰撞點，快慢指針再從該位置遍歷一遍環。下次碰撞慢指針走過的距離就是環的長度。
（3）如何找出環的連接點在哪裡？
解法：碰撞點到連接點的距離 = 頭指針到連接點的距離，再次從兩點遍歷即可。
（4）帶環鏈表的長度是多少？
解法：問題2+問題3.
間接尋址的基本概念
間接尋址簡單描述就是二級指針的應用。二級指針有三個含義：指向指針的指針、一維數組、二維數組。間接尋址在此特指其一維數組的含義。
間接尋址是數組和鏈表的組合。既保留了數組的許多優點，又獲得了鏈表的重要特色。首先，可以根據索引在O(1)的時間內訪問每個元素。其次，可以采用二分在對數時間內對一個有序表進行搜索。最後，在諸如插入和刪除操作期間不必對元素進行實際的移動。間接尋址使用指針數組來跟蹤每一個元素，對元素本身如何分配不設限制（可離散可連續）。
間接尋址的應用
（1）內存池
自構建等塊內存池，每一個指針分別指向每一塊內存的首地址。內存池可以避免內存碎片和系統調用。
（2）散列鏈表
如果指針指向的元素包含next指針，則間接尋址變成了散列鏈表。
模擬指針的基本概念
模擬指針簡單描述就是利用數組的下標當指針。模擬指針的最大用途是解決並查集問題。
（1）實現一：首先構造一個節點數組，節點包含兩個域：data和link。link域指向數組中的其他節點。和間接尋址有相似之處。
（2）實現二：數組只包含link域，可以用來模擬樹。
等價類的定義
定義：假定有一個具有n個元素的集合U，另有一個具有r個關系的集合R。如果(a,b)屬於R，則元素a和b是等價的。等價類是指相互等價元素的最大集合。換句話說，將集合U根據關系進行劃分，類內的元素等價，可以看做是一種聚類。
離線等價類：已知n和R，確定所有的等價類。
在線等價類：初始時有n個元素，每個元素都屬於一個獨立的等價類。然後不停的執行Find和Union操作向R中添加新關系。通常被稱為並查集問題。
並查集的基本概念
並查集的操作：
（1）Find：查詢元素a和b是否屬於同一類；
（2）Union：合並元素a和b所在的類。
並查集的實現：
采用方式二的模擬指針。數組的下標即表示指針，指針的指向使並查集構成了一棵虛擬的森林。但是並查集不關注每棵樹的形狀以及相互指向關系，只關注最終的根節點以及該樹的元素個數或者高度。
並查集的優化：
可以根據重量規則或者高度規則對並查集的操作進行優化。
