前言
線性表是指數(shù)據(jù)之間是一對一的關(guān)系，比如數(shù)組和鏈表都屬于這一范疇腐泻。數(shù)組和鏈表又代表了兩種存儲方式：順序存儲和鏈?zhǔn)酱鎯Α２糠种R已在Java集合源碼分析之基礎(chǔ)（一）：數(shù)組與鏈表中闡述，這里不再贅述圆雁，本文是對這些概念的補充由桌，以及給出可參考的Java代碼實現(xiàn)为黎。
順序存儲
順序存儲在大多數(shù)語言中定義為數(shù)組。它的特點就是地址連續(xù)行您，大小固定铭乾。下面，我們從增娃循、刪片橡、查三個方面說明它的操作性。首先淮野，我們聲明了一個數(shù)組捧书，并賦值了一些初始值吹泡，如下所示：
- 增
- 如果要在空閑位置插入數(shù)據(jù)，例如位置6经瓷，數(shù)據(jù)插入后無需任何額外操作爆哑，此時時間復(fù)雜度為O(1)，如下所示：
- 如果要在中間某個位置插入數(shù)據(jù)舆吮，例如想把數(shù)據(jù)6插入到5和7之間揭朝，那么7及之后的數(shù)據(jù)都需要向后移動一位，如下所示：
此時時間復(fù)雜度就不再是O(1)了色冀。我們先用java代碼實現(xiàn)它潭袱，示例如下：
public static void main(String[] args) {
int[] arr = {1,2,5,7,9,11,0,0};
int len = arr.length;
// 在arr[3]插入6，注意邊界锋恬，最后的數(shù)據(jù)會被刪除
for (int i = len-1; i >= 3; i--) {
arr[i] = arr[i-1];
}
arr[3] = 6;
for (int i = 0; i < len; i++) {
System.out.print(arr[i]);
System.out.print(", ");
}
}
運行后打印結(jié)果如下：
2, 5, 6, 7, 9, 11, 0,
最壞情況下屯换，要把元素插入到位置0，需要執(zhí)行n-1次操作与学，所以時間復(fù)雜度為O(n)彤悔。
- 刪
刪除操作正好和插入相反，刪除一個數(shù)據(jù)后索守，后邊的數(shù)據(jù)都要向前移動一位晕窑，所以它的最壞時間復(fù)雜度也是O(n)。
- 查
這里查分兩種情況卵佛，一種是獲取某一位置的數(shù)據(jù)杨赤，一種是查找一個值。
- 獲取某個位置元素
對一個數(shù)組而言截汪，數(shù)組的每個位置都可以通過位置0與偏移量計算出來望拖，例如要獲取位置6的地址，只需要：
a[6] = a[0] + 6*{數(shù)據(jù)長度}
所以它對應(yīng)的時間復(fù)雜度為O(1)挫鸽。
- 查找值
遺憾的是说敏，數(shù)組僅記錄下標(biāo)，卻不記錄數(shù)據(jù)本身位置丢郊，而且數(shù)組的數(shù)據(jù)也不是有序的（可以插入時排序盔沫，但這不是必需），我們要查詢一個元素是否存在于數(shù)組中枫匾，需要對它進行遍歷架诞。示例代碼如下：
public static void main(String[] args) {
int[] arr = {1,2,5,7,9,11,0,0};
int len = arr.length;
// 查找元素9的位置
for (int i = 0; i < len; i++) {
if(9 == arr[i]){
System.out.println("Index of num 9 is : " + i);
break;
}
}
}
它的最壞時間復(fù)雜度也是O(n)。
- 總結(jié)
數(shù)組是一個中規(guī)中矩的數(shù)據(jù)結(jié)構(gòu)干茉，它在增刪查方面的時間復(fù)雜度都是O(n)谴忧，僅在通過Index索引數(shù)據(jù)時為O(1)。數(shù)組也有些高級的用法，比如動態(tài)調(diào)整大小沾谓，這部分知識大家可以看我分析ArrayList的文章：Java集合源碼分析之List（二）：ArrayList
鏈?zhǔn)酱鎯?/h1>
線性存儲要求一塊完整的內(nèi)存委造，在增刪數(shù)據(jù)時也表現(xiàn)一般，而鏈?zhǔn)酱鎯t正好解決了這些問題均驶。我們依然從增昏兆、刪、查三個方面來解析妇穴。首先爬虱，我們先定義使用的Java模型：
class Node{
Integer data;
Node next;
}
其中data表示數(shù)據(jù)，next表示下一個數(shù)據(jù)的信息√谒現(xiàn)在我們實現(xiàn)了一個鏈表跑筝，如下所示：
- 增
要在一個鏈?zhǔn)酱鎯Φ慕Y(jié)構(gòu)中插入數(shù)據(jù)，只需要修改一個節(jié)點的指針域即可瞒滴。比如要把元素7插入到1和5之間曲梗，把5掛在7后面，再將1的指針域指向7的位置逛腿，示意如下：
可以看到這個操作對其他數(shù)據(jù)不會產(chǎn)生影響，所以它的時間復(fù)雜度為O(1)仅颇。
- 刪
刪除與插入類似单默，其時間復(fù)雜度也是O(1)，不過其操作順序和插入時相反忘瓦。例如要把數(shù)據(jù)2從原表中刪除搁廓，需要先把11掛在5的后邊，再刪除2耕皮，示意如下：
- 查
鏈?zhǔn)酱鎯Y(jié)構(gòu)不能像數(shù)組一樣根據(jù)Index獲取數(shù)據(jù)境蜕，它的查詢也必須要遍歷，所以時間復(fù)雜度為O(n)凌停。
- 總結(jié)
鏈?zhǔn)酱鎯Y(jié)構(gòu)增刪數(shù)據(jù)時時間復(fù)雜度是O(1)粱年，查詢和數(shù)組一樣，都是O(n)罚拟，且不支持Index獲取台诗。對比數(shù)組可以發(fā)現(xiàn)，數(shù)組適合靜態(tài)的赐俗、不變的數(shù)據(jù)拉队，而鏈?zhǔn)竭m合動態(tài)的、變化頻繁的數(shù)據(jù)阻逮。
單鏈表
單鏈表結(jié)構(gòu)與上述示例類似粱快，每個數(shù)據(jù)只知道下一個位置的數(shù)據(jù)，卻不知道前一位置的數(shù)據(jù)。通常事哭，定義一個單鏈表會設(shè)置一個頭結(jié)點head漫雷，它的數(shù)據(jù)域沒有意義，它的指針域指向鏈表的第一個數(shù)據(jù)慷蠕。我們用java代碼實現(xiàn)一個簡單的單鏈表珊拼。
- 聲明一個空鏈表
Node head = new Node(null,null);
- 添加一條數(shù)據(jù)
Node first = new Node(2,null);
Node second = new Node(5,null);
first.next = second;
head.next = first;
- 插入一條數(shù)據(jù)
Node insert = new Node(7,null);
// 注意順序，①把first也鏈接在insert后流炕，②再把insert鏈接在head后
// 因為通常情況下我們只持有head實例的引用
insert.next = head.next;
head.next = insert;
- 遍歷
Node print = head.next;
while (print!=null) {
System.out.println(print.data);
print = print.next;
}
- 刪除一條數(shù)據(jù)
// 刪除數(shù)據(jù)2
Node delete = head.next;
Node prev = delete;
while(delete!=null){
if(delete.data == 2){
// 也要注意順序澎现，先把后邊的數(shù)據(jù)，掛載在前一數(shù)據(jù)后邊
prev.next = delete.next;
// 再刪除數(shù)據(jù)2
delete.next = null;
break;
}
// 記錄前一數(shù)據(jù)
prev = delete;
delete = delete.next;
}
頭結(jié)點并非是必需的每辟，只是為了保證數(shù)據(jù)一致性所添加的輔助結(jié)點剑辫。
雙向鏈表
單鏈表的特點就是簡單，但是它在遍歷時只能從前往后渠欺，這在某些情況下是不適用的妹蔽。比如所有的數(shù)據(jù)都是有序的，按照從小到大排序挠将，數(shù)據(jù)依次是{1,3,5,6,8,9,11}胳岂，現(xiàn)在我們已經(jīng)找到了數(shù)據(jù)8的位置，想要找到6舔稀，按照單鏈表的設(shè)計只能從前向后遍歷乳丰。這時候如果鏈表是雙向的，從數(shù)據(jù)8開始内贮，只需要執(zhí)行一次操作就可以了产园。
雙向鏈表是在單鏈表的基礎(chǔ)上實現(xiàn)的，只需要在原有結(jié)構(gòu)上增加一個prev指針即可夜郁，如下所示：
class Node{
Integer data;
Node prev;
Node next;
}
它的操作和單鏈表類似什燕，只是在增刪時一定要注意順序，下面對這兩部分做重點說明竞端。
- 聲明一個空鏈表
為了數(shù)據(jù)的一致性屎即，我們增加一個tail結(jié)點，作為尾幾點：
Node head = new Node(null);
Node tail = new Node(null);
- 添加一條數(shù)據(jù)
Node first = new Node(2);
Node second = new Node(5);
// next和prev成對設(shè)置
second.next = tail;
tail.prev = second;
first.next = second;
second.prev = first;
head.next = first;
first.prev = head;
- 刪除一條數(shù)據(jù)
// 刪除數(shù)據(jù)2
Node delete = head.next;
Node prev = delete;
while(delete!=null){
if(delete.data == 2){
// 要注意順序事富，先把后邊的數(shù)據(jù)剑勾，掛載在前一數(shù)據(jù)后邊
prev.next = delete.next;
delete.next.prev = prev;
// 再刪除數(shù)據(jù)2
delete.next = null;
delete.prev = null;
break;
}
// 記錄前一數(shù)據(jù)
prev = delete;
delete = delete.next;
}
只要注意成對地處理prev和next，就不會出錯赵颅。
循環(huán)鏈表
無論是單鏈表還是雙向鏈表虽另，從某一數(shù)據(jù)開始遍歷，都不能循環(huán)整個鏈表饺谬，除非從head或tail開始遍歷捂刺。循環(huán)鏈表則可以從任意結(jié)點開始谣拣，遍歷整個鏈表极祸。它也是單鏈表的變種郭赐。
定義一個循環(huán)鏈表十分簡單袭灯，只需要把單鏈表的最后一個元素的next指針赏殃，指向head即可。示意圖如下所示：
它的操作和以上鏈表都類似伴榔，這里不再贅述联喘。
總結(jié)
數(shù)組和鏈表是計算機可以存儲數(shù)據(jù)的最基本的結(jié)構(gòu)血柳，其他的數(shù)據(jù)結(jié)構(gòu)雖然定義不同恰画，但最終還是需要轉(zhuǎn)換成這兩種結(jié)構(gòu)才能進行存儲宾茂，所以我們必須深刻理解。鏈表也不是僅有以上三種形態(tài)拴还，但都是在單鏈表的基礎(chǔ)上進行改造跨晴，以適應(yīng)不同的需求。
在JDK中包裝的ArrayList和LinkedList片林，就是數(shù)組和鏈表的應(yīng)用端盆，這些類包裝了數(shù)組和鏈表的常用操作，還增加了動態(tài)管理數(shù)組大小的技術(shù)费封，在性能上的表現(xiàn)十分優(yōu)秀焕妙，值得我們參考和學(xué)習(xí)。大家可以查看以下的文章學(xué)習(xí)相關(guān)知識：
以上涉及代碼均已上傳至我的github弓摘。
我是飛機醬焚鹊，如果您喜歡我的文章，可以關(guān)注我~
編程之路衣盾，道阻且長寺旺。唯爷抓，路漫漫其修遠兮势决，吾將上下而求索。
