# Linked Lists Notes
[Linked lists](http://www.cs.cmu.edu/~iliano/courses/18S-CMU-CS122/handouts/10-linkedlist.pdf)
* 15-122: Principles of Imperative Computation (Spring 2018)
Frank Pfenning, Rob Simmons, André Platzer, Iliano Cervesato
## Abstract
In this lecture we discuss the use of linked lists to implement the stack and
queue interfaces that were introduced in the last lecture. The linked list
implementation of stacks and queues allows us to handle work lists of any
length.
This fits as follows with respect to our learning goals:
* Computational Thinking: We discover that arrays contain implicit information, namely the indices of elements, which an be made explicit as
the addresses of the nodes of a linked list. We also encounter the notion of trade-off, as arrays and linked lists have different advantages
and drawbacks and yet achieve similar purposes.
* Algorithms and Data Structures: We explore linked lists, a data structure
used pervasively in Computer Science, and examine some basic algorithms about them.
* Programming: We see that programming algorithms for linked lists can
be tricky, which exposes once more the power of stating and checking
invariant. We use linked lists to implement stacks and queues.
## Introduction
### 1. Linked Lists
在數據結構的實現中，鍊錶是陣列的常見替代方案。鏈接列表中的每個項目都包含某種類型的數據元素和指向列表中下一個項目的指針。再鍊錶中可以很容易地插入和刪除元素，而對於陣列這樣屬於非自然操作，因為陣列有固定大小。另一方面，訪問列表中間的元素通常是 `O（n）`，其中 `n` 是列表的長度。
鍊錶中的一項由包含數據元素的結構和指向另一個鍊錶的指針組成。在 `C0` 中，我們必須定義 (commit) 存儲在鍊錶中的元素類型。我們將這個數據稱為具有 `elem` 類型，並期望在其他地方有一個類型定義告訴 `C0` 應該是什麼 `elem`。牢記這一點可確保沒有任何代碼實際上取決於所選擇的類型。這些考慮因素引起以下定義：
```cpp=
struct list_node {
elem data;
struct list_node* next;
};
typedef struct list_node list;
```
此定義是遞歸類型的示例。此類型的結構包含指向相同類型的另一個結構的指針，依此類推。我們通常使用類型 `t*` 的特殊元素（即 `NULL`）來表示我們已經到達列表的末尾。 有時（就像我們在堆棧和隊列中使用鍊錶一樣），我們可以避免顯式使用 `NULL` 並獲得更優雅的代碼。類型定義在那裡創建類型名稱 `list`，它代表 **`struct`** `list_node`，因此指向列表節點的指針將是 `list*`。我們還可以按照其他順序編寫這兩個語句，以更好地利用類型定義：
```cpp=
typedef struct list_node list;
struct list_node {
elem data;
list* next;
};
```
對遞歸類型有一些限制。宣告像是
```cpp=
struct infinite {
int x;
struct infinite next;
}
```
將被 `C0` 編譯器拒絕，因為它將需要無限量的空間。一般規則是，結構可以是遞歸的，但遞歸必須在其值為地址的指針或陣列類型下進行。這允許對 `struct` 類型的值進行有限表示。
我們不會在列表中介紹任何常規操作； 我們來看當我們需要時它們怎麼被使用。我們在這裡使用鍊錶是一種具體的類型，意味著我們不會在它們周圍構造接口和抽象層。當我們使用它們時，我們會了解並利用它們的精確內部結構。這與駐列 (queue) 或堆棧 (stack) 之類的抽像類型相反，前兩者執行是藏在介面後，僅會導出特定操作。鍊錶限制了客戶端可以執行的操作，但是它允許庫的作者改進其執行而不用擔心破壞客戶端程式碼。具體類型轉型只要一次就好。
### 2. List segments
一系列從開始到結束的節點。
這是 “inclusive-lower，exclusive-upper” 界限的熟悉結構：我們要討論一系列節點中的數據，而忽略最後一個節點中的數據。這意味著，對於任何非 `NULL` 列表節點指針 `l`，從 `l` 到 `l` 的段都是空的（不包含數據）。考慮以下結構：
根據我們對段的定義，從 `a1` 到 `a4` 的段中的數據是序列 `3`、`7`、`3`，從 `a2` 到 `a3` 的段中的數據包含序列 `7`，從 `a1` 到 `a1` 的段中的數據是空序列。
請注意，如果我們比較指針 `a1` 和 `a3`，`C0` 會告訴我們它們不相等-即使它們包含相同的數據，它們在內存中的位置也不同。
給定一個 `inclusive` 的起點和一個 `exclusive` 的終點，我們如何檢查是否有一個從起點到終點的路段？簡單的想法是從起點開始一直跟踪下一個指針，直到到達終點。如果我們到達 `NULL` 而不是 `end`，那麼我們知道我們錯過了期望的端點，因此我們沒有片段。（我們還必須確保如果 `start` 或 `end` 為 `NULL` 時我們沒有片段，這是我們上面對片段的定義所不允許的。）我們可以通過各種排列方式實現此簡單思想：
#### Recursively:
```cpp=
bool is_segment(list* start, list* end) {
if (start == NULL) return false;
if (start == end) return true;
return is_segment(start->next, end);
}
```
#### Using a while loop:
```cpp=
bool is_segment(list* start, list* end) {
list* l = start;
while (l != NULL) {
if (l == end) return true;
l = l->next;
}
return false;
}
```
#### Using a for loop:
```cpp=
bool is_segment(list* start, list* end) {
for (list* p = start; p != NULL; p = p->next) {
if (p == end) return true;
}
return false;
}
```
然而，`is_segment` 內的每一個執行都有相同的問題：如果給出了循環鍊錶結構，則 `is_segment` 可能不會終止。
可以有意或無意地創建這樣的結構。我們可以在 `Coin` 中創建循環鏈接列表的方法如下：
```cpp=
--> list* start = alloc(list);
--> start->data = 3;
--> start->next = alloc(list);
--> start->next->data = 7;
--> start->next->next = alloc(list);
--> start->next->next->data = 3;
--> start->next->next->next = alloc(list);
--> start->next->next->next->data = 12;
--> start->next->next->next->next = start->next;
--> list* end = alloc(list);
--> end->data = 18;
--> end->next = NULL;
--> is_segment(start, end);
```
這就是它的樣子：
只要有可能，我們的規範函數應該返回 `true` 或 `false`，而不是終止或引發中斷。我們確實將規範函數始終保持安全性視為絕對必要的–它們絕不能除以零，訪問邊界之外的數組或取消引用空指針。
### 3. Checking for Circularity
為了確保 `is_segment` 函數正確處理循環循環的情況，讓我們編寫一個函數來檢測列表段是否是循環的。我們可以在調用 `is_segment` 之前先調用此函數，然後確信 `is_segment` 將始終終止。
我們的循環檢測功能使用兩個指針，一個快和一個慢。我們將它們命名為 `h` 表示野兔，`t` 表示烏龜。慢指針 `t` 單步遍歷列表。另一方面，快的 `h`，每一步都會快 `t` 兩個元素。如果更快的 `h` 在 `t` 開始之前到達慢的 `t`，那麼它一定已經循環了。讓我們在列表上嘗試一下。 我們在每次迭代中顯示 `t` 和 `h` 的狀態。
程式碼:
```cpp=
bool is_acyclic(list* start) {
if (start == NULL) return true;
list* h = start->next; // hare
list* t = start; // tortoise
while (h != t) {
if (h == NULL || h->next == NULL) return true;
h = h->next->next;
//@assert t != NULL; // faster hare hits NULL quicker
t = t->next;
}
//@assert h == t;
return false;
}
```
關於此代碼的幾點說明：在循環內的條件下，我們利用邏輯或 “||” 的短路求值，因此僅當我們知道 `h` 不是 `NULL` 時，才跟隨 `h` 的下一個指針。
### 4. Queues with Linked Lists
這是我們設想實現隊列數據結構的方式的圖片，駐列中有元素 `1`、`2` 和 `3`。
駐列的實現是靠有前後字段的結構。前字段指向駐列的前面，後字段指向駐列的後面。 我們需要這兩個指針，以便我們可以有效地訪問駐列的兩端，這是必需的，因為出駐列（前）和入駐列（後）訪問列表的不同端。
使後向指針指向駐列末尾之後的一個元素很方便。因此，駐列末尾總會有一個多餘的元素，它沒有有效的數據或下一個指針。我們將其稱為虛擬節點，並在途中寫入 `X`。
上圖有以下定義:
```cpp=
typedef struct queue_header queue;
struct queue_header {
list* front;
list* back;
};
```
我們將其稱為 `header`，是因為它不包含駐列中的任何元素，而只是指向實際包含它們的鏈接列表的指針。通過類型定義，我們可以將 `queue_t` 用作代表指向駐列頭的指針的類型。我們以這種方式定義它，以便我們可以從客戶端隱藏駐列的真實實現，而僅將其稱為 `queue_t` 類型的元素。
```cpp=
typedef queue* queue_t;
```
這種類型的結構何時表示有效駐列？實際上，無論何時定義新的數據類型表示形式，都應首先考慮數據結構不變式。在我們思考和編寫實現接口的函數的前提條件和前提條件時，使這些內容顯式很重要。
我們需要的是，如果我們跟隨 `front`，然後向下移動鍊錶，則最終到達 `back`。我們稱其為列表段 (list segment)。我們還希望 `front` 和 `back` 都不為 `NULL`，以使其與圖片一致，即使駐列為空，也已經分配了一個元素。而已經編寫的`is_segment` 函數強制執行此操作。
```cpp=
bool is_queue(queue* Q) {
return Q != NULL
&& is_acyclic(Q->front)
&& is_segment(Q->front, Q->back);
}
```
要檢查駐列是否為空，我們只需比較駐列的`front` 和 `back`。 如果相等，則駐列為空；否則沒空。我們要求將有效駐列傳遞給我們。通常，在使用數據結構時，我們應始終要求並確保在操作它的函數的前後條件下滿足其不變性。在函數內部，我們通常會暫時違反不變式。
```cpp=
bool queue_empty(queue* Q)
//@requires is_queue(Q);
{
return Q->front == Q->back;
}
```
要獲得一個新的空駐列，我們只需分配一個列表結構，然後將新駐列的前後都指向該結構。根據我們的表示，我們不初始化列表元素，因為它的內容無關緊要。這樣說來，即使我們關心內存的內容，即使它恰好與放置在其中的默認值相同，也總是初始化內存是一個好習慣。
```cpp=
queue* queue_new()
//@ensures is_queue(\result);
//@ensures queue_empty(\result);
{
queue* Q = alloc(queue); // Create header
list* dummy = alloc(list); // Create dummy node
Q->front = dummy; // Point front
Q->back = dummy; // and back to dummy node
return Q;
}
```
要入駐列，也就是在駐列的後面添加一個新項目，我們只需將數據寫入後面的額外元素，創建一個新的 `back元素`，並確保正確地更新了指針。在編寫此類代碼之前，應先繪製一個圖表。這是將 `3` 插入列表的前後圖。新的或更新的項目在第二張圖中用虛線表示。
程式碼:
```cpp=
void enq(queue* Q, elem x
//@requires is_queue(Q);
//@ensures is_queue(Q);
{
list* new_dummy = alloc(list); // Create a new dummy node
Q->back->data = x; // Store x in old dummy node
Q->back->next = new_dummy;
Q->back = new_dummy;
}
```
最後，我們有出駐列操作。為此，我們只需要更改前指針，但是首先我們必須將出駐列元素保存在一個臨時變量中，以便稍後再返回它。在圖中：
程式碼:
```cpp=
elem deq(queue* Q)
//@requires is_queue(Q);
//@requires !queue_empty(Q);
//@ensures is_queue(Q);
{
elem x = Q->front->data;
Q->front = Q->front->next;
return x;
}
```
讓我們驗證一下指針解引用操作是否安全。我們有 `Q-> front-> data`，它需要兩個指針取消引用。從函數的前提我們知道`is_queue（Q）`。回想：
```cpp=
bool is_queue(queue Q) {
return Q != NULL
&& is_acyclic(Q->front)
&& is_segment(Q->front, Q->back);
}
```
我們看到 `Q->front` 是可以的，因為通過第一個測試，我們知道 `Q！= NULL` 是先決條件成立。通過第二個測試，我們看到 `Q->front` 和 `Q->back` 都不為空，因此可以取消引用它們。
我們還將賦值 `Q->front = Q->front->next`。為什麼這保留了不變性？因為我們知道駐列不為空（deq的第二個前提條件），因此 `Q->front！= Q->back`。因為 `Q->front` to `Q->back` 是有效的非空段，所以 `Q->front->next` 不能為 `null`。
關於出駐列操作的有趣點在於，我們沒有明確地取消分配第一個元素。如果該接口確定不會成為其他指針指向的駐列前面，則它將變得不可訪問：正在運行的其餘程序的任何操作都無法引用 (refer) 該項目。這意味著 `C0` 運行時間系統的垃圾回收器將在空間不足時回收此列表項。
### Stacks with Linked Lists
Sign in with Wallet
Connect another wallet