链表：

                是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的

链表的组成：

        链表是由一系列结点组成

结点的组成：

        一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

3. 结构

STL中的链表是一个双向循环链表

由于链表的存储方式不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

 4. list优缺点：

list的优点：

• 可以对任意位置进行快速插入或者删除
• 采用动态存储分配，不会造成内存浪费和溢出
• 链表执行插入和删除操作十分方便，修改指针即可，不需要大量移动数据

list的缺点：

• 容器遍历速度没有数组快，占用空间比数组大
• 链表灵活，但是空间(指针域)和时间(遍历)额外耗费比较大

5. 特别：

list容器的插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

二、list构造函数

• list  lst;                             // list采用模板类实现，对象的默认构造方式
• list(beg,  end);                        // 构造函数讲（beg，end）区间内的元素拷贝给本身
• list(n,  elem);                          // 构造函数将n个elem拷贝给本身
• list(const  list  &  lst);            // 拷贝构造函数

#include
#include
#include
using namespace std;
//遍历
void print_List(list &l)
{
	for(list::iterator it = l.begin();it!=l.end();it++)
	{
		cout<<*it<<" ";
	}
	cout< l; // 默认构造

	// 添加数据
	l.push_back(10);
	l.push_back(20);
	l.push_back(30);
    l.push_back(40);
		l.push_back(50);
		// 遍历容器
	print_List(l);

	// 区间构造
	list  L2(l.begin(),l.end());
	print_List(L2);

	// 拷贝构造
	list L3(L2);
	print_List(L3);

	// n 个 elem 的方式
	list L4(10,100);
	print_List(L4);
	return 0;
}

 三、list赋值和交换

• assign(beg,  end);                                  // 将（beg，end）区间内的数据拷贝赋值给本身
• assign(n,  elem);                                       // 将n个elem拷贝赋值给本身
• list  operator=(const  list  &  lst);            // 重载等号操作符
• swap(lst);                                                 // 将lst与本身的元素互换

#include
#include
#include
using namespace std;
//遍历
void print_List(list &l)
{
	for(list::iterator it = l.begin();it!=l.end();it++)
	{
		cout<<*it<<" ";
	}
	cout< L1;
	for(int i=0;i<10;i++)
	{
		L1.push_back(i);
	}
	print_List(L1);

	// 赋值
	list L2;
	L2 = L1;  // operator= 进行赋值
	print_List(L2);

	// assign 区间赋值
	list L3;
	L3.assign(L2.begin(),L2.end());
	print_List(L3);

    // assign n 个 elem 的方式
	list L4;
	L4.assign(10,100);
	print_List(L4);


	// 交换
	cout<<"交换前L3 和 L4："< 
 四、list大小操作 
 
 
size();                                  // 返回容器中元素的个数
empty();                             // 判断容器是否为空
resize(num);                       // 重新指定容器的长度为num，若容器变长，则以默认值0填充新的位置
 
                                          // 如果容器变短，则末尾超出容器长度的元素被删除
 
 
resize(num,  elem);  // 重新指定容器的长度为num，若容器变长，则以elem值填充新的位置
 
                                         // 如果容器变短，则末尾超出容器长度的元素被删除
 
 
	#include
	#include
	#include
	using namespace std;
	//遍历
	void print_List(list &l)
	{
		for(list::iterator it = l.begin();it!=l.end();it++)
		{
			cout<<*it<<" ";
		}
		cout< L1;
		for(int i=0;i<10;i++)
		{
			L1.push_back(i);
		}
		print_List(L1);
	
		// 判断容器是否为空
		if(L1.empty())
		cout<<"L1 为空"< 
 五、list插入和删除 
 
 
push_back(elem);             // 在容器尾部加入一个元素
push_front(elem);            // 在容器开头插入一个元素
pop_back();                       // 删除容器中最后一个元素
pop_front();                      // 删除容器第一个元素
 
 
 
insert(pos,  elem);                   // 在pos位置插入elem元素的拷贝，返回新数据的位置
insert(pos,  n,  elem);              // 在pos位置插入n个elem数据，无返回值
insert(pos,  beg,  end);            // 在pos位置插入（beg，end）区间内的数据，无返回值
 
 
 
erase(beg,  end);                      // 删除（beg，end）区间内的数据，返回下一个数据的位置
erase(pos);                               // 删除pos位置的数据，返回下一个数据的位置
 
 
 
remove(elem);                        // 删除容器中所有与elem值匹配的元素
 
 
 
clear();                                   // 移除容器中所有的数据
 
	#include
	#include
	#include
	using namespace std;
	//遍历
	void print_List(list &l)
	{
		for(list::iterator it = l.begin();it!=l.end();it++)
		{
			cout<<*it<<" ";
		}
		cout< L1;
		for(int i=0;i<10;i++)
		{
			L1.push_back(i);
		}
		print_List(L1);
	
		// 头插
		L1.push_front(100);
		// 尾插
		L1.push_back(200);
		print_List(L1);
		
	
		//insert 插入
		L1.insert(++L1.begin(),1000);  // 第一个参数是迭代器（位置）,第二个参数是插入的内容
		print_List(L1); // 迭代器可以偏移
	
		// 删除
		L1.erase(L1.begin());  // 迭代器可以偏移
	    list::iterator it = L1.begin(); // 设置it为迭代器
	    L1.erase(it);
		print_List(L1);
	
		// 移除
		L1.push_back(10000);
		print_List(L1);
		L1.remove(10000); // 移除list中所有的指定内容
		print_List(L1);
	
	    // 清空
	    L1.clear();
	    print_List(L1); // 清空所有的内容
		return 0;
	}
 
 六、list数据存取 
 
 
list本质是链表，不是连续线性空间存储数据，迭代器也不支持随机访问
 
 
list不支持[]和at()访问
 
 
 
 
front();          // 返回第一个元素
back();               // 返回最后一个元素
 
	#include
	#include
	#include
	using namespace std;
	//遍历
	void print_List(list &l)
	{
		for(list::iterator it = l.begin();it!=l.end();it++)
		{
			cout<<*it<<" ";
		}
		cout< L1;
		for(int i=0;i<10;i++)
		{
			L1.push_back(i);
		}
		print_List(L1);
	
	    // 访问第一个和最后一个元素
	    cout<<"第一个元素为："<::iterator it = L1.begin();
		it++; // 只能++或者--不能+1
		return 0;
	}
 
 七、list反转和排序 
 
 
reverse();            // 反转链表
sort();                       // 链表排序
 
 
	#include
	using namespace std;
	#include
	#include
	
	//遍历
	void print_List(list &L)
	{
		for(list::iterator it = L.begin();it!=L.end();it++)
		{
			cout<<*it<<" ";
		}
		cout< L1;
		for(int i=0;i<10;i++)
		{
			L1.push_back(i);
		}
		cout<<"反转前："< 就让第一个数大于第二个数
		return v1 > v2;
	}
	
	void test02()
	{
		// 排序
		list L2;
		L2.push_back(5);
		L2.push_back(78);
		L2.push_back(2);
		L2.push_back(98);
		L2.push_back(65);
		cout<<"排序前："< 
八、附加一个排序案例 
	#include
	using namespace std;
	#include
	#include
	
	class person
	{
	public:
		person(string name,int age,int height)
		{
			this->name=name;
			this->age=age;
			this->height=height;
		}
		string name;
		int age;
		int height;
	};
	
	void print_list(list&L)
	{
		for(list::iterator it=L.begin();it!=L.end();it++)
		{
			cout<<"姓名："<name<<"t年龄："<age<<"t身高："<height<p2.height;
		// 按年龄升序
		return p1.age L;
		person p1("刘备",35,175);
		person p2("曹操",45,180);
		person p3("孙权",40,170);
		person p4("赵云",25,190);
		person p5("张飞",35,189);
		person p6("关羽",35,200);
	
		L.push_back(p1);
		L.push_back(p2);
		L.push_back(p3);
		L.push_back(p4);
		L.push_back(p5);
		L.push_back(p6);
	
		// 排序前
		print_list(L);
	
		// 排序后
		cout<<"按年龄排序后："< 

                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！