目錄1.list 的基本使用1.1 創(chuàng)建和初始化1.2. 插入元素1.3. 刪除元素1.4. 訪問元素1.5 遍歷1.6 總結(jié)list是C標(biāo)準(zhǔn)庫STL中的雙向鏈表容器屬于list頭文件。它的特點是動態(tài)大小可以隨時插入或刪除元素不需要手動管理內(nèi)存。雙向鏈表每個節(jié)點都連接前后兩個節(jié)點支持雙向遍歷。高效插入刪除插入和刪除的時間復(fù)雜度是O(1)比vector快vector可能會移動大量元素。隨機訪問慢不像vector可以直接訪問vec[i]list只能順序遍歷O(n)。1.list的基本使用1.1創(chuàng)建和初始化std::listint lst1; // 創(chuàng)建空 list std::listint lst2 {1, 2, 3, 4, 5}; // 用初始化列表創(chuàng)建 std::listint lst3(5, 100); // 創(chuàng)建 5 個元素每個值都為 100 std::listint lst4(lst2); // 拷貝構(gòu)造1.2. 插入元素lst.push_back(10); // 尾部插入 10 lst.push_front(5); // 頭部插入 5 auto it lst.begin(); std::advance(it, 2); // 迭代器前進 2 步 lst.insert(it, 99); // 在第 3 個位置插入 991.3. 刪除元素lst.pop_back(); // 刪除最后一個元素 lst.pop_front(); // 刪除第一個元素 auto it lst.begin(); std::advance(it, 1); lst.erase(it); // 刪除第二個元素 lst.remove(3); // 刪除所有值為 3 的元素 lst.clear(); // 清空 list1.4. 訪問元素std::cout lst.front(); // 訪問第一個元素 std::cout lst.back(); // 訪問最后一個元素1.5 遍歷// 方式 1使用范圍 for for (int num : lst) { std::cout num ; } // 方式 2使用迭代器 for (std::listint::iterator it lst.begin(); it ! lst.end(); it) { std::cout *it ; }1.6 總結(jié)區(qū)別vector動態(tài)數(shù)組list雙向鏈表底層結(jié)構(gòu)動態(tài)數(shù)組連續(xù)內(nèi)存雙向鏈表分散存儲訪問速度隨機訪問快 (O(1))隨機訪問慢 (O(n))插入刪除尾部操作快 (O(1))中間插入/刪除慢 (O(n))任意位置插入/刪除快 (O(1))內(nèi)存使用連續(xù)存儲節(jié)省空間但可能需要擴容每個節(jié)點有額外指針開銷內(nèi)存占用較大遍歷方式支持 []可用 、- 運算符只能用迭代器 或 --pair這是 C 標(biāo)準(zhǔn)庫里的“對組”或“二元組”。它里面可以裝兩個不同類型的數(shù)據(jù)。比如pairint, string就是“一個整數(shù) 一個字符串”捆綁在一起。list這就是我們剛才聊的鏈表容器雙向鏈表。合在一起listpairA, B意思就是——這個鏈表里每一個節(jié)點存儲的數(shù)據(jù)不再是一個普通的數(shù)字而是一個“小包裹”pair。