面試官：你能說說 LinedList 嗎？
Python 小星：LinedList 數據結構是鏈表，查詢慢，增刪快。
面試官：那 LinkedList 是單向鏈表還是雙向鏈表？
Python 小星：雙向鏈表
面試官：那 LinkedList 是雙向循環鏈表嗎？
Python 小星：......
面試官：沒事，那我問你 LinkedList 為什麼不用單鏈表，而是用雙鏈表？
Python 小星：......
面試官：那 LinkedList 刪除元素，默認是刪除最後一個還是第一個元素？
Python 小星：最後一個
面試官：回去等消息吧
如果你對鏈表不是很熟悉，可以先看看 @Python大星 之前的文章
這裡用圖簡單帶過：
1、單鏈表
2、雙向鏈表
3、循環鏈表
單鏈表 和 雙向鏈表的區別？？？
① 刪除單鏈表中的某個結點時，一定要得到待刪除結點的前驅，得到該前驅有兩種方法，第一種方法是在定位待刪除結點的同時一路保存當前結點的前驅。第二種方法是在定位到待刪除結點之後，重新從單鏈表表頭開始來定位前驅。儘管通常會採用方法一。但其實這兩種方法的效率是一樣的，指針的總的移動操作都會有 2*i 次。而如果用雙向鏈表，則不需要定位前驅結點。因此指針總的移動操作為 i 次。
② 查找時也一樣，我們可以借用二分法的思路，從 head（首節點）向後查找操作和 last（尾節點）向前查找操作同步進行，這樣雙鏈表的效率可以提高一倍。
相信不少小夥伴在瀏覽其他博客時，會看到有的地方說 LinkedList 是雙向鏈表，有的地方說是雙向循環鏈表。這個各有其道理，jdk 1.6 ，LinkedList 是雙向循環鏈表，從 jdk 1.7 後，LinkedList 是簡單的雙向鏈表。下面我們主要以 jdk 1.8 的 LinkedList 說起。
LinkedList 源碼解析
1、類的屬性
實際元素個數，首節點，尾節點
2、 Node 的靜態內部類
3、構造函數
4、查找 - get
先校驗 index 的有效性
在查找時，先比較 index 與 （size >> 1），即 index 與 size 中間值比較。
如果 index 較小，則從 first 開始往 last 方向遍歷；
如果 index 較大，則從 last 開始往 first 方向遍歷。
5、添加 - add
注意：當從指定位置添加元素，其中可能會使用 node 方法，從查找中我們可以知道，查找當前 index 對應的 node 元素，需要遍歷鏈表，如果增加的元素在中間，在大數據量下，花費時間可能比 ArrayList 要多。
① 插入到第一個元素中 - linkFirst
新添加的元素，前節點 pre 為 null，後節點 next 為原 first 節點。
新的 first 節點為當前添加的 new。
判斷 first 是否為空，即添加的 new 是否是第一個元素，
如果為空，則 last 節點 為 當前節點 new；
如果不為空，last 節點不變，原 first 的前節點 pre 變更為 new，後節點 next 不變。
② 插入到最後一個元素中 - linkLast
新添加的元素後節點 next 為 null，前節點 pre 為原 last 節點。
新的 last 節點為當前添加的 new。
判斷 last 是否為空，即添加的 new 是否是第一個元素，
如果為空，則 first 節點為當前節點 new ；
如果不為空，則原 last 節點的後節點 next 為當前節點 new
③ 在非空節點前插入元素 - linkBefore
和 linkFirst 原理一樣
6、修改
先校驗 index 的有效性
然後 node 方法返回當前 index 對應的 node 值
最後給原 node 值賦予新的 element
7、刪除
我們可以看到 LinkedList 默認是從 first 節點開始刪除數據的
@Python大星 | 文
