您好,登錄后才能下訂單哦!
這篇文章主要介紹“C++ List鏈表如何使用”的相關(guān)知識,小編通過實際案例向大家展示操作過程,操作方法簡單快捷,實用性強(qiáng),希望這篇“C++ List鏈表如何使用”文章能幫助大家解決問題。
1. list是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器,并且該容器可以前后雙向迭代。
2. list的底層是雙向鏈表結(jié)構(gòu),雙向鏈表中每個元素存儲在互不相關(guān)的獨立節(jié)點中,在節(jié)點中通過指針指向其前一個元素和后一個元素。
3. list與forward_list非常相似:最主要的不同在于forward_list是單鏈表,只能朝前迭代,已讓其更簡單高效。
4. 與其他的序列式容器相比(array,vector,deque),list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率更好。
5. 與其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的隨機(jī)訪問,比如:要訪問list的第6個元素,必須從已知的位置(比如頭部或者尾部)迭代到該位置,在這段位置上迭代需要線性的時間開銷;list還需要一些額外的空間,以保存每個節(jié)點的相關(guān)聯(lián)信息(對于存儲類型較小元素的大list來說這可能是一個重要的因素)
list的底層:帶頭節(jié)點雙向鏈表結(jié)構(gòu)
使用list要帶上頭文件’
#include<list>
//構(gòu)造打印練習(xí) void TestList() { list<int>L1; //十個值為5 list<int>L2(10,5); //區(qū)間方式構(gòu)造 vector<int>v{ 0,3,35,34,2 }; list<int>L3(v.begin(),v.end()); //拷貝構(gòu)造 list<int>L4(L3); //列表構(gòu)造 list<int>L5{ 1,23,34 }; //打印,范圍for for (auto e:L2) { cout << e << " "; } cout << endl; //迭代器打印 auto it = L3.begin(); while (it != L3.end()) { cout << *it << " "; ++it; } cout << endl; }
1. begin與end為正向迭代器,對迭代器執(zhí)行++操作,迭代器向后移動
2. rbegin(end)與rend(begin)為反向迭代器,對迭代器執(zhí)行++操作,迭代器向前移動
上面一些方法的使用,都很簡單,隨意測試一下
void TestList() { list<int>L; L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); L.push_back(5); cout << L.size() << endl; cout << L.front() << endl;//訪問起始位置 cout << L.back() << endl;//訪問末尾 L.front() = 50; L.back() = 1000; L.pop_back();//刪除list中最后一個元素 cout << L.size() << endl; cout << L.front() << endl; cout << L.back() << endl; }
任意位置的插入
void TestList() { list<int>L; L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); L.push_back(5); PrintList(L); auto pos = L.begin(); L.insert(pos, 0);//在1的位置插入0,插入之前 PrintList(L); cout << *pos << endl;//查看迭代器是否正常使用 //在鏈表中值為data的節(jié)點前插入10個值為2的元素 int data = 0; cin >> data; //在這個區(qū)間內(nèi)找data,返回pos。如果沒找到返回end pos= find(L.begin(),L.end(),data); if (pos != L.end()) { L.insert(pos, 10, 2); } PrintList(L); //區(qū)間形式 pos = L.begin(); vector<int>v{ 10,20,34,34,1244 }; L.insert(pos, v.begin(), v.end()); PrintList(L); }
void TestList() { list<int>L; L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); L.push_back(5); PrintList(L); auto pos1 = L.begin(); auto pos2 = find(L.begin(),L.end(),5); cout << *pos2 << endl; L.erase(pos1);//將pos1位置處元素刪除 PrintList(L); cout << *pos2 << endl;//檢測迭代器是否失效 cout << *pos1 << endl; //結(jié)果是pos2正常,pos1失效 }
erase會導(dǎo)致刪除位置的迭代器失效,但是對于其他位置的迭代器沒有影響。
迭代器失效即迭代器所指向的節(jié)點的無效,即該節(jié)點被刪除了。因為list的底層結(jié)構(gòu)為帶頭結(jié)點的雙向循環(huán)鏈表,因此在list中進(jìn)行插入時是不會導(dǎo)致list的迭代器失效的,只有在刪除時才會失效,并且失效的只是指向被刪除節(jié)點的迭代器,其他迭代器不會受到影響
模擬實現(xiàn)具體可以參閱網(wǎng)上文章
vector | list | |
底 層 結(jié) 構(gòu) | 動態(tài)順序表,一段連續(xù)空間 | 帶頭結(jié)點的雙向循環(huán)鏈表 |
隨 機(jī) 訪 問 | 支持隨機(jī)訪問,訪問某個元素效率O(1) | 不支持隨機(jī)訪問,訪問某個元素效率O(N) |
插 入 和 刪 除 | 任意位置插入和刪除效率低,需要搬移元素,時間復(fù)雜度為O(N),插入時有可能需要增容,增容:開辟新空間,拷貝元素,釋放舊空間,導(dǎo)致效率更低 | 任意位置插入和刪除效率高,不需要搬移元素,時間復(fù)雜度為O(1) |
空 間 利 用 率 | 底層為連續(xù)空間,不容易造成內(nèi)存碎片,空間利用率高,緩存利用率高 | 底層節(jié)點動態(tài)開辟,小節(jié)點容易造成內(nèi)存碎片,空間利用率低,緩存利用率低 |
迭 代 器 | 原生態(tài)指針 | 對原生態(tài)指針(節(jié)點指針)進(jìn)行封裝 |
迭 代 器 失 效 | 在插入元素時,要給所有的迭代器重新賦值,因為插入元素有可能會導(dǎo)致重新擴(kuò)容,致使原來迭代器失效,刪除時,當(dāng)前迭代器需要重新賦值否則會失效 | 插入元素不會導(dǎo)致迭代器失效,刪除元素時,只會導(dǎo)致當(dāng)前迭代器失效,其他迭代器不受影響 |
使 用 場 景 | 需要高效存儲,支持隨機(jī)訪問,不關(guān)心插入刪除效率 | 大量插入和刪除操作,不關(guān)心隨 機(jī)訪問 |
關(guān)于“C++ List鏈表如何使用”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識,可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會為大家更新不同的知識點。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。