一践啄、LinkedList
一、LinkedList概述
LinkedList是一個簡單的數(shù)據(jù)結構沉御，與ArrayList不同的是往核，他是基于鏈表實現(xiàn)的。
這樣一個簡單的操作：
LinkedListlist=newLinkedList();
list.add("語文: 1");
list.add("數(shù)學: 2");
list.add("英語: 3");
----以雙向鏈表實現(xiàn)嚷节。鏈表無容量限制，但雙向鏈表本身使用了更多空間虎锚，也需要額外的鏈表指針操作硫痰。按下標訪問元素—get(i)/set(i,e) 要悲劇的遍歷鏈表將指針移動到位(如果i>數(shù)組大小的一半，會從末尾移起)窜护。
插入效斑、刪除元素時修改前后節(jié)點的指針即可，但還是要遍歷部分鏈表的指針才能移動到下標所指的位置柱徙，只有在鏈表兩頭的操作—add(), addFirst(),removeLast()或用iterator()上的remove()能省掉指針的移動缓屠。
1.1、get和set函數(shù)
這兩個函數(shù)都調(diào)用了node函數(shù)护侮，該函數(shù)會以O(n/2)的性能去獲取一個節(jié)點
Nodenode(intindex) {//assert isElementIndex(index);if(index<(size>>1)) {Nodex=first;for(inti=0; ix=last;for(inti=size-1; i>index; i--)? ? ? ? ? ? x=x.prev;returnx;? ? }}
就是判斷index是在前半?yún)^(qū)間還是后半?yún)^(qū)間敌完，如果在前半?yún)^(qū)間就從head搜索，而在后半?yún)^(qū)間就從tail搜索羊初。而不是一直從頭到尾的搜索滨溉。如此設計，將節(jié)點訪問的復雜度由O(n)變?yōu)镺(n/2)长赞。
二晦攒、HashMap
2.1、初次見面
當我們執(zhí)行以下操作時：
HashMapmap=newHashMap();
map.put("語文",1);
map.put("數(shù)學",2);
map.put("英語",3);
map.put("歷史",4);
map.put("政治",5);
map.put("地理",6);
map.put("生物",7);
map.put("化學",8);
for(Entryentry:map.entrySet()) {System.out.println(entry.getKey()+":"+entry.getValue());}
運行結果時：政治: 5
生物: 7
歷史: 4
數(shù)學: 2
化學: 8
語文: 1
英語: 3
地理: 6
what得哆！發(fā)生了什么脯颜，那就上個圖吧！
從圖中提取幾個關鍵的信息：基于Map接口實現(xiàn)贩据、允許null鍵/值栋操、非同步、不保證有序(比如插入的順序)乐设、也不保證序不隨時間變化讼庇。
2.2、HashMap的put和get
hashmap初始化時會定義一個table近尚。如果是普通的map的話蠕啄，直接將將item放入到map的對應列當中。但是hashmap呢
三、LinkedHashMap
看下這個代碼
LinkedHashMaplmap=newLinkedHashMap();
lmap.put("語文",1);lmap.put("數(shù)學",2);lmap.put("英語",3);lmap.put("歷史",4);lmap.put("政治",5);lmap.put("地理",6);lmap.put("生物",7);lmap.put("化學",8);
for(Entryentry:lmap.entrySet()) {System.out.println(entry.getKey()+":"+entry.getValue());}
運行結果：語文: 1 數(shù)學: 2 英語: 3 歷史: 4 政治: 5 地理: 6 生物: 7 化學: 8
我們可以觀察到歼跟，和HashMap的運行結果不同和媳，LinkedHashMap的迭代輸出的結果保持了插入順序。是什么樣的結構使得LinkedHashMap具有如此特性呢哈街？
LinkedHashMap是Hash表和鏈表的實現(xiàn)留瞳，并且依靠著雙向鏈表保證了迭代順序是插入的順序。
