[TOC] # 鏈表 定義： * 是一種線性結構 * 最簡單的動態數據結構 * 更深入的理解引用（或者指針） * 更深入的理解遞歸 * 輔助組成其它數據結構 * 數據存儲在“節點”（Node）中 ``` class Node { $e; Node next;---------指向下一個節點 } ```  # 鏈表的優缺點 優點：真正的動態，不需要處理固定容量的問題 缺點：喪失了隨機訪問的能力 原因： * 在計算機底層，數組是開辟連續的一段內存空間，是連續的，所以可以通過索引快速找到 * 鏈表不是一塊連續的內存空間，是通過指針指向下一個地址，將一系列不連續的內存聯系起來，將那種碎片內存進行合理地利用，解決空間的問題。 # 鏈表的類型 * 單向鏈表 > 單向鏈表包含兩個域，一個是信息域，一個是指針域。也就是單向鏈表的節點被分成兩部分，一部分是保存或顯示關于節點的信息，第二部分存儲下一個節點的地址，而最后一個節點則指向一個空值  * 雙向鏈表 > 每個節點有兩個鏈接，一個是指向前一個節點（當此鏈接為第一個鏈接時，指向的是空列表或空值），另一個則指向后一個節點（當此鏈接為最后一個鏈接時，指向的是空值或空列表）。意思就是說雙向鏈表有兩個指針，一個是指向前一個節點的指針，另一個則指向后一個節點的指針 >  * 循環鏈表 > 循環鏈表就是首節點和末節點被連接在一起。循環鏈表中的第一個節點之前就是最后一個節點，反之亦然 >