1.鏈表集合

什么鏈表集合？
鏈表集合分為單鏈集合和雙鏈集合，其中這里的“鏈”字表示引用的意思师痕，那單鏈也可以叫單引用集合会通？雙鏈也可以叫雙引用集合？這說明鏈表里面除了存值以外還存了引用嗎性雄？那這個(gè)引用是什么的引用呢没卸？
為啥要搞鏈表集合？
我們知道數(shù)組存值是有長(zhǎng)度限制的秒旋，但是我們的數(shù)組集合已經(jīng)解決了無(wú)限制長(zhǎng)度問題约计，且能存所有的對(duì)象了，為啥還要鏈表集合迁筛？
數(shù)組集合雖然能夠無(wú)限制存儲(chǔ)煤蚌，不停的擴(kuò)展存儲(chǔ)來(lái)實(shí)現(xiàn)無(wú)限制，但是它是不太方便在頭细卧、尾尉桩、中間進(jìn)行刪除、插入贪庙、修改等操作魄健，這就是數(shù)組集合的缺點(diǎn)了，修改不靈活插勤，雖然數(shù)組集合的添加沽瘦、修改的速度快一點(diǎn)，但是不靈活农尖，所以我們想做一種可以靈活修改析恋，想加長(zhǎng)就加長(zhǎng)、想縮短就縮短盛卡，能隨意的在頭助隧、尾、中間進(jìn)行插入、刪除并村、修改操作的一個(gè)集合巍实，也就是為了搞一個(gè)靈活的集合出來(lái)。
鏈表集合很靈活哩牍，但是修改的速度稍微比數(shù)組集合慢一丟丟棚潦。
鏈表的算法的實(shí)現(xiàn)：同樣離不開數(shù)組的，鏈表可以想象成鏈條膝昆，鏈條的優(yōu)點(diǎn)：想加長(zhǎng)就加長(zhǎng)丸边、想縮短就縮短，想更換其中某個(gè)壞的就隨意【學(xué)Java荚孵，到凱哥學(xué)堂kaige123.com】更換其中的壞的節(jié)點(diǎn)妹窖。
單鏈集合實(shí)現(xiàn)原理：

單鏈集合的實(shí)現(xiàn)是使用長(zhǎng)度為2的數(shù)組，分別存儲(chǔ)數(shù)據(jù)和引用收叶，其中這個(gè)引用是對(duì)下家數(shù)組的引用骄呼，單鏈集合只能從上家找下家，無(wú)法從下家找上家判没。
雙鏈集合原理：

雙鏈集合既可從上家找下家谒麦，也可從下家找到上家，在集合的頭部哆致、尾?imageMogr2/blur/1x0/quality/75|watermark/1/image/aHR0cDovL29zNzhmNGhueS5ia3QuY2xvdWRkbi5jb20vd2F0ZXJtYXJrLnBuZw==/dissolve/50/gravity/SouthEast/dx/10/dy/10|imageslim部绕德、中間插入、刪除摊阀、修改都很方便耻蛇。
雙鏈代碼實(shí)現(xiàn)：

由上可知，我們用長(zhǎng)度為3的數(shù)組來(lái)存儲(chǔ)對(duì)象胞此，鏈表這個(gè)東西是要有頭部和尾部的臣咖，定義兩個(gè)Object[]數(shù)組，分別為頭部和尾部節(jié)點(diǎn)漱牵，其中頭部應(yīng)該存第一次存入的對(duì)象夺蛇，且它應(yīng)該是保持不動(dòng)的，而尾部酣胀，則會(huì)隨著一個(gè)個(gè)不斷存入的對(duì)象而往下移動(dòng)刁赦。

第一次存入第一個(gè)對(duì)象的時(shí)候，head是null的闻镶，建一個(gè)數(shù)組甚脉，值為要存的obj，此時(shí)上家和下家的引用都不知道铆农，都是null牺氨，然后呢因?yàn)橹挥幸粋€(gè)值，所以head和tail都是指向這個(gè)數(shù)組的。
當(dāng)后續(xù)存入的值的時(shí)候猴凹，head就不是null了夷狰，此時(shí)要新建一個(gè)長(zhǎng)度為3的數(shù)組來(lái)存新的值，新建的數(shù)組為objs郊霎，它的值是obj沼头，此時(shí)可以知道它的上家是tail，而它的下家不知道則是null歹篓，此外瘫证，還知道tail的下家是新存入的objs揉阎，所以tail[2]=objs庄撮，把這兩層引用關(guān)系表達(dá)出來(lái)后呢，因?yàn)樾麓嫒肓藢?duì)象毙籽，所以尾部是要往下移動(dòng)的洞斯，所以tail=objs，新存入的對(duì)象就成了新的尾部了坑赡。這就完成了烙如。
鏈表的實(shí)現(xiàn)，最重要的就是搞清楚各個(gè)節(jié)點(diǎn)之間的引用關(guān)系毅否，當(dāng)一個(gè)對(duì)象失去了引用的時(shí)候亚铁，也就相當(dāng)于被刪除了，gc會(huì)回收它的螟加。
關(guān)于LinkedList和ArrayList的效率問題徘溢，可以使用飛行器來(lái)檢測(cè)的，ArrayList的修改速度是要比LinkedList快的捆探，但是LinkedList更加靈活然爆，至于內(nèi)存消耗和cpu消耗相差不大，linkedList的cpu消耗會(huì)稍微少點(diǎn)黍图。
向后添加的方法addLast(Object obj)
這個(gè)方法實(shí)現(xiàn)的話就可以直接調(diào)用add方法了曾雕，因?yàn)閍dd就是向后添加的啊：

添加到前面的方法addFirst(Object obj)
這個(gè)方法是在頭部的地方加入一個(gè)值助被，實(shí)現(xiàn)代碼如下：

向前添加的方法剖张，如果是第一次存入對(duì)象，則向前添加和add的性質(zhì)一樣揩环，直接調(diào)用add方法修械，如果不是第一次存入對(duì)象，則要新建一個(gè)數(shù)組objs存值检盼，并且放在頭部的前面肯污，此時(shí)知道的引用關(guān)系為：objs的下家是head，head的上家是objs，把兩層關(guān)系表達(dá)完后蹦渣，objs成為新的頭部哄芜，完成。
向前刪除：removeFirst()

向前刪除的時(shí)候柬唯，看是不是里面沒有值认臊，沒有值就拋異常，再看看是不是只有一個(gè)值锄奢，只有一個(gè)值的話我們很輕松的把頭部和尾部一起置為空失晴，就刪除了，如果不止一個(gè)值拘央，我們要?jiǎng)h除一個(gè)頭部的話涂屁，就要斷了所有的其他數(shù)組對(duì)它的引用，當(dāng)然這里只有一個(gè)下家數(shù)組對(duì)它有一個(gè)向上的引用灰伟，而且刪了頭部拆又，則頭部下家就成了新的頭部。所以讓頭部下家成為新的頭部栏账，然后再把新的頭部的向上引用斷開(置空)帖族，這樣就完成了。
向后刪除代碼實(shí)現(xiàn)：removeLast()

向后刪除的時(shí)候挡爵，我們先看是不是沒有值竖般，沒有值就拋異常，再看是不是只有一個(gè)值茶鹃，只有一個(gè)值的話涣雕，我們就把頭部和尾部一起置空，當(dāng)不止一個(gè)值的時(shí)候前计，要?jiǎng)h除尾部胞谭，我們知道只有尾部的上家對(duì)尾部有一個(gè)向下的引用，我們的目標(biāo)是斷掉這個(gè)引用男杈，可以先把尾部上家變成新的尾部丈屹，然后再把新的尾部的向下引用置空，這就完成了伶棒。
中間插入方法：add(int index,Object obj)

中間指定下標(biāo)插入一個(gè)對(duì)象的時(shí)候旺垒，我們要先定位，確定在哪個(gè)元素的前面插入一個(gè)新元素肤无，定位好后先蒋，要續(xù)上4條引用，然后就算完成宛渐，定位需要新建一個(gè)數(shù)組來(lái)存一個(gè)個(gè)取出來(lái)的值竞漾，采用while循環(huán)眯搭，因?yàn)椴淮_定次數(shù)，需要看條件index==0业岁，在一個(gè)一個(gè)找的時(shí)候鳞仙，如果出現(xiàn)取出來(lái)的objs==null說明，取值的時(shí)候笔时，把值取完了棍好，說明index太大了，那就要拋異常了允耿。
當(dāng)定位完了之后借笙，我們?nèi)〕鰜?lái)的值(存在objs中)，我們是要在objs前面插入一個(gè)對(duì)象较锡，那我們要再新建一個(gè)數(shù)組objs1存要新插入的對(duì)象业稼，它的數(shù)據(jù)對(duì)象obj，此時(shí)我們知道兩條引用關(guān)系：就是objs1的上家是objs的上家objs[0]念链，objs1的下家是objs,所以：Object[] objs1=new Object[]{objs[0],obj,objs};續(xù)完這兩條引用關(guān)系盼忌，再續(xù)另外兩條积糯，我們還知道掂墓，objs的上家的新下家是objs1了，并且objs的新上家也是objs1了看成，把這兩條引用續(xù)上君编，那就完成了。
按下標(biāo)刪除方法remove(int index,Object obj):

按下標(biāo)刪除川慌，像這種要進(jìn)行刪除的方法(包括向前刪除吃嘿、向后刪除)，最先考慮的是這個(gè)鏈表是不是空的梦重，是的話就拋異常兑燥，然后既然不是空的，就看下標(biāo)是不是刪頭部琴拧，如果是降瞳，就調(diào)用現(xiàn)存的向前刪除，如果不是刪頭部蚓胸，就要定位了挣饥，定位從頭部開始往下擼，所以把head交給申請(qǐng)的暫存取出來(lái)的元素的object數(shù)組沛膳，然后while循環(huán)扔枫，不知道具體的次數(shù)，只能靠條件index==0來(lái)進(jìn)行循環(huán)跳出锹安。在循環(huán)里面一直把下家取出來(lái)短荐，取出下家后倚舀，要看看是不是null，如果取著取著變成空了忍宋，就要拋異常了瞄桨，當(dāng)擼到index為0的時(shí)候，我們就成功定位到了我們要?jiǎng)h除的元素了讶踪，這是要看它是不是尾部芯侥，如果是尾部，調(diào)用現(xiàn)存的向后刪除乳讥，如果不是尾部柱查，我們則要先把要?jiǎng)h除的元素的上下家取出來(lái)，然后把上下家對(duì)這個(gè)將被刪除的引用斷開云石，要斷開的引用分別是上家對(duì)它的向下引用和下家對(duì)它的向上引用唉工，當(dāng)然這里用不著置空，直接把下家向上引用給上家汹忠，上家的向下引用給下家淋硝，就把這個(gè)元素越過去了，也就完成了宽菜。
hasNext()和next()方法谣膳，這兩個(gè)方法用來(lái)把鏈表的所有值打印出來(lái)：

hasNext方法和next方法是用來(lái)把整個(gè)鏈表打印出來(lái)的方法，next用來(lái)返回值铅乡，hasNext用來(lái)判斷取出來(lái)的對(duì)象數(shù)組是不是空继谚，不是空就是有值的，我們先看鏈表是不是空阵幸，如果是空花履，直接false，如果不是空挚赊，要看是不是取第一個(gè)诡壁，取第一個(gè)直接把頭部給過去，若不是取第一個(gè)荠割，則取下家妹卿，取出來(lái)的下家要防止它是空的，是空的就要false涨共，那剩下的情況就是true了纽帖。
ArrayList集合的優(yōu)點(diǎn)是添加速度很快，LinkedList集合的優(yōu)點(diǎn)是修改非常靈活举反，每個(gè)集合都有各自的優(yōu)點(diǎn)的懊直，再使用的時(shí)候可以組合起來(lái)使用。
鏈表的好處：由于它的修改非常方便火鼻、靈活室囊，而且盡然有刪頭部雕崩，刪尾部，頭部添加融撞，尾部添加這樣的方法盼铁，就使得它可以運(yùn)用到隊(duì)列中去，可以用來(lái)進(jìn)行排隊(duì)(隊(duì)列中的執(zhí)行順序是：先來(lái)先執(zhí)行尝偎，后來(lái)后執(zhí)行)饶火。
對(duì)于隊(duì)列模式下：隊(duì)列中如果有非常多的任務(wù)，要讓任務(wù)排隊(duì)不停的執(zhí)行致扯，我們可以使用linkedlist來(lái)處理肤寝，在任務(wù)隊(duì)列中的頭部的地方使用removeFirst()方法，不停的把執(zhí)行完了的任務(wù)刪除掉抖僵，在任務(wù)隊(duì)列的尾部使用addLast方法鲤看，不停的往任務(wù)隊(duì)列中添加新的任務(wù)，這樣我們就可以不停的把任務(wù)壓入到任務(wù)隊(duì)列中耍群，讓任務(wù)一個(gè)一個(gè)不停的去執(zhí)行义桂。

添加的任務(wù)從后面進(jìn)來(lái)，刪除的任務(wù)從前面出去蹈垢，這就是一個(gè)隊(duì)列的模型慷吊。鏈表集合的存儲(chǔ)方式非常擅長(zhǎng)制作隊(duì)列數(shù)據(jù)。
2.哈希集合
哈希集合的好處：我們要弄出哈希集合來(lái)是有原因的耘婚，它是專門做檢索的罢浇，它的檢索的速度非陈礁常快沐祷，這是它最大的優(yōu)點(diǎn)，檢索速度相當(dāng)快攒岛，非忱盗伲快能查找到數(shù)據(jù)。它的缺陷是灾锯，添加速度比較慢一些兢榨。
檢索就是給你一個(gè)值，看這個(gè)值是否存在這個(gè)集合里面顺饮。檢索的專長(zhǎng)就是檢索吵聪。
檢索速度展示：

相比之下，ArrayList的檢索速度就慢了很多了

這就是為啥說HashSet的專長(zhǎng)是檢索了兼雄。
原理圖：

哈希為什么會(huì)有這么快的檢索速度呢吟逝？原來(lái)是原因的，因?yàn)樗诎阎荡嫒霐?shù)組中時(shí)就做了手腳赦肋，當(dāng)然在檢索的時(shí)候也是有竅門的块攒。
比如励稳，要把”AAA”/”BBB”/”CCC”這三個(gè)值存入到一個(gè)長(zhǎng)度為18的數(shù)組中，它就會(huì)進(jìn)行一個(gè)處理了它把要存入的所有數(shù)據(jù)進(jìn)行一次區(qū)域劃分囱井，用對(duì)象的hashCode值去對(duì)數(shù)組長(zhǎng)度進(jìn)行取余運(yùn)算驹尼，取余運(yùn)算得出來(lái)的結(jié)果是多少就把值掛到相應(yīng)的下標(biāo)下面，這樣就能保證每個(gè)要存入的數(shù)據(jù)都是在數(shù)組長(zhǎng)度的范圍呢庞呕，比如新翎，這里數(shù)組長(zhǎng)度為18，我們hashCode()%18住练，這樣結(jié)果就是0-17料祠，剛好對(duì)應(yīng)數(shù)組的所有下標(biāo)，就相當(dāng)于把所有要存入的數(shù)據(jù)進(jìn)行了一次區(qū)域劃分澎羞，但是要存入的數(shù)據(jù)有很多個(gè)八枵馈？就有可能會(huì)導(dǎo)致不同的值算出來(lái)的hashCode()%18結(jié)果是一樣的妆绞，那就把不同的值掛到同一個(gè)數(shù)組下標(biāo)下面去了顺呕。其實(shí)不同的值掛到同一個(gè)下標(biāo)下面去也沒有關(guān)系，它會(huì)把后面【學(xué)Java括饶，到凱哥學(xué)堂kaige123.com】掛過來(lái)的值掛到前面的值的下家株茶，形成一個(gè)單鏈，其中第一個(gè)值是長(zhǎng)度為3的數(shù)組存儲(chǔ)图焰，它第0個(gè)放值启盛，第1個(gè)放下家引用，第2個(gè)放單鏈最后一個(gè)對(duì)象的引用技羔，而后面的值都是長(zhǎng)度為2的數(shù)組存儲(chǔ)僵闯，第0個(gè)放值，第1個(gè)放下家的引用藤滥。這樣就相當(dāng)于數(shù)組里面存儲(chǔ)的是單鏈集合了鳖粟。
那哈希檢索的時(shí)候也是有手段的，比如“BBB”需要進(jìn)行檢索拙绊，它會(huì)取出“BBB”的hashCode值向图，去%18，得到一個(gè)結(jié)果标沪，然后用這個(gè)結(jié)果直接到對(duì)應(yīng)的區(qū)域上去找了榄攀，相當(dāng)于進(jìn)行了精確定位，但是數(shù)組集合來(lái)檢索的話金句，他就要從頭到尾一個(gè)一個(gè)去詢問的了檩赢，這就是為啥數(shù)組集合檢索這么慢的原因了。
代碼實(shí)現(xiàn)：
我們首先要申請(qǐng)一個(gè)數(shù)組趴梢，來(lái)存值漠畜，實(shí)際上币他，真正的哈希集合的數(shù)組是可以自動(dòng)變長(zhǎng)的。