在瞭解完 "什麼是數據結構" 之後，讓我們一起來探索下數據結構中常見的一種— 鏈表 。 鏈表 鏈表是數據結構之一， 其中的數據呈線性排列。在鏈表中，數據的添加和刪除都較為方便，就是訪問比較耗費時間。 如上圖所示就是鏈表的概念圖，Blue、Yellow、Red 這 3 個字元串作為數據被存儲於鏈表中， ...
在瞭解完什麼是數據結構之後，讓我們一起來探索下數據結構中常見的一種—鏈表。
鏈表
鏈表是數據結構之一，其中的數據呈線性排列。在鏈表中，數據的添加和刪除都較為方便，就是訪問比較耗費時間。
如上圖所示就是鏈表的概念圖，Blue、Yellow、Red 這 3 個字元串作為數據被存儲於鏈表中，也就是數據域，每個數據都有 1 個指針，即指針域，它指向下一個數據的記憶體地址，其中 Red 是最後 1 個數據，Red 的指針不指向任何位置，也就是為 NULL，指向 NULL 的指針通常被稱為空指針。
在鏈表中，數據一般都是分散存儲於記憶體中的，無須存儲在連續空間內。
因為數據都是分散存儲的，所以如果想要訪問數據，只能從第 1 個數據開始，順著指針的指向一一往下訪問（這便是順序訪問）。比如，想要找到 Red 這一數據，就得從 Blue 開始訪問，這之後，還要經過 Yellow，我們才能找到 Red。
如果想要添加數據，只需要改變添加位置前後的指針指向就可以，非常簡單。比如，在 Blue 和 Yellow 之間添加 Green。
首先將 Blue 的指針指向的位置變成 Green，然後再把 Green 的指針指向 Yellow，數據的添加就大功告成了。
數據的刪除也一樣，只要改變指針的指向就可以，比如刪除 Yellow。
這時，只需要把 Green 指針指向的位置從 Yellow 變成 Red，刪除就完成了。雖然 Yellow 本身還存儲在記憶體中，但是不管從哪裡都無法訪問這個數據，所以也就沒有特意去刪除它的必要了。今後需要用到 Yellow 所在的存儲空間時，只要用新數據覆蓋掉就可以了。
那麼對鏈表的操作所需的運行時間到底是多少呢？在這裡，我們把鏈表中的數據量記成 n。訪問數據時，我們需要從鏈表頭部開始查找（線性查找），如果目標數據在鏈表最後的話，需要的時間就是 O（n）。
另外，添加數據只需要更改兩個指針的指向，所以耗費的時間與 n 無關。如果已經到達了添加數據的位置，那麼添加操作只需花費 O（1）的時間，刪除數據同樣也只需 O（1）的時間。
鏈表的實現
在對鏈表有了大概的認識以後，我們用 Java 去實現屬於自己的鏈表：
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
class MyLinkedList {
int size;
/**
* 哨兵節點作為偽頭
*/
ListNode head;
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
/**
* 獲取鏈表第 index 個節點的值。如果索引是無效的，返回-1
*
* @param index
* @return
*/
public int get(int index) {
// 若索引無效
if (index < 0 || index >= size) {
return -1;
}
ListNode curr = head;
// 從偽頭節點開始，向前走 index+1 步
for (int i = 0; i < index + 1; ++i) {
curr = curr.next;
}
return curr.val;
}
/**
* 在頭部插入節點
*
* @param val
*/
public void addAtHead(int val) {
addAtIndex(0, val);
}
/**
* 在尾部插入節點
*
* @param val
*/
public void addAtTail(int val) {
addAtIndex(size, val);
}
/**
* 在鏈表中的第 index 個節點前添加值為 val 的一個節點。如果 index 等於鏈表的長度時，節點將被添加到鏈表的末尾。如果 index 大於鏈表長度，節點將無法插入
*
* @param index
* @param val
*/
public void addAtIndex(int index, int val) {
// 如果index大於長度，則不會插入該節點。
if (index > size) {
return;
}
// 如果 index 為負，則該節點將插入列表的開頭。
if (index < 0) {
index = 0;
}
++size;
// 查找要添加的節點的前驅節點
ListNode pred = head;
for (int i = 0; i < index; ++i) {
pred = pred.next;
}
// 要添加的節點
ListNode toAdd = new ListNode(val);
// 通過改變 next 來插入節點
toAdd.next = pred.next;
pred.next = toAdd;
}
/**
* 如果 index 是有效的，刪除鏈表中的第 index 個節點
*
* @param index
*/
public void deleteAtIndex(int index) {
// 如果 index 無效，則不執行任何操作
if (index < 0 || index >= size) {
return;
}
size--;
// 找到要刪除節點的前驅節點
ListNode pred = head;
for (int i = 0; i < index; ++i) {
pred = pred.next;
}
// 通過改變 next 來刪除節點
pred.next = pred.next.next;
}
}到這裡，我相信大家應該對鏈表有了進一步的理解，大家可以用不同的語言去設計實現下。
鏈表擴展
以上講述的鏈表是最基本的一種鏈表，除此之外，還存在幾種擴展方便的鏈表。
雖然上文中提到的鏈表在尾部沒有指針，但我們也可以在鏈表尾部使用指針，並且讓它指向鏈表頭部的數據，將鏈表變成環形，這便是迴圈鏈表，也叫環形鏈表。迴圈鏈表沒有頭和尾的概念，想要保存數量固定的最新數據時通常會使用這種鏈表。
另外，以上提到的鏈表裡的每個數據都只有一個指針，但我們可以把指針設定為兩個，並且讓它們分別指向前後數據，這就是雙向鏈表。使用這種鏈表，不僅可以從前往後，還可以從後往前遍曆數據，十分方便。
但是，雙向鏈表存在兩個缺點：一是指針數的增加會導致存儲空間需求增加；二是添加和刪除數據時需要改變更多指針的指向。
總結
看完之後，相信大家都對鏈表和鏈表的基本操作有了一定的瞭解，還對迴圈鏈表和雙向鏈表有了初步的認識，大家可以使用自己喜歡的語言去設計實現下單向鏈表，有能力的話可以把迴圈鏈表和雙向鏈表也實現下。
說完鏈表，當然不能忘記經常和鏈表同時出現在面試官口中的—數組，將在接下來的文章對其進行展開介紹。
參考
《我的第一本演算法書》
