list的模擬實(shí)現(xiàn)1.1 list基本結(jié)構(gòu)list的結(jié)構(gòu)是個帶頭雙向循環(huán)鏈表每個數(shù)據(jù)是存儲在一個單獨(dú)的節(jié)點(diǎn)內(nèi)這個節(jié)點(diǎn)除了存儲數(shù)據(jù)還有兩個指針分別指向前一個和后一個節(jié)點(diǎn)這里定義節(jié)點(diǎn)的類用struct定義list的類用class的原因是一個默認(rèn)的共識一個類如果它的所有成員都不期望用訪問限定符限制的時候習(xí)慣上就用struct定義這里的list_node通常作為鏈表的一個子結(jié)構(gòu)是存儲每個數(shù)據(jù)的一個最小單元鏈表內(nèi)是要大量訪問內(nèi)部數(shù)據(jù)的所以這里不用訪問限定符限制。雖然這樣寫后別人就可以隨便訪問這些結(jié)構(gòu)了但是有迭代器之后在外層的角度是看不到節(jié)點(diǎn)的例如從使用的角度在接口使用的時候是不用鏈表的節(jié)點(diǎn)的無論是訪問修改還是插入刪除都是直接用迭代器的即雖然list_node是公有的但是其是一種隱形的封裝平時看不到也不會/不需要訪問這里 list_node T * _prev; 這個寫法是C 模板語法 指針語法的組合list_node T 是語法規(guī)定 list_node是定義的模板結(jié)構(gòu)體C 語法要求使用模板類 / 結(jié)構(gòu)體時必須通過模板參數(shù)指定具體的泛型類型這里T是模板參數(shù)所以list_node T 是模板結(jié)構(gòu)體的 “實(shí)例化類型寫法”屬于語法強(qiáng)制要求。*是語法規(guī)定*是 C 中 “指針類型” 的聲明符號list_node T *表示 “指向list_node T 類型對象的指針”這是指針的標(biāo)準(zhǔn)語法。補(bǔ)充一下這里模板聲明的作用范圍模板聲明的作用范圍template class T 是 “模板參數(shù)聲明”它的作用域僅限于緊跟在它后面的那個類或結(jié)構(gòu)體、函數(shù)。例如代碼語言javascriptAI代碼解釋// 第一個類模板list_node templateclass T // 作用范圍下面的 struct list_node struct list_node { ... }; // 第二個類模板list templateclass T // 作用范圍下面的 class list class list { ... };這里的兩個 template class T 是獨(dú)立的分別服務(wù)于 list_node 和 list 兩個類彼此不影響。新類模板需要重新聲明每個類模板都是獨(dú)立的實(shí)體即使兩個類的功能相關(guān)比如鏈表的節(jié)點(diǎn)和鏈表本身定義新的類模板時也必須重新寫template class T 。原因是模板參數(shù) T 是 “當(dāng)前類模板的局部參數(shù)”只在當(dāng)前類的范圍內(nèi)有效。比如 list_node 中的 T 和 list 中的 T 雖然名字相同但實(shí)際上是兩個獨(dú)立的模板參數(shù)只是習(xí)慣上用相同的字母表示。特殊情況嵌套類模板如果一個類模板內(nèi)部嵌套了另一個類嵌套類可以直接使用外部類的模板參數(shù)無需重復(fù)聲明代碼語言javascriptAI代碼解釋templateclass T class outer { // 嵌套類直接使用外部的 T class inner { T data; // 這里的 T 繼承自 outer 的 templateclass T }; };但如果嵌套類需要自己的獨(dú)立模板參數(shù)比如同時支持 T 和 U則需要單獨(dú)聲明代碼語言javascriptAI代碼解釋templateclass T class outer { // 嵌套類有自己的模板參數(shù) U templateclass U // 單獨(dú)聲明作用范圍下面的 inner class inner { T a; // 來自 outer 的 T U b; // 來自 inner 自己的 U }; };1.2 構(gòu)造 尾插在這里插入圖片描述尾插邏輯如圖在這里插入圖片描述在這里插入圖片描述這里運(yùn)行不了運(yùn)行不了的原因是list_node 缺少無參構(gòu)造函數(shù) 在 List.h 中l(wèi)ist_node 結(jié)構(gòu)體的構(gòu)造函數(shù)只有帶參數(shù)的版本list_node(const T x)但沒有無參構(gòu)造函數(shù)。 而在 list 類的構(gòu)造函數(shù)中執(zhí)行了 _head new Node; —— 這里嘗試調(diào)用 list_node 的無參構(gòu)造函數(shù)但該構(gòu)造函數(shù)并不存在因此會觸發(fā)編譯錯誤。這里有三種解決辦法方法 1利用list_node的帶參構(gòu)造顯式傳入默認(rèn)值在 list 類的構(gòu)造函數(shù)中創(chuàng)建頭結(jié)點(diǎn)時顯式調(diào)用 list_node 的帶參構(gòu)造并傳入 T 類型的默認(rèn)值通過 T() 觸發(fā) T 的默認(rèn)構(gòu)造也就是使用匿名對象T有可能是任意類型。這樣無需為 list_node 新增無參構(gòu)造函數(shù)。