雖然筆者在研習深度學習時第一個接觸的程式語言為 Python，不過在練習的過程中總覺得對於寫程式的觀念不是很清楚，例如甚麼是 Node、array 和 list 的差別為何等等問題，特別是在 LeetCode 上寫題目時，發現許多之前沒有接觸過的觀念，因此決定進一步自修，於評價很好且免費的線上課程 CS61B，來學習資料結構及演算法，同時記錄上課重點，透過筆記作為複習使用，以及確認自己是否了解課程的內容。
此課程以 Java 教學，內容淺顯易懂，還有許多實作的練習機會，推薦學過基本程式語言的新手上課。筆者在上這堂課前已經學習過 Python 的基本語法，因此本文只會節錄筆者認為重點的部分。順便推薦之前在學習 Python 時參加的課程 ccClub，每年會有兩季開放線上及線下班，只要完成指定作業和期末專案，便可以拿回保證金，等同於免費教學Python的基本語法。
Data Types
在 Java，所有的變數都可以區分為兩種型態
- Primitive type
包含了 8 種 Java 預設的型態：boolean、int、byte、short、long、double、float、char。 - Reference type
除了 primitive type 都屬於 reference type。
舉例來說，當我們需要一個儲存整數的變數 age 時，需要進行三個步驟，如圖一所示：
int age = 16;
- 在等號左側，宣告（declare）該變數是一個屬於 primitive type 中的整數（int）型態，此時 Java 會準備可以存放 32 位元的空間留給這個變數，用來存放我們實際希望儲存的整數。
- 在等號右側，準備整數放入步驟一中 Java 為我們準備的空間，對程式來說任何資料最後都會以 0 和 1 來表示，因此整數對 Java 來說實際上是一連串 0 和 1 共 32 位元的組合。
- 等號（＝）將右側代表整數的 32 位元，複製到左側所準備的32位元的空間中，又稱 GRoE（Golden Rule of Equals）。
除了 int，其他 primitive type 像是布林值（boolean），則是僅用 1 個位元存放 1 或 0 分別來代表真值、假值，而 Java 預留字串 true 代表真值，false 代表假值，例如：
boolean flag = true;
代表的是 flag 這個變數為布林值，含 1 位元存放著 1。
當然我們不會只用到 primitive type 的資料，其中一個常用內建的資料結構「陣列（array）」，在 Java 以一對中括號 [] 來表示；然而對於 Java 來說，除了 primitive type 的資料其餘都屬於 reference type。reference type 的變數固定存放 64 位元的資料，這 64 個 0 和 1 的組合，並非直接代表該變數的所含的內容，而是代表這一個物件（object）所在的記憶體位置。
如圖二為例，實例（instantiate）一個陣列，並且回傳代表該陣列的 64 位元的記憶體之位置給變數 ages。也因此，ages 這個變數存放的 0 和 1 並不能代表該陣列的內容，而是一個可以找到被實例的陣列其地址，而這個 64 位元的地址又可以稱為指標（pointer）。
Linked List
有了指標的概念後，接著介紹一種常見的資料結構 linked list，這種資料結構會將每一個節點（Node）串聯起來，而其中一個可能的節點範例如下所示，存在一個存放代表該節點的整數變數 val，另一個則是串聯每一個節點的關鍵，存放另一個節點的節點變數 next。
如圖三所示，假設有一個被宣告成節點物件的變數 head 後面接著兩個節點，每個節點內的next都指向下一個節點，即可形成一個以 head 為首的linked list，而最後一個節點並沒有接到下一個節點，因此指向 null。
雖然說變數 head 只有指向第一個節點，不過第二個和第三個節點都存在的原因是因為對於這兩個節點，都存在另一個節點指向它們，分別是第一個節點和第二個節點。如果經圖四操作後，val=1的節點並沒有任何其他的節點指向它，就會被 garbage collector 認為這個物件（val=1節點記憶體的位址）並沒有人使用，該空間自動被 Java 釋出，也就是刪除該節點，如圖四。
節點及指標的概念除了運用在 linked list 這種資料結構，在後續會介紹的雙向 linked list、樹（Tree）也都會用到，不過當初在學習 Python 時，並未討論到這麼詳細的觀念，這也是推薦 CS61B 這門課的原因之一。
接下來會記錄一些跟 linked list 有關的題目，後續也會不定期更新在這篇文章底下。
LeetCode #206 Reverse Linked List(Easy)
題目敘述給定一個linked list，要求倒轉排列的順序，如圖五。
由上述可知，一個 linked list 會存在，是因為有一個變數 head 指向這一串節點的起始位置，題目要求回傳一個翻轉後的節點，因此
第一步，先建立一個欲回傳的節點變數 reverseHead 指向 null，代表翻轉後最後一個節點指向的位置；另一個節點變數 pointer 則負責跟著 head。
第二步，令 head 持續向下一個節點移動，pointer 負責將當下節點內的節點變數 next 指向 reverseHead。
第三步，將 reverseHead 指向 pointer，目的是為了能讓 reverseHead 永遠指向翻轉後的第一個節點，且讓 pointer 持續跟著 head 移動。
持續步驟二和步驟三直到 head 指向 null，代表已經歷過題目提供的所有節點，即可回傳翻轉後的節點 reverseHead。過程中可以注意到因為在進行每一個步驟時，每一個節點都會有另一個節點指向它，因此不會被 garbage collector 刪除。
