個人主頁：平行線也會相交??
歡迎 點贊?? 收藏? 留言? 加關(guān)注??本文由 平行線也會相交 原創(chuàng)
收錄于專欄【C++之路】??
本專欄旨在記錄C++的學(xué)習(xí)路線，望對大家有所幫助???
希望我們一起努力、成長，共同進(jìn)步。??

list是STL中的一種容器，底層其實就是一個雙向鏈表。

既然底層實現(xiàn)是雙向鏈表，所以list重要的一點就是插入和刪除操作的時間復(fù)雜度為常數(shù)時間O(1)，這是因為鏈表的結(jié)構(gòu)不需要像數(shù)組一樣進(jìn)行內(nèi)存重排。

當(dāng)然，如果要頻繁訪問鏈表中的元素，需要沿著鏈表進(jìn)行遍歷，這導(dǎo)致list容器訪問操作的時間復(fù)雜度為O(n)。

下面將對list中的常見的用法進(jìn)行一一介紹。

一、創(chuàng)建變量

下面鏈表變量的創(chuàng)建：

list<int> it1;//創(chuàng)建一個空的list
list<int> it2 = { 1,2,3,4,5 };//創(chuàng)建一個帶有初始元素的list

二、增刪查改

1??插入元素

插入元素總共分為三種：尾插、頭插、任意位置插入。
尾插（push_back()）：

list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);

頭插（push_front()）：

list<int> lt1;
lt1.push_front(1);
lt1.push_front(2);

任意位置插入刪除（insert()）：

//在第三個位置進(jìn)行插入10
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
list<int>::iterator it = lt1.begin();
for (size_t i = 0; i < 2; i++)
{
	it++;
}
lt1.insert(it, 10);
for (auto e : lt1)
{
	cout << e << " ";
}
cout << endl;

2??刪除

//刪除的節(jié)點中數(shù)據(jù)為3的節(jié)點
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
for (auto e : lt1)
{
	cout << e << " ";
}
cout << endl;

list<int>::iterator it = lt1.begin();
it = find(lt1.begin(), lt1.end(), 3);
//判斷是否查找成功
if (it != lt1.end())
{
	lt1.erase(it);
	//節(jié)點此時已經(jīng)被刪除了，當(dāng)前的迭代器失效
	//*it *= 10;
}
for (auto e : lt1)
{
	cout << e << " ";
}
cout << endl;

下面來刪除list中的偶數(shù)元素：

list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);

	list<int>::iterator it = lt1.begin();
	while (it != lt1.end())
	{
		if (*it % 2 == 0)
		{
			it = lt1.erase(it);
		}
		else
		{
			it++;
		}
	}
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

3??查找和修改

這里我們需要注意一點：std::list沒有提供內(nèi)置的find()函數(shù)。

原因主要有兩點：
第一：遍歷代替索引訪問：由于std::list是一個雙向鏈表，不支持通過索引來直接訪問元素。相反，要訪問或查找元素，需要使用迭代器進(jìn)行迭代操作。

第二：鏈表的特點是插入和刪除元素的時間復(fù)雜度為O(1)，但訪問元素的時間復(fù)雜度為O(n)，其中n是鏈表長度。相比之下，std::vector的訪問時間復(fù)雜度為O(1)。由于鏈表不支持快速隨機(jī)訪問，使用線性搜索遍歷整個鏈表可能是更高效的操作。

舉例：

//在鏈表中查找節(jié)點中數(shù)據(jù)為3的節(jié)點，如果查找成功，將該數(shù)據(jù)的數(shù)據(jù)*10
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
for (auto e : lt1)
{
	cout << e << " ";
}
cout << endl;

list<int>::iterator it = lt1.begin();
it = find(lt1.begin(), lt1.end(), 3);
//判斷是否查找成功
if (it != lt1.end())
{
	//查找成功則將迭代器位置的數(shù)據(jù)*10
	*it *= 10;
}
for (auto e : lt1)
{
	cout << e << " ";
}
cout << endl;
}

可以看到查找成功并將該節(jié)點的數(shù)據(jù)*10。

三、list大小計算

std::list提供了size()函數(shù)，用于返回鏈表中元素的數(shù)量。

四、迭代器遍歷

list<int> lt1 = { 1,2,3,4,5 };

for (auto it = lt1.begin(); it != lt1.end(); it++)
{
	(*it)++;
	cout << *it << " ";
}
cout << endl;

五、常見算法

1??排序

list<int> lt = { 12,56,2,95,35,78,47 };
lt.sort();
for (auto e : lt)
{
	cout << e << " ";
}
cout << endl;

2??刪除指定值-remove()

這里需要注意的是：remove()函數(shù)會移除鏈表中所有與指定值相等的元素，而不僅僅是第一個匹配項。這與erase()函數(shù)的行為不同，erase()函數(shù)通常只移除第一個匹配項。

list<int> lt1 = { 12,56,2,95,35,78,47 };
lt1.remove(56);
for (auto e : lt1)
{
	cout << e << " ";
}
cout << endl;

如果鏈表中沒有想要刪除的指定值，則remove()函數(shù)不會作任何事情，也不會報錯。請看舉例：

3??鏈表元素轉(zhuǎn)移-splice()

在STL中，std::list提供了splice()函數(shù)，用于將一個鏈表的元素或者一個元素范圍轉(zhuǎn)移到另一個鏈表中。

splice()函數(shù)共有3個版本：

void splice(const_iterator position, list& x);
void splice(const_iterator position, list& x, const_iterator i);
void splice(const_iterator position, list& x, const_iterator first, const_iterator last);

下面對splice()函數(shù)的3個版本進(jìn)行舉例，請看：

list<int> lt1 = { 1,2,3,4 };
list<int> lt2 = { 10,20,30,40 };

list<int> lt3 = { 1,2,3,4 };
list<int> lt4 = { 10,20,30,40 };

list<int> lt5 = { 1,2,3,4 };
list<int> lt6 = { 10,20,30,40 };

// 將lt2中的所有元素移動到lt1的末尾
lt1.splice(lt1.end(), lt2);
for (auto e : lt1)
	cout << e << " ";
cout << endl;

// 將lt4中的第二個元素移動到lt3的開頭
auto it3 = lt3.begin();
auto it4 = lt4.begin();
it4++;
lt3.splice(it3, lt4, it4);
for (auto e : lt3)
	cout << e << " ";
cout << endl;

//將lt6中的20 30 40移動到lt5的最后位置
auto first = ++lt6.begin();
auto end = lt6.end();
lt5.splice(lt5.end(), lt6, first, end);
for (auto e : lt5)
	cout << e << " ";
cout << endl;

運(yùn)行結(jié)果如下：

好了，以上就是本文的全部內(nèi)容，主要對list的一些基本語法和用法進(jìn)行了介紹。
就到這里吧，再見啦友友們?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-599966.html

到了這里，關(guān)于【C++】STL---list基本用法介紹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！