前言

線性表是指數(shù)據(jù)之間是一對(duì)一的關(guān)系，比如數(shù)組和鏈表都屬于這一范疇。數(shù)組和鏈表又代表了兩種存儲(chǔ)方式：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。部分知識(shí)已在Java集合源碼分析之基礎(chǔ)（一）：數(shù)組與鏈表中闡述，這里不再贅述，本文是對(duì)這些概念的補(bǔ)充，以及給出可參考的Java代碼實(shí)現(xiàn)。

順序存儲(chǔ)

順序存儲(chǔ)在大多數(shù)語(yǔ)言中定義為數(shù)組。它的特點(diǎn)就是地址連續(xù)，大小固定。下面，我們從增、刪、查三個(gè)方面說明它的操作性。首先，我們聲明了一個(gè)數(shù)組，并賦值了一些初始值，如下所示：

初始條件

• 增

1. 如果要在空閑位置插入數(shù)據(jù)，例如位置6，數(shù)據(jù)插入后無需任何額外操作，此時(shí)時(shí)間復(fù)雜度為O(1)，如下所示：

插入12

2. 如果要在中間某個(gè)位置插入數(shù)據(jù)，例如想把數(shù)據(jù)6插入到5和7之間，那么7及之后的數(shù)據(jù)都需要向后移動(dòng)一位，如下所示：

插入6

此時(shí)時(shí)間復(fù)雜度就不再是O(1)了。我們先用java代碼實(shí)現(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ù)會(huì)被刪除
    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(", ");   
    }
}

運(yùn)行后打印結(jié)果如下：

2, 5, 6, 7, 9, 11, 0,

最壞情況下，要把元素插入到位置0，需要執(zhí)行n-1次操作，所以時(shí)間復(fù)雜度為O(n)。

• 刪

刪除操作正好和插入相反，刪除一個(gè)數(shù)據(jù)后，后邊的數(shù)據(jù)都要向前移動(dòng)一位，所以它的最壞時(shí)間復(fù)雜度也是O(n)。

• 查

這里查分兩種情況，一種是獲取某一位置的數(shù)據(jù)，一種是查找一個(gè)值。

1. 獲取某個(gè)位置元素

對(duì)一個(gè)數(shù)組而言，數(shù)組的每個(gè)位置都可以通過位置0與偏移量計(jì)算出來，例如要獲取位置6的地址，只需要：

a[6] = a[0] + 6*{數(shù)據(jù)長(zhǎng)度}

所以它對(duì)應(yīng)的時(shí)間復(fù)雜度為O(1)。

2. 查找值

遺憾的是，數(shù)組僅記錄下標(biāo)，卻不記錄數(shù)據(jù)本身位置，而且數(shù)組的數(shù)據(jù)也不是有序的（可以插入時(shí)排序，但這不是必需），我們要查詢一個(gè)元素是否存在于數(shù)組中，需要對(duì)它進(jìn)行遍歷。示例代碼如下：

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;
        }
    }
}

它的最壞時(shí)間復(fù)雜度也是O(n)。

• 總結(jié)

數(shù)組是一個(gè)中規(guī)中矩的數(shù)據(jù)結(jié)構(gòu)，它在增刪查方面的時(shí)間復(fù)雜度都是O(n)，僅在通過Index索引數(shù)據(jù)時(shí)為O(1)。數(shù)組也有些高級(jí)的用法，比如動(dòng)態(tài)調(diào)整大小，這部分知識(shí)大家可以看我分析ArrayList的文章：Java集合源碼分析之List（二）：ArrayList

鏈?zhǔn)酱鎯?chǔ)

線性存儲(chǔ)要求一塊完整的內(nèi)存，在增刪數(shù)據(jù)時(shí)也表現(xiàn)一般，而鏈?zhǔn)酱鎯?chǔ)則正好解決了這些問題。我們依然從增、刪、查三個(gè)方面來解析。首先，我們先定義使用的Java模型：

class Node{
    Integer data;
    Node next;
}

其中data表示數(shù)據(jù)，next表示下一個(gè)數(shù)據(jù)的信息?，F(xiàn)在我們實(shí)現(xiàn)了一個(gè)鏈表，如下所示：

初始條件

• 增

要在一個(gè)鏈?zhǔn)酱鎯?chǔ)的結(jié)構(gòu)中插入數(shù)據(jù)，只需要修改一個(gè)節(jié)點(diǎn)的指針域即可。比如要把元素7插入到1和5之間，把5掛在7后面，再將1的指針域指向7的位置，示意如下：

插入7

可以看到這個(gè)操作對(duì)其他數(shù)據(jù)不會(huì)產(chǎn)生影響，所以它的時(shí)間復(fù)雜度為O(1)。

• 刪

刪除與插入類似，其時(shí)間復(fù)雜度也是O(1)，不過其操作順序和插入時(shí)相反。例如要把數(shù)據(jù)2從原表中刪除，需要先把11掛在5的后邊，再刪除2，示意如下：

刪除2

• 查

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能像數(shù)組一樣根據(jù)Index獲取數(shù)據(jù)，它的查詢也必須要遍歷，所以時(shí)間復(fù)雜度為O(n)。

• 總結(jié)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)增刪數(shù)據(jù)時(shí)時(shí)間復(fù)雜度是O(1)，查詢和數(shù)組一樣，都是O(n)，且不支持Index獲取。對(duì)比數(shù)組可以發(fā)現(xiàn)，數(shù)組適合靜態(tài)的、不變的數(shù)據(jù)，而鏈?zhǔn)竭m合動(dòng)態(tài)的、變化頻繁的數(shù)據(jù)。

單鏈表

單鏈表結(jié)構(gòu)與上述示例類似，每個(gè)數(shù)據(jù)只知道下一個(gè)位置的數(shù)據(jù)，卻不知道前一位置的數(shù)據(jù)。通常，定義一個(gè)單鏈表會(huì)設(shè)置一個(gè)頭結(jié)點(diǎn)head，它的數(shù)據(jù)域沒有意義，它的指針域指向鏈表的第一個(gè)數(shù)據(jù)。我們用java代碼實(shí)現(xiàn)一個(gè)簡(jiǎn)單的單鏈表。

1. 聲明一個(gè)空鏈表

Node head = new Node(null,null);

2. 添加一條數(shù)據(jù)

Node first = new Node(2,null);
Node second = new Node(5,null);
first.next = second;
head.next = first;

3. 插入一條數(shù)據(jù)

Node insert = new Node(7,null);
// 注意順序，①把first也鏈接在insert后，②再把insert鏈接在head后
// 因?yàn)橥ǔＧ闆r下我們只持有head實(shí)例的引用
insert.next = head.next;
head.next = insert;

4. 遍歷

Node print = head.next;
while (print!=null) {
    System.out.println(print.data);
    print = print.next;
}

5. 刪除一條數(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é)點(diǎn)并非是必需的，只是為了保證數(shù)據(jù)一致性所添加的輔助結(jié)點(diǎn)。

雙向鏈表

單鏈表的特點(diǎn)就是簡(jiǎn)單，但是它在遍歷時(shí)只能從前往后，這在某些情況下是不適用的。比如所有的數(shù)據(jù)都是有序的，按照從小到大排序，數(shù)據(jù)依次是{1,3,5,6,8,9,11}，現(xiàn)在我們已經(jīng)找到了數(shù)據(jù)8的位置，想要找到6，按照單鏈表的設(shè)計(jì)只能從前向后遍歷。這時(shí)候如果鏈表是雙向的，從數(shù)據(jù)8開始，只需要執(zhí)行一次操作就可以了。

雙向鏈表是在單鏈表的基礎(chǔ)上實(shí)現(xiàn)的，只需要在原有結(jié)構(gòu)上增加一個(gè)prev指針即可，如下所示：

class Node{
    Integer data;
    Node prev;
    Node next;
}

它的操作和單鏈表類似，只是在增刪時(shí)一定要注意順序，下面對(duì)這兩部分做重點(diǎn)說明。

1. 聲明一個(gè)空鏈表

為了數(shù)據(jù)的一致性，我們?cè)黾右粋€(gè)tail結(jié)點(diǎn)，作為尾幾點(diǎn)：

Node head = new Node(null);
Node tail = new Node(null);

2. 添加一條數(shù)據(jù)

Node first = new Node(2);
Node second = new Node(5);
// next和prev成對(duì)設(shè)置
second.next = tail;
tail.prev = second;
first.next = second;
second.prev = first;
head.next = first;
first.prev = head;

3. 刪除一條數(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;
}

只要注意成對(duì)地處理prev和next，就不會(huì)出錯(cuò)。

循環(huán)鏈表

無論是單鏈表還是雙向鏈表，從某一數(shù)據(jù)開始遍歷，都不能循環(huán)整個(gè)鏈表，除非從head或tail開始遍歷。循環(huán)鏈表則可以從任意結(jié)點(diǎn)開始，遍歷整個(gè)鏈表。它也是單鏈表的變種。

定義一個(gè)循環(huán)鏈表十分簡(jiǎn)單，只需要把單鏈表的最后一個(gè)元素的next指針，指向head即可。示意圖如下所示：

循環(huán)鏈表

它的操作和以上鏈表都類似，這里不再贅述。

總結(jié)

數(shù)組和鏈表是計(jì)算機(jī)可以存儲(chǔ)數(shù)據(jù)的最基本的結(jié)構(gòu)，其他的數(shù)據(jù)結(jié)構(gòu)雖然定義不同，但最終還是需要轉(zhuǎn)換成這兩種結(jié)構(gòu)才能進(jìn)行存儲(chǔ)，所以我們必須深刻理解。鏈表也不是僅有以上三種形態(tài)，但都是在單鏈表的基礎(chǔ)上進(jìn)行改造，以適應(yīng)不同的需求。

在JDK中包裝的ArrayList和LinkedList，就是數(shù)組和鏈表的應(yīng)用，這些類包裝了數(shù)組和鏈表的常用操作，還增加了動(dòng)態(tài)管理數(shù)組大小的技術(shù)，在性能上的表現(xiàn)十分優(yōu)秀，值得我們參考和學(xué)習(xí)。大家可以查看以下的文章學(xué)習(xí)相關(guān)知識(shí)：

Java集合源碼分析之List（二）：ArrayList

Java集合源碼分析之LinkedList

以上涉及代碼均已上傳至我的github。

我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~

編程之路，道阻且長(zhǎng)。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。