靜態(tài)鏈表：數(shù)據(jù)全部存儲在數(shù)組中（和順序表一樣），但存儲位置是隨機的察郁，數(shù)據(jù)之間"一對一"的邏輯關(guān)系通過一個整形變量（稱為"游標"衍慎，和指針功能類似）維持。
例如皮钠，使用靜態(tài)鏈表存儲 {1,2,3} 的過程如下：
創(chuàng)建一個足夠大的數(shù)組稳捆，假設(shè)大小為 6，如圖1 所示：
接著麦轰，在將數(shù)據(jù)存放到數(shù)組中時乔夯，給各個數(shù)據(jù)元素配備一個整形變量，此變量用于指明各個元素的直接后繼元素所在數(shù)組中的位置下標款侵，如圖 2 所示：
通常末荐，靜態(tài)鏈表會將第一個數(shù)據(jù)元素放到數(shù)組下標為 1 的位置（a[1]）中。
圖 2 中新锈，從 a[1] 存儲的數(shù)據(jù)元素 1 開始甲脏，通過存儲的游標變量 3，就可以在 a[3] 中找到元素 1 的直接后繼元素 2妹笆；同樣块请，通過元素 a[3] 存儲的游標變量 5，可以在 a[5] 中找到元素 2 的直接后繼元素 3拳缠，這樣的循環(huán)過程直到某元素的游標變量為 0 截止（因為 a[0] 默認不存儲數(shù)據(jù)元素）墩新。
類似圖 2 這樣，通過 "數(shù)組+游標" 的方式存儲具有線性關(guān)系數(shù)據(jù)的存儲結(jié)構(gòu)就是靜態(tài)鏈表脊凰。
靜態(tài)鏈表中的節(jié)點
靜態(tài)鏈表存儲數(shù)據(jù)元素也需要自定義數(shù)據(jù)類型抖棘，至少需要包含以下2部分信息：
- 數(shù)據(jù)域：用于存儲數(shù)據(jù)元素的值
- 游標：其實就是數(shù)組的下表茂腥，表示直接后繼元素所在數(shù)組中的位置
備用鏈表
圖2顯示的靜態(tài)鏈表還不夠完整，靜態(tài)鏈表搜中切省，出了數(shù)據(jù)本身通過游標組成的立案表外最岗，還需要有一條連接各個空閑位置的鏈表，稱為備用鏈表
通常朝捆，備用鏈表的表頭位于數(shù)組下標為 0（a[0]） 的位置般渡，而數(shù)據(jù)鏈表的表頭位于數(shù)組下標為 1（a[1]）的位置。
靜態(tài)鏈表中設(shè)置備用鏈表的好處是芙盘，可以清楚地知道數(shù)組中是否有空閑位置驯用，以便數(shù)據(jù)鏈表添加新數(shù)據(jù)時使用。比如儒老，若靜態(tài)鏈表中數(shù)組下標為 0 的位置上存有數(shù)據(jù)蝴乔，則證明數(shù)組已滿。
靜態(tài)鏈表的實現(xiàn)
假設(shè)使用靜態(tài)鏈表（數(shù)組長度為 6）存儲 {1,2,3}驮樊，則需經(jīng)歷以下幾個階段薇正。
在數(shù)據(jù)鏈表未初始化之前，數(shù)組中所有位置都處于空閑狀態(tài)囚衔，因此都應(yīng)被鏈接在備用鏈表上挖腰，如圖 4 所示：
當向靜態(tài)鏈表中添加數(shù)據(jù)時，需提前從備用鏈表中摘除節(jié)點练湿，以供新數(shù)據(jù)使用猴仑。
備用鏈表摘除節(jié)點最簡單的方法是摘除 a[0] 的直接后繼節(jié)點；同樣肥哎，向備用鏈表中添加空閑節(jié)點也是添加作為 a[0] 新的直接后繼節(jié)點辽俗。因為 a[0] 是備用鏈表的第一個節(jié)點，我們知道它的位置贤姆，操作它的直接后繼節(jié)點相對容易榆苞，無需遍歷備用鏈表，耗費的時間復雜度為
O(1)霞捡。
因此坐漏，在圖 4 的基礎(chǔ)上，向靜態(tài)鏈表中添加元素 1 的過程如圖 5 所示：
在圖5的基礎(chǔ)上碧信，添加元素2的過程如圖6所示：
在圖 6 的基礎(chǔ)上赊琳，繼續(xù)添加元素 3 ，過程如圖 7 所示：
靜態(tài)鏈表與動態(tài)鏈表區(qū)別
類似于圖8 這樣的鏈表砰碴，我們稱他為“動態(tài)鏈表”躏筏。
類似于圖9 這樣的鏈表，我們稱他為“靜態(tài)鏈表”呈枉。
靜態(tài)鏈表和動態(tài)鏈表的共同點是趁尼，數(shù)據(jù)之間"一對一"的邏輯關(guān)系都是依靠指針（靜態(tài)鏈表中稱"游標"）來維持埃碱，僅此而已。
靜態(tài)鏈表
使用靜態(tài)鏈表存儲數(shù)據(jù)酥泞，需要預先申請足夠大的一整塊內(nèi)存空間砚殿，也就是說，靜態(tài)鏈表存儲數(shù)據(jù)元素的個數(shù)從其創(chuàng)建的那一刻就已經(jīng)確定芝囤，后期無法更改似炎。
靜態(tài)鏈表是在固定大小的存儲空間內(nèi)隨機存儲各個元素，這就造成了靜態(tài)鏈表中需要使用另一條鏈表（一般稱為“備用鏈表”）悯姊，來記錄空閑存儲空間的位置羡藐。
這意味著使用靜態(tài)鏈表除了操作數(shù)據(jù)鏈表，還需要操作備用鏈表悯许。
動態(tài)鏈表
動態(tài)鏈表不需要預先申請內(nèi)存空間仆嗦，也就是說動態(tài)鏈表存儲數(shù)據(jù)元素的個數(shù)是不限的，想存多少就存多少岸晦。
同時欧啤，使用動態(tài)鏈表整個過程是需要操控一條存儲數(shù)據(jù)的鏈表。當添加刪除元素的時启上，只需要申請malloc或釋放free空間即可（java中不需要，gc自動回收）店印，實現(xiàn)簡單冈在。
循環(huán)鏈表
無論是靜態(tài)鏈表還是動態(tài)鏈表，有時候在解決具體問題時按摘，需要我們對其結(jié)構(gòu)進行稍微地調(diào)整包券。比如，可以把鏈表兩頭連接炫贤，使其成為一個環(huán)狀鏈表溅固，通常稱為循環(huán)鏈表。
需要注意的是兰珍，雖然循環(huán)鏈表成環(huán)狀侍郭，但本質(zhì)上還是鏈表，因此在循環(huán)鏈表中掠河，依然能夠找到頭指針和首元節(jié)點等亮元。循環(huán)鏈表和普通鏈表相比，唯一的不同就是循環(huán)鏈表首尾相連唠摹，其他都完全一樣爆捞。
循環(huán)鏈表實現(xiàn)約瑟夫環(huán)
約瑟夫環(huán)問題，是一個經(jīng)典的循環(huán)鏈表問題勾拉，題意是：已知 n 個人（分別用編號 1煮甥，2盗温，3，…成肘，n 表示）圍坐在一張圓桌周圍卖局，從編號為 k 的人開始順時針報數(shù)，數(shù)到 m 的那個人出列艇劫；他的下一個人又從 1 開始吼驶，還是順時針開始報數(shù)，數(shù)到 m 的那個人又出列店煞；依次重復下去蟹演，直到圓桌上剩余一個人。
如圖 11 所示顷蟀，假設(shè)此時圓周周圍有 5 個人酒请，要求從編號為 3 的人開始順時針數(shù)數(shù)，數(shù)到 2 的那個人出列：
出列順序依次為：
- 編號為 3 的人開始數(shù) 1鸣个，然后 4 數(shù) 2羞反，所以 4 先出列；
- 4 出列后囤萤，從 5 開始數(shù) 1昼窗，1 數(shù) 2，所以 1 出列涛舍；
- 1 出列后澄惊，從 2 開始數(shù) 1，3 數(shù) 2富雅，所以 3 出列掸驱；
- 3 出列后，從 5 開始數(shù) 1没佑，2 數(shù) 2毕贼，所以 2 出列；
- 最后只剩下 5 自己蛤奢，所以 5 勝出鬼癣。
約瑟夫環(huán)問題有多種變形，比如順時針轉(zhuǎn)改為逆時針等远剩，雖然問題的細節(jié)有多種變數(shù)扣溺，但解決問題的中心思想是一樣的，即使用循環(huán)鏈表瓜晤。
//解決了約瑟夫環(huán)問題锥余，但未使用循環(huán)鏈表
private static void senario(int total, int cycle) {
List<Integer> all = new LinkedList<Integer>();
for(int i = 1;i <= total;i++){
all.add(i);
}
int i = 0;
for(int n = 1;n < total;n++){
i = (i + cycle -1) % all.size();
System.out.print(all.get(i)+(n==total-1?"\n":" "));
all.remove(i);
}
System.out.printf("幸存者為：%d號 (人數(shù)=%d, 周期=%d, (默認從第1個人開始、正向報數(shù)))\n",
all.get(0), total, cycle);
}
循環(huán)鏈表和動態(tài)鏈表唯一不同在于它的首尾連接痢掠，這也注定了在使用循環(huán)鏈表時驱犹，附帶最多的操作就是遍歷鏈表嘲恍。
在遍歷的過程中，尤其要注意循環(huán)鏈表雖然首尾相連雄驹，但并不表示該鏈表沒有第一個節(jié)點和最后一個結(jié)點佃牛。所以，不要隨意改變頭指針的指向医舆。
雙向鏈表
無論是動態(tài)鏈表還是靜態(tài)鏈表俘侠，表中各節(jié)點中都只包含一個指針（游標），且都統(tǒng)一指向直接后繼節(jié)點蔬将，通常稱這類鏈表為單向鏈表（或單鏈表）爷速。
如果算法中需要大量地找某指定結(jié)點的前趨結(jié)點，鏈表并不是效率最優(yōu)的存儲結(jié)構(gòu)霞怀，為了能夠高效率解決"從后往前"的問題惫东，可以使用雙向鏈表（簡稱雙鏈表）。
雙向毙石，指的是各節(jié)點之間的邏輯關(guān)系是雙向的廉沮，但通常頭指針只設(shè)置一個，除非實際情況需要徐矩。
從圖 11 中可以看到滞时，雙向鏈表中各節(jié)點包含以下 3 部分信息（如圖 12 所示）：
- 指針域：用于指向直接前驅(qū)節(jié)點
- 數(shù)據(jù)域：用于存儲數(shù)據(jù)元素
- 指針域：用于存儲直接后繼節(jié)點
雙向鏈表的基本操作
添加至表頭
假設(shè)新元素節(jié)點為 temp，表頭節(jié)點為 head滤灯，則需要做以下 2 步操作即可
- temp.next = head; head.prior=temp;
- 將頭指針重新指向temp
添加至表中
新節(jié)點先與直接后繼節(jié)點建立雙層邏輯關(guān)系
新節(jié)點的直接前驅(qū)節(jié)點與新節(jié)點建立雙層邏輯關(guān)系
添加至表尾
找到雙鏈表最后一個節(jié)點
讓新節(jié)點與最后一個節(jié)點進行雙層邏輯關(guān)系
雙鏈表刪除漂洋，查找，更改
與單鏈表幾乎無異力喷。
雙向循環(huán)鏈表
雙向鏈表也可以進行首尾連接，構(gòu)成雙向循環(huán)鏈表演训。如圖 16 所示：
當問題中涉及到需要 "循環(huán)往復" 地遍歷表中數(shù)據(jù)時弟孟，就需要使用雙向循環(huán)鏈表。例如样悟，前面章節(jié)我們對約瑟夫環(huán)問題進行了研究拂募，其實約瑟夫環(huán)問題有多種玩法，每次順時針報數(shù)后窟她，下一輪可以逆時針報數(shù)陈症，然后再順時針......一直到剩下最后一個人。解決這個問題就需要使用雙向循環(huán)鏈表結(jié)構(gòu)震糖。
