一、LinkedList
一、LinkedList概述
LinkedList是一個(gè)簡單的數(shù)據(jù)結(jié)構(gòu)，與ArrayList不同的是，他是基于鏈表實(shí)現(xiàn)的。
這樣一個(gè)簡單的操作：
LinkedListlist=newLinkedList();
list.add("語文: 1");
list.add("數(shù)學(xué): 2");
list.add("英語: 3");
----以雙向鏈表實(shí)現(xiàn)。鏈表無容量限制，但雙向鏈表本身使用了更多空間，也需要額外的鏈表指針操作。按下標(biāo)訪問元素—get(i)/set(i,e) 要悲劇的遍歷鏈表將指針移動(dòng)到位(如果i>數(shù)組大小的一半，會(huì)從末尾移起)。
插入、刪除元素時(shí)修改前后節(jié)點(diǎn)的指針即可，但還是要遍歷部分鏈表的指針才能移動(dòng)到下標(biāo)所指的位置，只有在鏈表兩頭的操作—add(), addFirst(),removeLast()或用iterator()上的remove()能省掉指針的移動(dòng)。
1.1、get和set函數(shù)
這兩個(gè)函數(shù)都調(diào)用了node函數(shù)，該函數(shù)會(huì)以O(shè)(n/2)的性能去獲取一個(gè)節(jié)點(diǎn)
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搜索。而不是一直從頭到尾的搜索。如此設(shè)計(jì)，將節(jié)點(diǎn)訪問的復(fù)雜度由O(n)變?yōu)镺(n/2)。
二、HashMap
2.1、初次見面
當(dāng)我們執(zhí)行以下操作時(shí)：
HashMapmap=newHashMap();
map.put("語文",1);
map.put("數(shù)學(xué)",2);
map.put("英語",3);
map.put("歷史",4);
map.put("政治",5);
map.put("地理",6);
map.put("生物",7);
map.put("化學(xué)",8);
for(Entryentry:map.entrySet()) {System.out.println(entry.getKey()+":"+entry.getValue());}
運(yùn)行結(jié)果時(shí)：政治: 5
生物: 7
歷史: 4
數(shù)學(xué): 2
化學(xué): 8
語文: 1
英語: 3
地理: 6
what！發(fā)生了什么，那就上個(gè)圖吧！
從圖中提取幾個(gè)關(guān)鍵的信息：基于Map接口實(shí)現(xiàn)、允許null鍵/值、非同步、不保證有序(比如插入的順序)、也不保證序不隨時(shí)間變化。
2.2、HashMap的put和get
hashmap初始化時(shí)會(huì)定義一個(gè)table。如果是普通的map的話，直接將將item放入到map的對(duì)應(yīng)列當(dāng)中。但是hashmap呢
三、LinkedHashMap
看下這個(gè)代碼
LinkedHashMaplmap=newLinkedHashMap();
lmap.put("語文",1);lmap.put("數(shù)學(xué)",2);lmap.put("英語",3);lmap.put("歷史",4);lmap.put("政治",5);lmap.put("地理",6);lmap.put("生物",7);lmap.put("化學(xué)",8);
for(Entryentry:lmap.entrySet()) {System.out.println(entry.getKey()+":"+entry.getValue());}
運(yùn)行結(jié)果：語文: 1 數(shù)學(xué): 2 英語: 3 歷史: 4 政治: 5 地理: 6 生物: 7 化學(xué): 8
我們可以觀察到，和HashMap的運(yùn)行結(jié)果不同，LinkedHashMap的迭代輸出的結(jié)果保持了插入順序。是什么樣的結(jié)構(gòu)使得LinkedHashMap具有如此特性呢？
LinkedHashMap是Hash表和鏈表的實(shí)現(xiàn)，并且依靠著雙向鏈表保證了迭代順序是插入的順序。
