資料結構

鏈結串列

• 以位址來連結數個元素
• 易於插入元素，檢索特定元素需花費 O(n) 時間，因為不知道切確位置必須要遍歷
• 最後指向 null 表示該點為鏈結串列的最後一個節點

鏈結串列常見的分兩種，一種是單向鏈結串列，一種是雙向鏈結串列。
兩者差在單向鏈結串列的屬性只會有指向下一個元素，雙向鏈結串列則是多一個屬性指向上一個元素。
大部分題目是單向鏈結串列居多。

以 C# 為例，常見的結構會長這樣

public class ListNode{
    public int val;
    public ListNode next;
    public ListNode last;//僅有雙向鏈結串列有
    public ListNode(int x){
        val = x;
    }
}

我們今天會主要專注在單向鏈結串列上去討論，雙向鏈結串列的題目相對稀少，大多是實際應用儲存時會用到，之後如果有機會我們再單獨抽一篇看雙向鏈結串列的題目。
可以比較 Leetcode 上 Linked List 和 Doubly Linked List的 Tag 題單，Doubly Linked List 明顯少得多(但也不代表不重要，LRU 和 LFU 也是重要的主題)。

下面提到的鏈結串列都默認是單向鏈結串列。

基本操作

鏈結串列的類別在題目裡多是用如上面的方式宣告出來的，基礎題目會考察關於鏈結串列的操作，在不是使用內建型別的情況下，該怎麼處理。
就最基本的 CRUD，增刪查改我們可以看一下鏈結串列的概念：

• 增 Create
  如果按照一般增的概念，就是建立一個實體，new ListNode(-1)，沒什麼特別的。
  有一個小技巧是題目一般會給 head 節點作為輸入鏈結串列的開頭，看別人寫題的時候，很多時候會額外創建一個 var dummy = new ListNode(-1)，然後把 dummy 的 next 指向 head，最後回傳只要回傳 dummy.next 就是原本的鏈結串列的頭了，這個小技巧稱做虛擬頭節點，在很多題目用了會帶來方便

• 改 Update

向鏈結串列中某個點插入資料
向鏈結串列中移除資料

無論是插入還是移除，鏈結串列是透過指標 next 來連結各個點的，所以基本上假設有一個鏈結串列的值如下：
1 -> 2 -> 4
假設我們要移除 2 這個點，那其實直接把 2 的 next 指向 4 就好了。
看語言特性，如果不會自動釋放記憶體的語言，修改指向需要手動去把 2 的記憶體釋放，避免記憶體占用，C# 這個部分就不用特別處理，直接改指向就算完成，讓語言的機制自己處理。
假設我們要在 2 後面插入一個 3，也是很簡單，就是建一個 3 的節點，記住 2 的 next 後，把 2 的 next 指向 3，再把 3 的 next 指向剛剛記住的 4 節點，這樣就完成了

• 查 Read
  上面說的改本身的時間複雜度如果在已經到要插入或是移除的點的時候，時間複雜度本身是 O(1)，那個操作也不影響其他點。但是要找到某個點，就要從頭開始遍歷，不斷透過 next 指針找往下個點，持續比對，所以查本身就是一個迴圈，直到滿足條件或到結尾為止不斷的往 next 找去，這個操作的時間複雜度是 O(n)

• 刪 Delete
  刪除指定節點的話就是查加上改，透過時間複雜度 O(n) 先找到節點，再透過修改指向來達到刪除的效果。
  陣列是無法刪除元素的，相對的，因為使用指向來觀連元素，鏈結串列是有刪除的操作，不管是插入或移除，都只影響鄰近點，不會造成整個元素串的位移，相較陣列在這方面使用起來較方便。陣列則是在查的動作本身有時間複雜度 O(1) 的優勢，就看需求決定使用的資料結構。

相關演算法題目形式

1. 雙指針
   是的，你沒看錯，和陣列一樣，雙指針也是鏈結串列中常用到的技巧。只是特性下，快慢指針的使用頻率一般會高於左右指針，因為左右指針在結構下，如果題目沒有給尾節點，必須要先做一次 O(n) 的遍歷來找到尾節點。

快慢指針
左右指針

雙指針的原理說明，這邊不細講，可以參考 Day 3 陣列裡的說明，實際如何在鏈結串列的結構裡運用，我們會在實際題目直接來看。

2. 鏈結串列的反轉
   反轉指的是給一個串列如 1->2->3->4->5，輸入 1 的頭節點，從輸入的節點開始反轉，要求返回串列為 5->4->3->2->1 的頭節點 5。
   鏈結串列的反轉通常有兩種實作方式；迴圈和遞迴，操作的原理是一樣的，因為鏈結串列單向遍歷的特性，反轉會被拿來當作考察是否對鏈結串列指標和位置能夠清晰操作的一個題目，出現頻率算高，部分題目也會用到反轉部分串列的概念，得確定兩個方式都能順利寫出來。

3.有環無環結構
假設數值代表唯一點 1-> 2 ->3 是一個無環的鏈結串列， 1 -> 2 -> 3 -> 1 表示一個有環的鏈結串列，所謂的環指的是鏈結串列如果透過 next 指標持續往下遍歷，最後會不會到 Null (結尾)，還是會一直在串列裡兜轉，會一直在串列裡的就稱做有環。
有一個著名的題目叫做龜兔賽跑，會帶到關於環結構的概念跟形成環結構時的相對位置。

今天的資料結構簡單的帶過大概到這裡，明天我們一起來看一下這些結構特性和相關題目該如何一一解題。