1–2 列表 List
列表的資料結構將數據排成一直線，由節點和指標組成。
每個數據都包含了：節點(node)和指標(pointer)，pointer指向下一個數據在記憶體中的位址。
而上圖中的數據37，是這個list當中的最後一個數據，他的pointer指向NULL。
列表是一個有方向性的數據結構。
但他在記憶體中，不需要依照數據的順序儲存，可以分散存在不同領域，只要透過pointer將這些list中的data連接起來即可。
也因為可以分散儲存，因此當我們要存取(access)這些數據時，必須跟著pointer按照順序 (sequential access) 存取各數據。例如，要access 37必需先access 12, 接著access 99才能access到37，這是列表的一個缺點。
列表的優點是：想要在列表中新增或刪除數據時，可以藉由pointer的轉向來達成。例如把12的pointer由指向99轉成指向新的數據45，而讓新的數據45的pointer指向99，就完成了在12和99之間新增一個數據45。
存取列表的時間是線性搜尋(3–1)會花費的時間：O(n)。而新增刪除數據花費的時間，如前面敘述，是個一次性的動作，因此花費時間為O(1)。
列表也有不同型態，例如：把最後一個數據指向第一個的circular list (環狀串列/ 循環串列)。或是每個node帶有兩個pointer分別只向前一個及後一個數據的bidrecttional list (雙向串列)。
1–3 陣列 Array
Array也是將數據排成一列，每個數據都會有一個index。
假設上圖中的array名稱為myArray，若想要access index 8 的數據，直接指定myArray[8]就可以存取，這種方式稱為隨機存取(random access)。跟List相比，Array也是將數據排成一列，但因為每個數據都會有一個index, 所以存取較為容易。
另一個與List不同的是Array沒有方向性:
Array在記憶體中的儲存是依序儲存。
缺點是，要新增或刪除數據時，必須要挪動其他數據的位置。例如，要在array中插入一個新數據時，得先在array最後新增一個空位，接者挪動其他數據將想要插入的位置空出來，才能將數據新增到想要的位置。刪除一個數據時，也必須移動被刪除數據之後的其他數據，把空下來的位置補齊。
跟List概念相反，Array的存取時間短，是O(1)常數時間。但新增刪除所需的時間就比較長，會是O(n)。
1–4 堆疊 Stack
同樣是將數排成一列，但顧名思義，堆疊就是把數據由下往上堆。
追加數據的動作，稱為push (推入)。反之，從stack 中拿出數據，稱為pop (彈出)。我們只能由最上面(也就是最新追加)的數據開始存取。
上述這種概念稱為“後進先出” Last In First Out。
堆疊看似非常不方便，因為要存取一個排在數列中間的數據時，得反覆pop直到該數據變成在stack的最上面才行。
不過，”隨時都只能存取最新數據”這件事，也有它的好處，例如：
一串字串：(AB (C (DE) F) (G ((H) IJ) K))
如果想知道每個右括弧相對應的左括弧是哪一個，我們可以藉由以下方式達成：
- 每當出現左括弧時，就將該位置push進stack裏。
- 每當出現右括弧時，就進行pop。
執行的流程會如下圖：我們可以從被彈出的數據得知，對應某一右括弧的左括弧是哪一個。
另外，堆疊也利於執行深度優先搜尋(4–3)，之後會說明。
