### 概述 動態數組,棧,隊列底層都是依托于靜態數組,靠resize解決固定容量問題.而鏈表是真正的動態數據結構. * 鏈表是最簡單的動態數據結構. * 更深入的理解引用(或者指針). * 更深入的理解遞歸. * 輔助組成其他數據結構 . ### 鏈表Linked list * 數據存儲在"節點"(Node)中,當一個節點的next是NULL,那么這個節點就是最后一個節點.  * 優點:真正的動態,不需要處理固定容量的問題.需要多少的數據,就生成多少個節點. * 缺點:喪失了隨機訪問的能力. ### 數組和鏈表的對比 #### 數組 * 數組對號用于索引有語意的情況 . scores[2] * 最大優點:支持快速查詢. #### 鏈表 * 鏈表不適合用于索引有語意的情況. * 最大優點:動態. ### 向鏈表中添加元素 和數組不同,數組在尾部添加元素比較方便,而鏈表是在頭部添加元素比較方便 . #### 在鏈表頭添加元素  #### 為鏈表設立虛擬頭結點 在向鏈表頭添加元素和在鏈表其他位置添加元素邏輯上會有差別,為什么對鏈表頭添加元素會有差別呢?因為在向鏈表添加元素的時候,需要找到鏈表待添加位置之前的一個節點,但是對于鏈表頭來說,它沒有之前的一個節點. 這時候就需要虛擬的頭結點了(dummyHead).這個dummyHead對用戶來說是沒有意義的,只是方便我們編寫邏輯.當有了dummyHead之后我們就不要對頭結點進行特殊的處理了.  #### 在鏈表中間添加元素  在鏈表中操作的順序很重要  #### 鏈表元素的刪除(需要虛擬頭結點) 找到待刪除元素之前的那個節點.  ### 時間復雜度 鏈表的增刪改查的時間復雜度都是O(n)的,只對鏈表頭操作是O(1) .對于鏈表來說,適合做的事情,不去修改,查也別查任意位置的元素,只查鏈表頭,增加和刪除也只對鏈表頭進行操作.因為鏈表是動態的,所以不會占用大量的內存空間,具有一定的優勢. #### 添加操作 * addLast(e) //O(n) * addFirst(e) //O(1) * add(index e) //O(n/2) = O(n) #### 刪除操作 * removeLast(e) //O(n) * removeFirst(e) //O(1) * remove(index e) //O(n/2) = O(n) #### 修改操作 * set(index e) //O(n) #### 查找操作 鏈表中不用實現find()方法,因為就算拿到了索引,也沒辦法快速訪問. * get(index) //O(n) * contains(e) //O(n)