這篇文章我們來說說Java里一個(gè)很重要的數(shù)據(jù)結(jié)構(gòu)——線性表捌臊，還是這張圖豁鲤，線性表對應(yīng)著下圖里的List。
紅框里的內(nèi)容就是線性表的大家族了宙项，其中黃色部分是要重點(diǎn)了解的乏苦，線性表里的元素是按線性排列的（這里的線性指邏輯上的） 線性表分為兩大類，分別是順序表和鏈表：
一尤筐、順序表
順序表中的數(shù)據(jù)元素存儲(chǔ)是連續(xù)的汇荐，內(nèi)存劃分的區(qū)域也是連續(xù)的。存儲(chǔ)結(jié)構(gòu)如下圖：
我們的ArrayList底層是數(shù)組實(shí)現(xiàn)的盆繁，底層元素在內(nèi)存中是按順序排列的掀淘，ArrayList是Java中順序表的體現(xiàn)。
二油昂、鏈表
鏈表在物理存儲(chǔ)上通常是非連續(xù)革娄、非順序的方式存儲(chǔ)的，數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用來實(shí)現(xiàn)的冕碟。
1拦惋、單向鏈表
很簡單，內(nèi)存中的對象是隨機(jī)分布的安寺，對象不但存儲(chǔ)了張三厕妖、李四等數(shù)據(jù)，還持有一個(gè)next引用挑庶，指向下一個(gè)對象言秸，來確定一組對象的邏輯順序软能。
2、循環(huán)鏈表
也很簡單举畸，和單向鏈表一樣查排，只不過最后一個(gè)對象的next又指向了第一個(gè)對象。
3抄沮、雙向鏈表
不但持有next引用跋核，指向下一個(gè)對象，還持有一個(gè)prev引用合是，指向上一個(gè)對象了罪。
記住雙向鏈表這個(gè)圖，很重要聪全，下一篇文章我們要講的LinkedList就是以雙向鏈表的方式實(shí)現(xiàn)的。
三辅辩、棧和隊(duì)列
棧和隊(duì)列是兩種比較特殊的線性表难礼。
1、棧
棧是一種操作受限制的線性表玫锋。其限制是僅允許在線性表的尾部進(jìn)行添加和刪除操作蛾茉，這一端被稱為棧頂，另一端稱為棧底撩鹿。向一個(gè)棧添加新元素叫壓棧谦炬，刪除元素又稱為出棧。
如上圖节沦，把趙六放入到棧中叫壓棧键思，不放入趙六，直接取出（刪除）王五的過程叫出棧甫贯，只能從棧頂放入和刪除元素吼鳞。本文第一張圖里的Stack就是棧在Java中的實(shí)現(xiàn)。舉個(gè)例子叫搁，最后洗好的盤子都是疊放在最上面的赔桌，但每次用的時(shí)候都是從最上面拿，最先洗好的盤子反而不容易用到渴逻。
2疾党、隊(duì)列
隊(duì)列也是一種操作受限制的線性表。只能從頭部刪除(取出)元素惨奕，從隊(duì)尾添加元素雪位，進(jìn)行刪除操作的端稱為隊(duì)頭。
看上面的圖墓贿，只能從隊(duì)尾添加元素茧泪，隊(duì)頭取出（刪除）元素蜓氨。本文第一張圖里的Queue就是隊(duì)列的體現(xiàn)，Queue是基于鏈表來體現(xiàn)的队伟。注意穴吹，Queue是一個(gè)接口，直接寫如下代碼是會(huì)報(bào)錯(cuò)的
Queuequeue=newQueue();//會(huì)報(bào)錯(cuò)嗜侮，Queue是接口港令，不允許實(shí)例化
正確的用法是
Queuequeue=newLinkedList();//正確的用法，基于鏈表來實(shí)現(xiàn)
隊(duì)列的鏈表實(shí)現(xiàn)是通過子類LinkedList來實(shí)現(xiàn)的锈颗，Queue接口收窄了LinkedList的訪問權(quán)限顷霹，只提供從隊(duì)尾，隊(duì)頭等的操作击吱。
為了加深大家的印象淋淀，我舉一個(gè)例子，惡心了一點(diǎn)覆醇，但保證大家能記住朵纷，大家在喝啤酒的過程中，正常去廁所小解的永脓，這個(gè)過程叫做隊(duì)例袍辞。喝多了吐出來的過程，叫做棧常摧。
以上就是Java線性表的介紹搅吁，面試中會(huì)經(jīng)常被問起，后續(xù)文章會(huì)把重點(diǎn)都說一下落午，希望對大家能有所幫助谎懦。
轉(zhuǎn)載出自：https://zhuanlan.zhihu.com/p/28346365
