# 2024q1 Homework1 (lab0)
contributed by < `alianlbj23` >

### Reviewed by `allenliao666`

- Git commit 都有依照修改項目撰寫對應的commit，而且沒有把多個函式修改全記錄在同一次 coomit 中，也有撰寫修改的原因及方法等等，方便日後追蹤，很值得我學習。
- 建議在 `q_reverse` 的部分增加從 `do-while` 迴圈修改為 `while` 的理由。
- `q_swap` 可以使用間接指標使程式碼更優雅簡潔。

### Reviewed by `brian049`
- commit message 描述清楚明瞭。:+1:

## 開發環境

$ neofetch --stdout
OS: Kubuntu 22.04.4 LTS x86_64 
Host: Modern 15 A5M REV:1.0 
Kernel: 6.5.0-21-generic 
Uptime: 14 mins 
Packages: 3004 (dpkg), 12 (snap) 
Shell: zsh 5.8.1 
Resolution: 1920x1080, 2560x1440 
DE: Plasma 5.24.7 
WM: KWin 
Theme: [Plasma], Breeze [GTK2/3] 
Icons: [Plasma], breeze-dark [GTK2/3] 
Terminal: konsole 
Terminal Font: MesloLGS NF 14 
CPU: AMD Ryzen 7 5700U with Radeon Graphics (16) @ 4.372GHz 
GPU: AMD ATI 04:00.0 Lucienne 
Memory: 3590MiB / 15338MiB

## 指定佇列的操作
### q_new
建立一個名為 `struct list_head` 的結構體，並使用 `list.h` 內的 `INIT_LIST_HEAD` 初始化成雙向鏈結串列

### q_free
使用 `list.h` 內的 `list_for_each_entry_safe` 走訪每個節點，需要注意釋放完傳入的鏈結串列底下的節點後，頭節點也要被刪除。

### q_insert_head和q_insert_tail
使用 `list.h` 內的` list_add` 和 `list_add_tail` 函式，可以將新的節點分別插入於鏈結串列的頭部和尾部。

這邊使用`strdup` 而非 `strcpy` 的原因在於 `strdup` 可自動計算字串長度，並分配足夠的記憶體複製儲存的字串，從而避免了 `strcpy` 在使用時可能導致緩衝區溢出的問題。

    new_node->value = strdup(s);

### `q_size`
逐一走訪節點以求得指定鏈結串列的長度

### `q_reverse`
考慮到使用 `while` 並以 `current != head` 作為條件，一開始將 `current = head` 會有矛盾，因此使用 `do-while` 讓它先做過一遍在判斷就能解決矛盾的問題。

    do {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = temp;
    } while (current != head);

為了確保在 `while` 循環的開始也能正確處理而沒有矛盾，因此修改成以下程式碼

-    do {
-        temp = current->next;
-        current->prev = temp;
-        current->next = current->prev;
-        current = temp;
-    } while (current != head);
+    if (!head || list_empty(head))
+        return;
+    struct list_head *current = head, *next = NULL;
+    while (next != head) {
+        next = current->next;
+        current->next = current->prev;
+        current->prev = next;
+        current = next;
+    }

每次的循環會修改 next 指向目前節點的下一個指標，藉此判斷是否走完了全部的節點。

## `q_swap`
對於現行節點 `current` 和其下一個節點 `next`，通過修改它們的 `prev` 和 `next` 指標來進行交換。接著更新 `current` 和 `next` 指向下一對相鄰節點，以便進行下一輪的交換。

while (current != head && next != head) {
        current->prev->next = next;
        next->prev = current->prev;
        current->next = next->next;
        next->next->prev = current;
        current->prev = next;
        next->next = current;
        current = current->next;
        next = current->next;
    }

參考了 ChenFuhuangKye 內的程式碼，發現他使用了 `list_move` 大幅簡化了程式碼，觀察 `list_move` 的敘述

list_move(struct list_head *node, struct list_head *head)

這個函式的設計允許我們將一個節點移動到另一個特定位置，特別是移動到鏈結串列的開頭。list_move 的實現依賴於兩個基本操作：`list_del` 和 `list_add` 。
### 功能說明
這個函式的主要功能是將一個節點從它當前的位置移動到一個新的位置，這個新位置是作為 `head` 節點之後的第一個元素。

### <s>實做</s> 細節

:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

- list_del
- 指定節點將從鏈結串列中移除。通過讓該節點的前後節點互相連接，並跳過該結點達成，因此指定節點不會被刪除。
- list_add
- 接著將 `list_del` 刪除的節點新增至 `head` 的開頭。
### 操作過程
1. 初始狀態
假設有一個鏈結串列為以下所示， `node` 指向1， `head` 指向2

graph LR;
head-->1-->2-->NULL;

2. 執行 `list_del` 節點 `node` 會被跳過，而 `node` 前後節點互相連接

graph LR;
head-->2-->NULL;

3. 執行 `list_add`
節點 `node` 會新增至 `head` 之後，因此最終的鏈結串列變成

graph LR;
head-->2-->1-->NULL;

:::warning
使用 Graphviz 予以視覺化，並嵌入到 HackMD 筆記中
:::

-    struct list_head *current = head->next, *next = current->next;
-    while (current != head && next != head) {
-        current->prev->next = next;
-        next->prev = current->prev;
-        current->next = next->next;
-        next->next->prev = current;
-        current->prev = next;
-        next->next = current;
+    struct list_head *current = head->next;
+    while (current != head && current->next != head) {
+        list_move(current, current->next);
         current = current->next;
-        next = current->next;
     }

:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::