# 2019q1 第 11 週測驗題 (中) :::info 目的: 檢驗學員對 linked list 實作的技巧 ::: --- ### 測驗 `1` 給定一個 circular linked list 實作如下: (檔案 `list.h`) ```cpp #ifndef INTERNAL_LIST_H #define INTERNAL_LIST_H /* circular doubly-linked list */ typedef struct __list_t { struct __list_t *prev, *next; } list_t; /* * Initialize a list to empty. Because these are circular lists, an "empty" * list is an entry where both links point to itself. This makes insertion * and removal simpler because they do not need any branches. */ static inline void list_init(list_t *list) { list->prev = list; list->next = list; } /* * Append the provided entry to the end of the list. This assumes the entry * is not in a list already because it overwrites the linked list pointers. */ static inline void list_push(list_t *list, list_t *entry) { list_t *prev = list->prev; entry->prev = prev; entry->next = list; prev->next = entry; list->prev = entry; } /* * Remove the provided entry from whichever list it is currently in. This * assumes that the entry is in a list. You do not need to provide the list * because the lists are circular, so the list's pointers will automatically * be updated if the first or last entries are removed. */ static inline void list_remove(list_t *entry) { list_t *prev = entry->prev; list_t *next = entry->next; prev->next = next; next->prev = prev; } /* * Remove and return the first entry in the list or NULL if the list is empty. */ static inline list_t *list_pop(list_t *list) { list_t *foo = list->prev; if (foo == list) return NULL; LL1 } #endif ``` 請參照上方程式註解,補完對應程式碼。 ==作答區== LL1 = ? * `(a)` return foo; * `(b)` return foo->next; * `(c)` return foo->prev; * `(d)` list_remove(foo->prev); return foo; * `(e)` list_remove(foo); return foo; * `(f)` list_remove(foo->next); return foo->next; * `(g)` list_remove(foo); return foo->next; :::success 延伸問題: 1. 研讀 2019q3 Week11 的 cache-oblivious data structures 參考資料,記錄所見所聞; 2. 依據之前給定的 Linux 核心 linked list 實作,開發 cache-oblivious 的版本,並證實其效益; 3. 實作 Skip list,並且比照之前的 unit test 提供對應的測試、效能分析,還有改善機制 :::